Enigmatic Code

Programming Enigma Puzzles

Enigma 356: Counting house

From New Scientist #1505, 24th April 1986 [link]

“My fortune,” said the king to his vizier, “consists of a number of identical gold pieces. I remember their number by a set of peculiar numerical circumstances. I do not speak their number openly, as there are spies and eavesdroppers at court. Instead I shall tell you indirectly.”

“My fortune cannot be divided equally among my sons without splitting gold pieces. Nor could it be so divisible, unless the number of my sons were to run into thousands. My three youngest sons live in the palace, and of the other 15 some have perished in the late wars against the heathen.”

“Now the number of pieces of gold in my fortune has the following curious property: if one multiplies it by the number of my sons living, one obtained a 10-digit number in which all the digits from 0 to 9 appear, with one exception. If any number of digits be cut off the right of this number, the remaining digits form a number which is divisible without remainder by the number of digits cut off. You have a reputation of being a calculator, and so will know the number I mean, and thus the number of gold pieces in my counting house.”

The vizier bowed and reached for his pen case and parchment.

How many sons and how many gold pieces did the king possess?

[enigma356]

Advertisements

2 responses to “Enigma 356: Counting house

  1. Jim Randell 5 August 2016 at 7:56 am

    This Python 3 program runs in 165ms.

    from enigma import irange, nsplit, factor, printf
    
    # generate 10 digit numbers: abcdefghij, such that:
    # 9 | a; 8 | ab; 7 | abc; ..., 2 | abcdefgh; 1 | abcdefghi
    def generate(n=0, k=9):
      # are we done
      if k == 1:
        n *= 100
        yield from irange(n, n + 99)
      else:
        # add the next digit
        for d in irange(0, 9):
          n1 = 10 * n + d
          if n1 > 0 and n1 % k == 0:
            yield from generate(n1, k - 1)
    
    # consider possible 10 digit numbers, N
    for N in generate():
      # check it is composed of 9 different digits
      if len(set(nsplit(N))) != 9: continue
      # we need a number with at least two factors
      fs = list(factor(N))
      if len(fs) < 2: continue
      # one factor between 4 and 16 (inclusive)
      if not(3 < fs[0] < 17): continue
      # and the rest more than 1000
      if not(fs[1] > 999): continue
      # so the number of sons and coins is...
      sons = fs[0]
      coins = N // sons 
      printf("N={N} {fs}, sons = {sons}, coins = {coins}")
    

    Solution: The king had 7 sons and 1,380,075,491 gold coins.

    That’s quite a lot of gold coins.

    The ten digit number is 9,660,528,437 which factorises as 7 × 3253 × 424247.

  2. Brian Gladman 5 August 2016 at 9:22 am
    from number_theory import factors
    
    # compile the number (nbr) progressively from the most significant
    # digit downwards; <nbr> is the number, <seq> is its digits, <div>
    # is the divisor in this step and <dup> is true if the number has
    # a duplicate digit
    def compile(nbr, div, dup, seq):
      # have we finsished (with nine digits) 
      if not div:
        # if we have a duplicate digit the tenth digit is 
        # one of those not used so far; otherwise the
        # tenth digit is an existing digit
        t = set(range(10)).difference(seq) if dup else seq
        for i in t:
          yield 10 * nbr + i
      else:
        # add the next digit on the right, ensuring that 
        # the most significant digit is not zero
        for n in range(0 if nbr else 1, 10):
          # check if we are allowed to use a duplicate
          if not (dup and n in seq):
            nn = 10 * nbr + n
            # check that the new number is divisible by the current divisor
            if not nn % div:
              yield from compile(nn, div - 1, dup | (n in seq), seq + [n])
    
    # find possible ten digit numbers of the required form
    for n in compile(0, 9, False, []):
      # we need one factor (for the number of sons) that is
      # greater than 3 and less than 18 with no other factors
      # below the thousands
      f = list(factors(n))
      if len(f) > 1 and 3 < f[0] < 18 and f[1] >= 1000:
        fs = 'The king has {} sons and {} pieces of gold.'
        print(fs.format(f[0], n // f[0]))
    

    This uses my number theory library that is available here

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 )

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

%d bloggers like this: