Sunday Times Teaser 2592 – Inventive Inventories

by Simon Massarella

Published: 27 May 2012 (link)

It is known that there is just one 10-figure number that is “self-counting” in the sense that its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it and the tenth digit equalling the number of 0s in it.

Similarly, a 9-figure number is “self-counting” if its first digit equals the number of 1s in it, the second digit equals the number of 2s in it, and so on, with the ninth digit equalling the number of 9s in it (and with the 0s remaining uncounted).

(a) What is the 10-figure self-counting number?
(b) What is the highest 9-figure self-counting number?

One Comment Leave one →

Brian Gladman permalink

This requires quite a bit of programming to obtain a reasonably fast solution. I tried several approaches, some of which wer very fast but didn’t guarantee to reach a solution. The solution here is reasonably fast and provides a more general solution for finding “self-describing” numbers. There are two sequences of such numbers, one in which successive digits from the left count ‘0’s, ‘1’s … and another in which they count ‘1’s, ‘2’s … This program can find both types.


from functools import reduce
from itertools import permutations

# generate the partitions of an integer
def partitions(n):
  k, y, a = 1, n - 1, [0 for i in range(n + 1)]
  while k != 0:
    k, x = k - 1, a[k - 1] + 1
    while 2 * x <= y:
      y, a[k], k = y - x, x, k + 1
    l = k + 1
    while x <= y:
      a[k], a[l] = x, y
      x, y = x + 1, y - 1
    y, a[k] = x + y - 1, x + y
    yield a[:k + 1]

# generate the unique permutations of items
# (items must be sorted on input)
def unique_permutations(items): 
  def perm(items, count): 
    if not count:
      yield tuple()
    else:
      prev_item = object() 
      for i, item in enumerate(items): 
        if item != prev_item: 
          for p in perm(items[:i] + items[i + 1:], count - 1): 
            yield (item,) + p 
        prev_item = item 
  yield from perm(items, len(items)) 

# Generate self describing sequences in which seq[i] gives the
# number of times the value <i> occurs in the sequence. The
# value 'off' specifies the value that is counted bt the first
# item in the sequence, either 0 (default) or 1.
def sd_nbr(n, off=0):
  # we don't count zeros if the first digit counts '1's and the
  # length of the sequence is less than 10
  cr = n - 1 if off and n < 10 else n
  # try different numbers of zeros in the number
  for zeros in range(0 if off else 1, n):
    # the number of non-zero digits in the number is its length
    # less the number of zeros - the counts of the number of '1's,
    # '2's ... are hence partitions of this number
    for p in partitions(n - zeros):
      # add zeros to the partition to make it the right length 
      # and check permutations to find one that is self describing
      for q in unique_permutations([0] * (n - 1 - len(p)) + p):
        # add the zero count at the start if the first digit counts zeros 
        # or at the end if it counts ones (and we are counting zeros)
        counts = ((zeros,) + q) if not off else q if n < 10 else (q + (zeros,))
        # check that the sequence is self describing
        cc = tuple(counts.count((i + off) % n) for i in range(cr))
        if cc == counts:
          yield counts

# output 'self describing' numbers for numbers where the count
# starts with the first (left hand) digit counting '0's and '1's
for f in (0, 1):
  print("nFirst digit counts '{}'s:".format(f))
  for n in range(1, 11):
    vals = tuple((reduce(lambda x, y: 10 * x + y, r, 0) for r in sd_nbr(n, f)))
    if vals:
      if len(vals) == 1:
        vals, = vals
      fs = "{:2} digit 'self counting' number(s): {}"
      print(fs.format(n, vals))

from functools import reduce

from itertools import permutations

# generate the partitions of an integer

def partitions(n):

k, y, a = 1, n - 1, [0 for i in range(n + 1)]

while k != 0:

k, x = k - 1, a[k - 1] + 1

while 2 * x <= y:

y, a[k], k = y - x, x, k + 1

l = k + 1

while x <= y:

a[k], a[l] = x, y

x, y = x + 1, y - 1

y, a[k] = x + y - 1, x + y

yield a[:k + 1]

# generate the unique permutations of items

# (items must be sorted on input)

def unique_permutations(items):

def perm(items, count):

if not count:

yield tuple()

else:

prev_item = object()

for i, item in enumerate(items):

if item != prev_item:

for p in perm(items[:i] + items[i + 1:], count - 1):

yield (item,) + p

prev_item = item

yield from perm(items, len(items))

# Generate self describing sequences in which seq[i] gives the

# number of times the value <i> occurs in the sequence. The

# value 'off' specifies the value that is counted bt the first

# item in the sequence, either 0 (default) or 1.

def sd_nbr(n, off=0):

# we don't count zeros if the first digit counts '1's and the

# length of the sequence is less than 10

cr = n - 1 if off and n < 10 else n

# try different numbers of zeros in the number

for zeros in range(0 if off else 1, n):

# the number of non-zero digits in the number is its length

# less the number of zeros - the counts of the number of '1's,

# '2's ... are hence partitions of this number

for p in partitions(n - zeros):

# add zeros to the partition to make it the right length

# and check permutations to find one that is self describing

for q in unique_permutations([0] * (n - 1 - len(p)) + p):

# add the zero count at the start if the first digit counts zeros

# or at the end if it counts ones (and we are counting zeros)

counts = ((zeros,) + q) if not off else q if n < 10 else (q + (zeros,))

# check that the sequence is self describing

cc = tuple(counts.count((i + off) % n) for i in range(cr))

if cc == counts:

yield counts

# output 'self describing' numbers for numbers where the count

# starts with the first (left hand) digit counting '0's and '1's

for f in (0, 1):

print("nFirst digit counts '{}'s:".format(f))

for n in range(1, 11):

vals = tuple((reduce(lambda x, y: 10 * x + y, r, 0) for r in sd_nbr(n, f)))

if vals:

if len(vals) == 1:

vals, = vals

fs = "{:2} digit 'self counting' number(s): {}"

print(fs.format(n, vals))

Sunday Times Teaser 2592 – Inventive Inventories

by Simon Massarella

Published: 27 May 2012 (link)

Leave a Reply Cancel reply

Recent Posts

Recent Comments

Archives

Categories

Meta