### Random Post

### Recent Posts

### Recent Comments

### Archives

### Categories

- article (11)
- enigma (1,270)
- misc (3)
- project euler (2)
- puzzle (67)
- site news (50)
- tantalizer (69)
- teaser (7)

### Site Stats

- 206,371 hits

Programming Enigma Puzzles

12 October 2018

Posted by on **From New Scientist #2197, 31st July 1999** [link]

George’s lucky number is six. After extensive number-crunching he has discovered that exactly half of all the numbers from 1 to his telephone number (inclusive) contain at least one six and that his telephone number is unique in possessing this property. George has done the hard work — all you have to do is deduce his telephone number, which has fewer than eight digits.

[enigma1041]

%d bloggers like this:

We can simply test all numbers up to the largest 7-digit number keeping a running total. We add 1 when we encounter a number that contains a 6 and subtract 1 when it doesn’t contain a 6. Then we look for places where the total is 0, in which case the number is “balanced” (there are as many numbers below it that contain the digit 6 as do not contain the digit 6).

If we turn the digit and the numbers into strings we can get a simple program that runs in 728ms (using PyPy).

Run:[ @repl.it ]Solution:George’s telephone number is 6377290.However, with a bit of analysis we can get a faster (but more complicated) program.

Analytically:

If we consider 1-digit numbers (including 0 for the moment), we find that 9 of them don’t include a 6 and one of them does. So if we count –1 for the numbers that don’t include 6 and +1 for the ones that do. So when we get to the end of the 1-digit numbers we would have a score of –8.

Now if we consider 2-digit numbers. The

6xnumbers will contribute +10, but all other decades will contribute –8. So as we count in blocks of 10 we would see:Considering the 3-digit numbers, we will get +100 for the

6xx, but –62 for all the others:For 4-digit numbers:

For 5-digit numbers:

For 6-digit numbers:

For 7-digit numbers:

which starts with a negative score and ends with a positive score.

So, we see that when we get to 5,999,999 we have a score –377,292 and the next 1,000,000 numbers all start with the digit 6, so by the time we get to 6,999,999 we have a score of 622,708, somewhere in the middle of the 6,xxx,xxx numbers the score has crossed zero.

In fact, as we included 0 when counting our numbers we actually want to find when there is a score of –1, and this occurs at 5,999,999 + 377,291 = 6,377,290 which is the required solution.

The following Python program uses the above analysis to build a sequence of counts of consecutive blocks of numbers that all either contain the required digit, or do not contain it. Each block is them examined to see if the total crosses 0 during that block, and from this solutions are found.

This program runs in 350ms (still using PyPy).

In general, if we consider all numbers with

kor fewer digits, and a (non-zero) digitd, then the proportion of those numbers that contain the specified digit is:Which makes

Ran increasing series:It makes sense that it should be an increasing sequence, as we get longer and longer numbers it is more likely that (at least) one of the digits will be the “special” digit.

Rcrosses the 0.5 value during the 7-digit numbers, so there will always be a solution involving a 7-digit number for any non-zero “special” digitd.It so happens that 6 is the only “special” digit which has only one “balanced” number, and that is the solution to this problem.

The other digits all have more than one solution (and for the digit 0 (which isn’t covered by the above analysis) the “balanced” numbers are 8 digits).

Here are graphs of

Rfor each “special” digit. The horizontal scale is logarithmic (as indicated on the axes ford=6):d=1:d=2:d=3:d=4:d=5:d=6:d=7:d=8:d=9:d=0:And here are numbers that are “balanced” for each “special” digit (grouped by the number of digits in the “balanced” number):

Some numbers balance more than one digit. The smallest example is 2, which balances both 1 and 2. But here’s a full list:

A nice analysis, Jim. I have a Python solution that produces a fast solution when the special digit is six but it only finds a subset of all balanced numbers for other special digits because it misses numbers in regions where the count difference decreases. But this teaser is simple enough to make even a C/C++ program a five minute job: