Enigmatic Code

Programming Enigma Puzzles

Enigma 1030: Uncommonly different progressions

From New Scientist #2186, 15th May 1999

Certain 5-digit perfect squares can be formed by coupling a pair of smaller squares: a 1-digit square followed by a 4-digit square, or a 2-digit square followed by a 3-digit square, or a 4-digit square followed by a 1-digit square. A leading zero in front of the second square makes it ineligible; that means that 64009 can only be regarded as 80² followed by 3² (not at 8² followed by 3²) and squares such as 10000 are eliminated — so don’t waste time looking for a 3-digit square followed by a 2-digit square; it should be obvious that no such 5-digit square can exist.

Harry, Tom and I each chose three eligible 5-digit squares, and on each of our squares we multiplied the square roots of the pair of coupled smaller squares. We each found that our three products could be arranged to form an arithmetic progression; in addition the common difference of our three progressions could themselves be arranged to form another arithmetic progression whose common difference was different from that of any of the three previous progressions.

1. List in ascending order those 5-digit squares that were chosen by just one of us.
2. List in ascending order those eligible 5-digit squares that none of us chose.

[enigma1030]

One response to “Enigma 1030: Uncommonly different progressions

  1. Jim Randell 28 December 2018 at 7:36 am

    This Python program runs in 76ms.

    Run: [ @repl.it ]

    from collections import namedtuple, defaultdict
    from itertools import product, combinations
    from enigma import irange, join, sprintf, printf
    
    # record 1 to 5 digit squares (as strings)
    squares = defaultdict(dict)
    for i in irange(0, 316):
      s = str(i * i)
      squares[len(s)][s] = i
    
    # record (a, b, s, p) results
    # whare a:b is the square s and the root product is p
    S = namedtuple('S', 'a b s p')
    fmt = lambda x: sprintf("{x.a}:{x.b} ({x.p})")
    ss = list()
    for n in irange(1, 4):
      for ((a, ra), (b, rb)) in product(squares[n].items(), squares[5 - n].items()):
        s = a + b
        rs = squares[5].get(s, None)
        if rs is not None:
          p = ra * rb
          printf("[{a}:{b} = {s} = {rs}^2, p = {p}]")
          ss.append(S(a, b, s, p))
    
    # sort the results by p
    ss.sort(key=lambda s: s.p)
    
    # find three results that form an arithmentic progression by p
    P = namedtuple('P', 's d')
    ps = list()
    for (x, y, z) in combinations(ss, 3):
      d = y.p - x.p
      if not(d == z.p - y.p): continue
      printf("[{x} -> {y} -> {z}, diff={d}]", x=fmt(x), y=fmt(y), z=fmt(z))
      ps.append(P((x, y, z), d))
    
    # sort the results by d
    ps.sort(key=lambda p: p.d)
    
    # find three progressions that whose differences form a progression
    for (T, D, H) in combinations(ps, 3):
      d = D.d - T.d
      if not(d == H.d - D.d): continue
      # the common difference is not the difference of any constituent sequence
      if d in (T.d, D.d, H.d): continue
    
      printf("seqs: (diff={d})")
      for x in (T, D, H):
        printf(" [{xs}], diff={x.d}", xs=join(map(fmt, x.s), sep=" -> "))
    
      # count the occurrences of 5 digit squares in the solution
      r = dict((s.s, 0) for s in ss)
      for x in (T, D, H):
        for y in x.s:
          r[y.s] += 1
    
      # (1) squares in just one sequences
      q1 = sorted(k for (k, v) in r.items() if v == 1)
      printf("(1) {q1}", q1=join(q1, sep=", "))
    
      # (2) squares in none of the sequences
      q2 = sorted(k for (k, v) in r.items() if v == 0)
      printf("(2) {q2}", q2=join(q2, sep=", "))
      
      printf()
    

    Denoting the five digit square abcde with a colon indicating the split point (e.g. a:bcde, ab:cde, abcd:e).

    Solution: (1) The unique squares are: 16:900, 36:100, 6400:9; (2) The unused squares are: 49:729, 81:225.

    There are 8 different five digit squares we can construct, and we can form 4 sequences from them:

    [1] = (36:100, 1:5625, 4:2025) gives products of (60, 75, 90), common difference = 15.
    [2] = (36:100, 4:2025, 16:900) gives products of (60, 90, 120), common difference = 30.
    [3] = (1:5625, 16:900, 9:3025) gives products of (75, 120, 165), common difference = 45.
    [4] = (4:2025, 9:3025, 6400:9) gives products of (90, 165, 240), common difference = 75.

    The sequence of common differences of sequences [1], [3], [4] gives (15, 45, 75) a sequence with a common difference of 30 (which is the common difference of sequence [2]).

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: