*Spoiler for New Scientist Enigma 1777 “Powerful tombola” *(Follow the link to see the puzzle.)

Let’s first ask, how many perfect squares are less than or equal to *j*? More generally, what is *N _{k}*(

*j*), the number of

*k*

^{th}powers less than or equal to

*j*? Well, clearly, for example, if

*j*= 50, there are 7 perfect squares less than or equal to

*j*because √50 = 7.071…; 7

^{2}< 50 but 8

^{2}> 50. So

*N*(

_{k}*j*) =

_{⌊}

*j*

^{1/k}

_{⌋}.

Now one’s first thought might be to add up *N _{k}*(

*j*) for all

*k*to get

*N*(

*j*), the number of powers less than or equal to

*j*. But this gets into trouble.

First, if you ask how many fourth powers there are less than 50, all of the ones you find also are squares, so they don’t add to the total number of powers under 50. Likewise any other even power. So to avoid double counting, we consider only prime powers.

Here’s another double counting problem to handle: 1 is a power of every number.

And here’s another: consider (prime) powers of (prime) powers. For instance, 4^{3} = (2^{2})^{3} = (2^{3})^{2} = 8^{2}. So counting up powers of 2 and 3 will include 64 twice.

The (incorrect) formula *N*(*j*) = 1 + Σ(_{⌊}*j*^{1/k}_{⌋}–1), where the sum is over *k* = primes, takes care of the first and second types of double counting. Then we can correct for the third type. The smallest prime powers of prime powers are:

- (2
^{2})^{3 }= (2^{3})^{2 }= 64 - (2
^{2})^{5 }= (2^{5})^{2 }= 1024 - (3
^{2})^{3 }= (3^{3})^{2 }= 729 - (4
^{2})^{3 }= (4^{3})^{2 }= 4096

Those are all of them less than 15000; should be enough? Hope so. Now let’s do a binary search.

For *j* = 100, we have _{⌊}100^{(1/2)}_{⌋} = 10, _{⌊}100^{(1/3)}_{⌋} = 4, _{⌊}100^{(1/5)}_{⌋} = 2; then *N*(100) = 1+(9+3+1)-1 (the -1 corrects for double counting 64) = 13. That’s 13% winning numbers. We need *j* larger.

For *j* = 1000, we have _{⌊}100^{(1/2)}_{⌋} = 31, _{⌊}100^{(1/3)}_{⌋} = 10, _{⌊}100^{(1/5)}_{⌋} = 3; _{⌊}100^{(1/7)}_{⌋} = 2; then *N*(100) = 1+(30+9+2+1)-2 (the -2 corrects for double counting 64 and 729) = 41. That’s 4.1% winning numbers. We need *j* larger.

Similarly for 10000 there are 125 winners, getting close to our 1%. We need *j* larger.

Since we only have the corrections up to 15000 let’s try 15000. Turns out there are … 150 winners. Bang on 1%! (The sum is: 1+(121+23+5+2+1+1)-4).

There were 15000 tickets.