Enigmatic Code

Programming Enigma Puzzles

Enigma 476: A curious question

From New Scientist #1627, 25th August 1988 [link]

Kugelbaum wandered into a history lecture by mistake and, almost as quickly, but not by mistake, wandered out again. “1210 may well have been a dull year,” he said to himself, “but it’s an interesting number. The first digit gives the number of 0s in it, the next the number of 1s in it, the next the number 2s in it and so on, quite consistently, right up to the very last digit. And there are other such numbers too, such as 2020 and 3211000! Curiously, I can’t find one with six digits, though.”

As he sought vainly the room where he was to give his lecture on number theory he amused himself by calculating all the numbers having this property. “I wonder,” he remarked as he looked into broom cupboard, “if one were to take all the numbers having this property and add them together, what the result would be?”

What is the sum of all the numbers having the property that their first digit gives the number of 0s in the number, the next the number of 1s in the number, the next the number of 2s in the number and so on, consistently right through to and including the last digit of the number?

(Since 10, 11, 12 and so on are not digits, any such number containing more than 10 digits must have zeros in its 11th place and any other places after this).

Note: The original puzzle statement gave 211000 as an example, not 3211000.

[enigma476]

One response to “Enigma 476: A curious question

  1. Jim Randell 26 November 2018 at 9:43 am

    [See also: Enigma 163, Enigma 1143, Enigma 298]

    The autobiographical numbers are also known as the curious numbers, hence the title of the puzzle.

    I wrote some code to generate autobiographical sequences, which is a sequence where the element at index n counts the total number of occurrences of the element n in the entire sequence.

    An autobiographical sequence represents an autobiographical number (in base 10), if all the elements have values that represent digits (i.e. are 0 – 9), and any element at an index higher than 9 is zero.

    As 9 is the largest value we can have at element 0, and any elements beyond index 9 must be zero, so all decimal autobiographical numbers must have fewer than 20 digits.

    This Python 3 program generates autobiographical sequences and totals the ones that correspond to decimal autobiographical numbers.

    It runs in 739ms.

    Run: [ @repl.it ]

    from enigma import irange, nconcat, arg, printf
    
    base = arg(10, 0, int)
    printf("[base = {base}]")
    
    # generate autobiographical sequences
    def _generate(a, m, s=[], k=0):
      if m < 0: return
      if s == a[:k]: yield s
      for i in irange(a[k], m):
        _s = s + [i]
        if i > k or a[i] != _s[i]:
          yield from _generate(a[:i] + [a[i] + 1] + a[i + 1:], m - i, _s, k + 1)
    
    # generate autobiographical sequences up to length n
    generate = lambda n: _generate([0] * (n + 1), n)
    
    # check a sequence is autobiographical
    def is_autobiographical(s):
      return all(x == s.count(i) for (i, x) in enumerate(s))
    
    # record totals
    t = 0
    for s in generate(2 * base - 1):
      assert is_autobiographical(s)
      if s and all(x < (base if i < base else 1) for (i, x) in enumerate(s)):
        n = nconcat(s, base=base)
        t += n
        printf("{s} -> {n}")
    printf("total = {t}")
    

    Solution: The total of all such numbers is 10109876341430.

    The full list of decimal autobiographical numbers is:

              1210
              2020
             21200
           3211000
          42101000
         521001000
        6210001000
       72100001000
      821000001000
     9210000001000 +
    --------------
    10109876341430

    It turns out that the only autobiographical sequences with length less than 7 are:

    ()
    (1, 2, 1, 0)
    (2, 0, 2, 0)
    (2, 1, 2, 0, 0)

    and for k ≥ 7 there is one autobiographical sequence of length k:

    (k – 4, 2, 1, … , 1, …)

    where the floating 1 is at index k – 4 and the remaining elements are 0.

    We can write a routine that uses this information to generate autobiographical sequences much faster than my original program.

    See: [ OEIS A138480 ] [ https://en.wikipedia.org/wiki/Self-descriptive_number ]

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: