Enigmatic Code

Programming Enigma Puzzles

Enigma 631: Fidget digit

From New Scientist #1785, 7th September 1991 [link]

My niece (whose age is a two-figure number) is very good at arithmetic, and to keep her occupied on a recent train journey I asked her to find a number with all its digits different and with the sum of its digits a multiple (more than one times) of her age.

She wrote down a list of lots of number with both those properties. So I then asked her to add 1 to each of her numbers, and to pick out from the new list each number which still had all its digits different and with the sum of its digits equal to a multiple (again, more than one times) of her age next birthday.

There were still quite a few numbers in this new list which had these properties. So I asked her to find one of them which, when multiplied by her age, gave an answer which still had all its digits different — which she did!

How old is she?

[enigma631]

6 responses to “Enigma 631: Fidget digit

  1. Jim Randell 5 July 2021 at 10:01 am

    If we have a number n that has a digit sum of k. Then the digit sum of (n + 1) will be (k + 1) unless the final digit of n is 9. And if it is, the digit sum will be (k – 9 + 1) = (k – 8).

    This program looks at sets of digits (as any number formed from those digits in some order will have the same digit sum), that have a digit sum that is a proper multiple of a potential 2-digit age.

    And then selects sets that potentially give numbers that, when incremented, will have a digit sum that is a proper multiple of the 2-digit age, also incremented.

    Once a potential set is identified we construct corresponding numbers that could appear on the first list (although this will not give an exhaustive list of possibilities for the first list), and from that list derives corresponding numbers that could appear on the second list, and then the third list.

    If the third list we get is non-empty, then we have found a solution.

    This Python program runs in 538ms.

    Run: [ @replit ]

    from enigma import irange, subsets, group, divisors_pairs, div, nconcat, is_duplicate, dsum, printf
    
    digits = set(irange(0, 9))
    
    # group collections of 3-9 distinct digits by digit sum
    d = group(subsets(digits, min_size=3, max_size=9), by=sum)
    
    # consider possible collections
    for (k, vs) in d.items():
      for (a, b) in divisors_pairs(k, every=1):
        if a < 10: continue
        if a > 99: break
        if b == 1: continue
    
        # digit sum of n + 1 is either (k + 1) or (k - 8)
        m1 = div(k + 1, a + 1)
        m2 = (None if k < 8 else div(k - 8, a + 1))
        if (m1 is None or m1 < 2) and (m2 is None or m2 < 2): continue
    
        printf("[age={a}; k={k}]")
    
        # list 1: numbers with distinct digits that have a digit sum
        # that is a proper multiple of a
        ns1 = list()
        for ds in vs:
          for s in subsets(ds, size=len, select="P"):
            if s[0] == 0: continue
            ns1.append(nconcat(s))
        printf("[-> {n} numbers in first list]", n=len(ns1))
    
        # list 2: numbers from ns1, incremented, with distinct digits
        # that have a digit sum that is a proper multiple of (a + 1)
        ns2 = list()
        for n in ns1:
          n += 1
          if is_duplicate(n): continue
          m = div(dsum(n), a + 1)
          if m is not None and m > 1:
            ns2.append(n)
        printf("[-> {n} numbers in second list]", n=len(ns2))
    
        # list 3: numbers from ns2, which when multiplied by a still
        # have distinct digits
        ns3 = list()
        for n in ns2:
          n *= a
          if is_duplicate(n): continue
          ns3.append(n)
        printf("[-> {n} numbers in third list]", n=len(ns3))
    
        # output solution
        if ns3:
          printf("age = {a} -> {ns3}")
    

    Solution: The niece’s age is 11.


    For instance the final number could be: 2679453810 (which has all its digits different).

    And: 2679453810 = 11 × 243586710.

    So: 243586710 is a number on the second list. It has all its digits different, and has a digit sum of 36 = 3 × 12, where the niece will be 12 on her next birthday.

    The corresponding number on the first list is: 243586709, which has all its digits different, and a digit sum of 44 = 4 × 11, where the niece is currently 11.

    (And of course any valid rearrangement of the digits of 243586709 will give a number that could appear on the first list).

    In fact, there are 22 possible numbers that the niece could have given:

    2679453810, 2836497510, 2846397510, 2946387510, 3768245910, 3769245810, 3769542810,
    3879462510, 4263879510, 4679253810, 4825397610, 4976253810, 5263789410, 5264987310,
    5362789410, 6295834710, 6427593810, 6957342810, 7462985310, 8234957610, 8342659710,
    9542876310

    The second list could have up to 5,760 numbers on it, and the first list could have up to 533,448 numbers on it.

    • Frits 6 July 2021 at 6:10 pm

      I am busy with a SubstitutedExpression solver program for this problem, I am not sure if I can make it fast enough to finish within a minute. I noticed you can limit her age to 10-22 as the sum of digits is 45 at most (if a > 22: break).

  2. Brian Gladman 6 July 2021 at 10:49 pm

    I have posted a solution to this enigma puzzle here.

  3. Pingback: New Scientist Enigma 631 – Fidget Digit | PuzzlingInPython

  4. Frits 7 July 2021 at 1:25 pm

    Only one age is possible with digital sum of first list number equal to 44 (age 10 is rejected).
    I have added code for this special situation.

    This Python program runs in approx 40ms.

    from enigma import SubstitutedExpression, dsum, div
    from collections import defaultdict
    
    d2i = defaultdict(set)  # dictionary of forbidden values
    
    exprs = []
    diffexp = []
    s2dvar = ""
    addexp = ""
    distinct= ""
    
    # choose F as RHS as H an I will have few values
    exprs.append("XY - sum([A, B, C, D, E, G, H, I]) % XY = F")
    exprs.append("len(set(str((ABCDEFGHI + 1) * XY))) == len(str((ABCDEFGHI + 1) * XY))")
    exprs.append("div(dsum(ABCDEFGHI + 1), XY + 1) > 1")
    exprs.append("div(dsum(ABCDEFGHI), XY) > 1")
    exprs.append("len(set(str(ABCDEFGHI))) == len(str(ABCDEFGHI))")
    exprs.append("len(set(str(ABCDEFGHI + 1))) == len(str(ABCDEFGHI + 1))")
    
    # inequality expressions
    diffexp.append("B != A or B == 0")
    diffexp.append("C not in set([A, B]) or C == 0")
    diffexp.append("D not in set([A, B, C]) or D == 0")
    diffexp.append("E not in set([A, B, C, D]) or E == 0")
    diffexp.append("F not in set([A, B, C, D, E]) or F == 0")
    diffexp.append("G not in set([A, B, C, D, E, F]) or G == 0")
    diffexp.append("H not in set([A, B, C, D, E, F, G]) or H == 0") 
    
    
    # determine valid ages
    xy = ""
    sum1l = []
    sum2l = []
    sumdl = []
    for a in range(10, 23):
      for k in range(2, 5):
        sumd = k * a
        sum1 = (sumd + 1)
        sum2 = (sumd - 8)
        d1 = div(sum1, (a + 1))
        d2 = div(sum2, (a + 1))
        if d1 in {None, 1} and d2 in {None, 1}: continue
    
        if d2 != None:
          # consider sum2
          # first list number must end on 9 
          # second list number must end on 0 
          # third list number must end on 0
          if a % 10 == 0: continue   # third list number will end on 00
          sum2l.append(sum2)
        else:
          sum1l.append(sum1)
        sumdl.append(sumd) 
            
        xy += str(a) + ","
    
    if len(xy) < 6:    # only one age possible    
      s2dvar += "X=" + xy[0] +", Y=" + xy[1] + ", "
    else:  
      exprs.append("XY in [" + xy[:-1] + "]")
      # age has range 10-22
      for k in [0, 3, 4, 5, 6, 7, 8, 9]:
        d2i[k].add("X")
    
    if len(sum1l) == 0 and len(sum2l):
      # first list number must end on 9 
      s2dvar += "I=9, "
      for k in "ABCDEFGH":
        d2i[9].add(k)
    
      # One entry with digital sum 44?
      if len(sum2l) == 1 and sumdl[0] == 44: 
        # first list number has 8 or 9 digits and may not contain 1
        for k in "ABCDEFGHI":
          d2i[1].add(k)
    
        # suppose first list number is abcdefgh9 (<a> may be zero)
        # second list number must end on
        # - 10 (abcdefg09 --> abcdefg10)
        #      first list number must have 9 digits
        # - x0 (abcdefg(x-1)9 --> abcdefgx0), x = 2...8
        #      missing digits in second list number are 1, x-1 and 9
        #      so first list number must have had 7 digits 
        #      ---- impossible if sumd = 44 ----
        # - 90 (abcdefg89 --> abcdefg90), 
        #      missing digits in second list number are 1 and 8
        #      so first list number must have had 8 digits (missing 0 and 1)
    
        # H must be 0 or 8
        for k in [2, 3, 4, 5, 6, 7, 9]:
          d2i[k].add("H")
    
        for k in "BCDEFGI":
          d2i[0].add(k)  
    
        # make first entry of the list
        distinct = "BCDEFGHI" if "I" not in s2dvar else "BCDEFGH"
     
    s2d = eval("dict(" + s2dvar[:-2] + ")")
    
    if not distinct:
      exprs += diffexp
    
    # the alphametic puzzle
    p = SubstitutedExpression(
      exprs,
      answer="XY, ABCDEFGHI, ABCDEFGHI + 1 , (ABCDEFGHI + 1) * XY",
      d2i=d2i,
      s2d=s2d,
      distinct=distinct,
      #reorder=0,
      verbose=0,
    )
    
    # collect answers
    answs = sorted(y for _, y in p.solve())
    
    if answs[0][0] == answs[-1][0]:
      print("age:", answs[0][0])
    else:
      print("no solution") 
    
    • Jim Randell 9 July 2021 at 6:01 pm

      Impressive speed for a solution using [[ SubstitutedExpression ]]. I made a run file that took 6m30s to execute.

      I stepped through your program in a debugger, and like the fact that if finds the 22 numbers on the third list (and their counterparts on the first two lists), even if it doesn’t display them.


      Analysing the potential digit sums (the first 20 lines of my program), tells us that there are only two potential situations:

      [1] age = 10; digit sum = 30; numbers on list 1 end in 9
      [2] age = 11; digit sum = 44; numbers on list 1 end in 9

      So it is not necessary to consider numbers on list 1, other than those that end in 9.

      And as you point out [1] is non-viable, as the numbers on list 2 must end in 0, and then the number on list 3 would end in 00.

      So this leaves [2] as the only possible source of solutions. Here’s my program modified to print the 22 numbers on the third list, and their counterparts on list 1 and 2:

      from enigma import irange, group, subsets, divisors_pairs, div, diff, nconcat, is_duplicate, printf
      
      digits = set(irange(0, 9))
      
      # group collections of 3-9 distinct digits by digit sum
      d = group(subsets(digits, min_size=3, max_size=9), by=sum)
      
      # consider possible collections
      for (k, vs) in d.items():
        for (a, b) in divisors_pairs(k, every=1):
          if a < 10: continue
          if a > 99: break
          if b == 1: continue
      
          # digit sum of n + 1 is either (k + 1) or (k - 8)
          m1 = div(k + 1, a + 1)
          m2 = (None if k < 8 else div(k - 8, a + 1))
      
          if not(m1 is None or m1 < 2):
            printf("[age={a}; k={k} -> (... ~9)]")
            # look for solutions with last digit other than 9
            assert False, "Not reached"
      
          if not(m2 is None or m2 < 2):
            printf("[age={a}; k={k} -> (... 9)]")    
            # can we have (... d 9) -> (... d+1 0)
            for ds in vs:
              if 9 not in ds: continue
              # find possible penultimate digits
              for d in ds:
                if d == 9 or d + 1 in ds: continue
                # permute the remaining digits
                for rs in subsets(diff(ds, (d, 9)), size=len, select="P"):
                  if rs[0] == 0: continue
                  # construct the numbers on each list
                  n1 = nconcat(rs + (d, 9))
                  n2 = n1 + 1
                  n3 = n2 * a
                  if is_duplicate(n3): continue
                  # output corresponding list numbers 
                  printf("age={a}: {n1} -> {n2} -> {n3}")
      

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: