Enigmatic Code

Programming Enigma Puzzles

Enigma 1289: Alternate chain

From New Scientist #2447, 15th May 2004 [link]

I have constructed a cyclical chain of 3-digit numbers, where each number starts with the digit (which is never 0) that was the last digit of the previous number in the chain, and the numbers in the chain are alternately perfect squares and triangular numbers.

The chain consist of as many numbers as is possible, consistent with the requirements outlined above and the stipulation that no number may appear in it more than once.

How many numbers are there in the chain?

Note: I am still waiting for a phone line to be connected at my new house, so I only have sporadic access to the internet at the moment.

[enigma1289]

Advertisements

4 responses to “Enigma 1289: Alternate chain

  1. Jim Randell 4 October 2014 at 1:39 pm

    This Python code runs in 239ms.

    from collections import defaultdict
    from itertools import count
    from enigma import T, Accumulator, flatten, printf
    
    # make a list of 3-digit numbers (as strings)
    # don't allow numbers that end in zero
    # record them by their leading digit
    def make_list(fn, s):
      r = defaultdict(list)
      for i in count(s):
        n = str(fn(i))
        if len(n) > 3: return r
        if n[-1] != '0': r[n[0]].append(n)
    
    # squares
    squares = make_list(lambda x: x * x, 10)
    
    # triangular numbers
    tris = make_list(T, 14)
    
    # extend a chain alternately from As and Bs
    # accumulating loops by length in r
    def solve(chain, As, Bs, r):
      # what digit is at the end of the chain?
      d = chain[-1][-1]
      # are we a loop?
      if d == chain[0][0]:
        # we're only interested in even length chains
        n = len(chain)
        if n % 2 == 0:
          r.accumulate_data(n, chain)
      # try to extend the chain (from As)
      for x in As[d]:
        if x not in chain:
          solve(chain + [x], Bs, As, r)
      
    r = Accumulator(fn=max)
    # start with a square...
    for x in flatten(squares.values()):
      # ... and then a tri, and so on...
      solve([x], tris, squares, r)
    printf("max chain length = {r.value} {chain}", chain=list(map(int, r.data)))
    

    Solution: There are 14 numbers in a maximal length chain.

    Here’s an example chain of length 14: (121, 105, 529, 903, 324, 406, 676, 666, 625, 528, 841, 153, 361, 171).

    Because the chain must form a closed loop of alternating squares and triangular numbers the solution can only be a chain with even length.

    But we can find longer sequences with alternating squares and triangular numbers that are of odd length, but when formed into a closed loop two numbers of the same type will be next to each other.

    Here’s an example chain of length 17: (561, 144, 496, 676, 666, 625, 528, 841, 171, 121, 153, 361, 105, 529, 903, 324, 465).

    When formed into a loop 561 = T(33) and 465 = T(30) will be adjacent.

  2. Julian Gray 8 October 2014 at 3:39 pm

    I wish to challenge the meaning of “cyclical chain”. To me it means following a predetermined cycle (i.e. alternate squares and triangular numbers), not that it has to be “circular”. Anyway, I got a chain 19 numbers long, beginning and ending with triangular numbers – 225 – 528 – 841 – 171 – 121 – 105 – 529 – 946 – 676 – 666 – 625 – 561 – 169 – 903 – 361 – 153 – 324 – 465 – 576. Happy days! (8 October 2014)

    • Jim Randell 8 October 2014 at 7:22 pm

      The published solution was that there were 14 numbers in the chain, so I think the setter was intending the numbers to be formed into a circle. They probably could have been a bit more explicit in the problem statement.

      If you relax the conditions so you’re just looking for an alternating sequence (that doesn’t have to form a closed loop) then 19 is indeed the maximal length you can achieve.

  3. Brian Gladman 8 October 2014 at 6:37 pm
    from collections import defaultdict
    
    # for three digit triangular numbers that 
    # can follow three digit squares
    f_sq = defaultdict(list)
    # for three digit squares that can follow
    # three digit triangular numbers
    f_tr = defaultdict(list)
    
    for s in (x * x for x in range(10, 32)):
      for t in (x * (x + 1) // 2 for x in range(14, 45)):
        if s % 10 == t // 100:
          f_sq[s].append(t)
        if t % 10 == s // 100:
          f_tr[t].append(s)
    
    # for the maximum length sequence
    lln, ssq = 0, ()
    
    # add a number to the sequence seq from dictionary s1 where seq 
    # ends with a number that is in dictionary s2
    def add(seq, s1, s2):
      global lln, ssq
    
      l = len(seq)
      # save the sequence if its length is even, it forms a chain
      # and it is longer than the longest so far
      if l % 2 == 0 and seq[0] // 100  == seq[-1] % 10 and l > lln:
        lln, ssq = l, tuple(seq)
    
      # try to add one from the first sequence (s1) above
      for s in s1[seq[-1]]:
        if s not in seq and s > seq[0]:
          # try to add another from the second sequence (by 
          # swapping the two sequences)
          add(seq + [s], s2, s1)
    
    # start with a triangular number
    for s in sum(f_sq.values(), []):
      add([s], f_tr, f_sq)
    # output the maximum length sequence
    print(lln, ssq)
    

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: