Enigmatic Code

Programming Enigma Puzzles

Enigma 1041: Lucky sixes

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]

2 responses to “Enigma 1041: Lucky sixes

  1. Jim Randell 12 October 2018 at 7:25 am

    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 ]

    from enigma import irange, arg, printf
    
    d = arg(6, 0, int)
    k = arg(7, 1, int)
    printf("[d={d} k={k}]")
    
    # count numbers n that don't contain d and those that do for n up to k digits
    s = str(d)
    t = 0
    for n in irange(1, 10 ** k - 1):
      t += (1 if s in str(n) else -1)
      if t == 0:
        printf("{n}")
    

    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 6x numbers will contribute +10, but all other decades will contribute –8. So as we count in blocks of 10 we would see:

    –8, –16, –24, –32, –40, –48, –38, –46, –54, –62

    Considering the 3-digit numbers, we will get +100 for the 6xx, but –62 for all the others:

    –62, –124, –186, –248, –310, –372, –272, –334, –396, –458

    For 4-digit numbers:

    –458, –916, –1374, –1832, –2290, –2748, –1748, –2206, –2664, –3122

    For 5-digit numbers:

    –3122, –6244, –9366, –12488, –15610, –18732, –8372, –11854, –14976, –18098

    For 6-digit numbers:

    –18098, –36196, –54294, –72392, –90490, –108588, –8588, –26686, –44784, –62882

    For 7-digit numbers:

    –62882, –125764, –188646, –251528, –314410, –377292, 622708, 559826, 496944, 434062

    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).

    from enigma import irange, arg, printf
    
    # extend s with t, combining ends if possible
    def extend(s, t):
      if not(s) or s[-1] * t[0] < 0:
        s.extend(t)
      else:
        s[-1] += t[0]
        s.extend(t[1:])
    
    # possible digits (in order)
    digits = tuple(irange(0, 9))
    
    d = arg(6, 0, int) # "special" digit
    k = arg(7, 1, int) # max digit length
    printf("[d={d} k={k}]")
    
    # sequence of steps for 1 digit numbers
    s = list(x for x in [-d, +1, d - 9] if x != 0)
    
    # construct the sequence for k digit numbers
    m = 1
    while k > 1:
      m *= 10
      _s = list()
      for x in digits:
        extend(_s, [m] if x == d else s)
      s = _s
      k -= 1
    
    # examine the steps to find "balanced" numbers
    (t, n) = (1, -1)
    for x in s:
      _t = t + x
      if 0 in range(_t, t, abs(x) // -x):
        if n > 0: printf("{r}", r=n + abs(t))
      t = _t
      n += abs(x)
    

    In general, if we consider all numbers with k or fewer digits, and a (non-zero) digit d, then the proportion of those numbers that contain the specified digit is:

    R(k) = 1 – (9^k – 1) / (10^k – 1)

    Which makes R an increasing series:

    0.111, 0.192, 0.271, 0.344, 0.469, 0.522, 0.570, 0.613, 0.651, …

    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.

    R crosses 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” digit d.

    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 R for each “special” digit. The horizontal scale is logarithmic (as indicated on the axes for d=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):

    d=1:
    (1) 2
    (2) 16, 24
    (3) 160, 270, 272
    (4) 1456, 3398, 3418, 3420, 3422
    (5) 13120, 44686
    (6) 118096, 674934
    (7) 1062880

    d=2:
    (1) 2
    (4) 2914, 3150, 3152, 3238, 3398
    (5) 26242, 41558, 42280, 44686
    (6) 236194, 671784, 672136, 674910, 674912, 674926, 674934
    (7) 1299076, 1305158, 1305232, 1305406, 1325320, 1346694, 2125762

    d=3:
    (5) 39364, 41288, 41308, 41558, 43738, 44686
    (6) 354292, 671782, 671784, 673594, 674910
    (7) 3188644

    d=4:
    (6) 472390, 630226, 642976, 671782, 671784
    (7) 4251526

    d=5:
    (6) 590488, 630224, 630226, 656098, 671782
    (7) 5314408

    d=6:
    (7) 6377290

    d=7:
    (7) 7440172
    (8) 15633516, 15633518, 15707032, 16264012, 16271278, 16305300, 16307728, 16308426, 16308428, 16769914, 16935524, 16937584, 16938652, 16938718, 16938922, 16979866, 16980210, 17006110

    d=8:
    (7) 8503054
    (8) 15633516, 15633518, 15825130, 16263742, 16263826, 16264012, 16284400, 16305276, 16305278, 16305280, 16305300, 16888012, 16935524, 18068992

    d=9:
    (7) 9565936
    (8) 15588832, 15588934, 15633516, 15943228, 16263742, 16263988, 16264012, 16297522, 16305276, 16305298, 16305300, 19131874

    d=0:
    (8) 10761678, 14958584, 14960718, 14961734, 15013206, 15588832, 15590574, 15591958, 15591960, 15592032, 15592228, 15592230, 15603696, 15633494, 15633504, 15633516, 16076088, 16263742, 20327616

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

    2 → 1, 2
    3398 → 1, 2
    41558 → 2, 3
    44686 → 1, 2, 3
    630226 → 4, 5
    671782 → 3, 4, 5
    671784 → 2, 3, 4
    674910 → 2, 3
    674934 → 1, 2
    15588832 → 9, 0
    15633516 → 7, 8, 9, 0
    15633518 → 7, 8
    16263742 → 8, 9, 0
    16264012 → 7, 8, 9
    16305276 → 8, 9
    16305300 → 7, 8, 9
    16935524 → 7, 8

  2. Brian Gladman 17 October 2018 at 9:18 am

    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:

    #include <iostream>
    #include <strstream>
    #include <iomanip>
    
    int main(void)
    {
        // consider each 'special' digit
        for(int digit = 0; digit < 10; ++digit)
        {
            unsigned long long cnt_d(0), cnt_nd(0), oc(0);
            std::cout << "\n\ndigit: " << digit;
    
            // for numbers lower than the (known) maximum necessary 
            for(unsigned long long nbr = 1; nbr < 21000000; ++nbr)
            {
                unsigned long long t = nbr;
                bool has_digit = false;
                // does this number contain the special digit     
                while(!has_digit && t > 0)
                {
                    has_digit |= (t % 10 == digit);
                    t /= 10;
                }
                // increment the 'has' or 'not have' counts accordingly  
                if(has_digit)
                    cnt_d += 1;
                else
                    cnt_nd += 1;
                // output numberss where the counts are the same
                if(cnt_d == cnt_nd)
                {
                    if(oc % 4 == 0)
                        std::cout << std::endl;
                    oc += 1;
                    std::cout << std::setw(10) << nbr ;
                }
            }
        }
        std::cout << "\n\n";
    }
    

Leave a Comment

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: