Enigma 1777

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 Nk(j), the number of kth 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…;  72 < 50 but 82 > 50. So Nk(j) = j1/k.

Now one’s first thought might be to add up Nk(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, 43 = (22)3 = (23)2 = 82. So counting up powers of 2 and 3 will include 64 twice.

The (incorrect) formula N(j) = 1 + Σ(j1/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:

  • (22)= (23)= 64
  • (22)= (25)= 1024
  • (32)= (33)= 729
  • (42)= (43)= 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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s