Teaser 3078: Digital daisy-chains
From The Sunday Times, 19th September 2021 [link] [link]
The number 798 is a “digital daisy-chain”; i.e., if you spell out each of its digits as a word, then the last letter of each digit is the first letter of the next. Furthermore, the number 182 is a “looped” digital daisy-chain because, in addition, the last letter of its last digit is the first letter of its first digit.
I have written down a large looped digital daisy-chain (with fewer than a thousand digits!). The total of its digits is itself a digital daisy-chain.
What is that total?
[teaser3078]
Frits, and 
GeoffR are discussing. 
S2T2 
Jim Randell 5:14 pm on 17 September 2021 Permalink |
When forming a loop the individual “links” must be “821” or “83”, and both of these have a digit sum of 11.
So the digit sum of any loop is a multiple of 11, and we just need to find a multiple of 11 that forms a chain.
The shortest link is length 2, so we only need to consider loops with up to 499 links, i.e. a total of 5489.
This Python program runs in 51ms.
Run: [ @replit ]
from enigma import irange, int2words, nsplit, tuples, printf # digits as words words = list(int2words(d) for d in irange(0, 9)) # does a number form a chain? is_chain = lambda n: all(words[x][-1] == words[y][0] for (x, y) in tuples(nsplit(n), 2)) # look for viable digit sums for loops for n in irange(1, 499): t = 11 * n if is_chain(t): printf("digit sum = {t}")Solution: The total of the digits in the loop is 583.
The shortest loop would be “83” repeated 53 times (= 106 digits), and we can use “821” instead in any of the links giving us loops of up to 159 digits.
The next highest possible sum would be 8382, which would require 762 links, so the loops would have between 1524 and 2286 digits.
LikeLike
Jim Randell 10:34 pm on 18 September 2021 Permalink |
As suggested by Frits below, it is faster to generate possible “chain” numbers, and look for those that are divisible by 11 (although I separated these conditions out, rather than interleaving them).
Run: [ @replit ]
from enigma import irange, int2words, group, subsets, unpack, div, printf # digits as words digits = irange(0, 9) words = list(int2words(d) for d in digits) # adjacency map for next digit adj = group( subsets(digits, size=2, select="M"), st=unpack(lambda x, y: words[x][-1] == words[y][0]), by=unpack(lambda x, y: x), f=unpack(lambda x, y: y), ) # generate chain numbers less than M def chains(M): ss = list(digits) while ss: n = ss.pop(0) yield n if n: # expand the chain for d in adj.get(n % 10, ()): n_ = n * 10 + d if n_ < M: ss.append(n_) # look for possible chain numbers ... for t in chains(500 * 11): # that are a multiple of 11 n = div(t, 11) if n: printf("digit sum = {t}")LikeLike
GeoffR 9:39 pm on 17 September 2021 Permalink |
A programme with a similar basis to Jim’s solution.
# Using Jim's number range/step # Two digit numbers are 11, 22, 33, 44, 55, 66, 77, 88, 99 # They cannot be digital daisy chains as last letter # of first word is not the starting letter of second word from enigma import nsplit # Dictionary to look up words from digits DN = {0:'zero', 1:'one', 2:'two', 3:'three', 4:'four', 5:'five', 6:'six', 7:'seven', 8:'eight', 9: 'nine'} for n in range(110, 5500, 11): # check three digit numbers if 100 < n < 1000: d1, d2, d3 = nsplit(n) # allocate words to digits w1 = DN[d1] w2 = DN[d2] w3 = DN[d3] # check last letter of one word is same # as first letter of next word if w1[-1] == w2[0] and w2[-1] == w3[0]: print(f"Total is {n}.") # check four digit numbers if 1000 < n < 5500: d1, d2, d3, d4 = nsplit(n) # allocate words to digits w1 = DN[d1] w2 = DN[d2] w3 = DN[d3] w4 = DN[d4] # check last letter of one word is same # as first letter of next word if w1[-1] == w2[0] and w2[-1] == w3[0] \ and w3[-1] == w4[0]: print(f"Total is {n}.")LikeLike
GeoffR 12:32 pm on 18 September 2021 Permalink |
I did further work on digital daisy chains, finding 2, 3, 4 and 5-digit examples.
Of the values found, five numbers were of the looped digital chain type i.e. 38, 83, 182, 218 and 821, with their digits summing to eleven.
from itertools import permutations W = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine'] for p in permutations(W, 2): w1, w2 = p if w1 == 'zero': continue if w1[-1] == w2[0]: print(w1, w2) # 18, 21, 38, 58, 79, 82, 83, 98 print(); print() for p in permutations(W, 3): w1, w2, w3 = p if w1 == 'zero': continue if w1[-1] == w2[0] and w2[-1] == w3[0]: print(w1, w2, w3) # 182, 183, 218, 382, 582, 583, 798, 821, 982, 983 # There were also 6 no. 4-digit digital daisy chains # i.e. 2183, 3821, 5821, 7982, 7983, 9821 # A 5-digit digital daisy chain number was found i.e. 79821LikeLike
Frits 7:50 pm on 18 September 2021 Permalink |
Doing it a bit differently and not using modulo.
dw = 'zero one two three four five six seven eight nine'.split() # credit: B. Gladman links = set((i, j) for j in range(10) for i in range(10) if dw[i][-1] == dw[j][0]) # look for chains of 3 or 4 digits with the alternating sum divisible by 11 def chain(k, lst, rs=[], asum=0): if k == 5: return # total is fewer than 5490 else: if k > 2 and asum in {-11, 0, 11}: t = int("".join(str(w) for w in (rs[0] + [y for x, y in rs[1:]]))) if t <= 5489: print("total =", t) for x, y in lst: if not rs or x == rs[-1][-1]: # total must be a multiple of 11 # use alternating sum for testing divisibility by 11 new = x - y if k == 1 else (-1)**k * y chain(k + 1, lst, rs + [[x, y]], asum + new) # look for daisy-chain total chain(1, links)LikeLike