Enigmatic Code

Programming Enigma Puzzles

Enigma 1068: Triangular Fibonacci squares

From New Scientist #2224, 5th February 2000 [link]

Harry, Tom and I were trying to find a 3-digit perfect square, a 3-digit triangular number and a 3-digit Fibonacci number that between them used nine different digits. (Triangular numbers are those that fit the formula n(n+1)/2; in the Fibonacci sequence the first two terms are 1 and 1, and every succeeding term is the sum of the previous two terms). We each found a valid solution and we each created a second valid solution by retaining two of the numbers of our first solution but changing the other one. Our six solutions were all different.

List in ascending order the numbers in the solution that none of us found.

[enigma1068]

3 responses to “Enigma 1068: Triangular Fibonacci squares

  1. Jim Randell 2 April 2018 at 7:30 am

    (See also: Enigma 1153).

    This Python program runs in 81ms.

    Run: [ @repl.it ]

    from itertools import product, combinations
    from enigma import irange, is_duplicate, T, fib, printf
    
    # select three digit numbers with non-repeating digits
    # from iterator <i> of increasing non-negative integers
    def numbers(i):
      s = set()
      for n in i:
        if n < 100: continue
        if n > 999: break
        if is_duplicate(n): continue
        s.add(n)
      return s
    
    # candidate square numbers
    squares = numbers(i * i for i in irange(10, 31))
    
    # candidate triangular numbers
    tris = numbers(T(i) for i in irange(13, 44))
    
    # candidate fibonacci numbers
    fibs = numbers(fib(1, 1))
    
    # find sets that contain 9 different digits
    ss = sorted(t for t in product(squares, tris, fibs) if not is_duplicate(*t))
    
    # make the relation (A, B) if A and B share exactly 2 numbers
    r = set((A, B) for (A, B) in combinations(ss, 2) if len(set(A).intersection(set(B))) == 2)
    
    # choose three sets for Tom, Dick, Harry
    for (T, D, H) in combinations(r, 3):
      # check the six sets are different
      s = set().union(T, D, H)
      if len(s) != 6: continue
      # find solutions that were not discovered by T, D, H
      for u in set(ss).difference(s):
        printf("undiscovered = {u}")
    

    Solution: The set of numbers that was not found was: 378, 529, 610.

    378 = T(27)
    529 = 23²
    610 = F(14)

  2. geoffrounce 2 April 2018 at 10:19 am

    Multiple output configuration in MiniZinc found the seven sets of numbers, one of which could be identified as the required solution – although not a rigorous programme solution.

    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 0..9:A;  var 0..9:B;  var 0..9:C;  var 0..9:D;
    var 0..9:E;  var 0..9:F;  var 0..9:G;  var 0..9:H;   
    var 0..9:I;  var 0..9:J;
    
    constraint all_different([A,B,C,D,E,F,G,H,I,J])
    /\ A > 0 /\ D > 0 /\ G > 0;
    
    var 100..999: ABC = 100*A + 10*B + C;  % 3-digit square
    var 100..999: DEF = 100*D + 10*E + F;  % 3-digit triangular number
    var 100..999: GHI = 100*G + 10*H + I;  % 3-digit Fibonnacci number
    
    set of int: tri3 = { n * (n+1) div 2 | n in 14..44 };
    
    set of int: sq3 = {n*n | n in 10..31};  
    
    set of int: fib3 = {144,233,377,610,987};
    
    constraint ABC in sq3 /\ DEF in tri3 /\ GHI in fib3;
    
    solve satisfy;
    
    output [ show(ABC) ++ "  " ++ show(DEF) ++ "  " ++ show(GHI) ];
    
    % 784  253  610  << set 1  (784 and 610 the same)
    % ----------
    % 784  325  610  << set 1  (ditto)
    % ----------
    % 729  435  610  << set 2  (435 and 610 the same)
    % ----------
    % 289  435  610  << set 2  (ditto)
    % ----------
    % 529  378  610  << Solution not found by Tom, Dick or Harry
    % ----------
    % 324  105  987  << set 3  (324 and 987 the same)
    % ----------
    % 324  561  987  << set 3  (ditto)
    % ----------
    % ==========
    % Finished in 318msec
    
    
  3. Brian Gladman 2 April 2018 at 9:00 pm
    from itertools import combinations, permutations, product
    
    # pair up <n> triples from <seq> in such a way that each pair
    # has two values in common and the remaining two values are
    # different; return the pairs and any unpaired triples 
    def pairs(n, seq, ps=[]):
      # if we have finished ...
      if not n:
        # return the list of paired triples and the remaining 
        # unpaired triples 
        yield ps, seq
      else:
        # pick two triples
        for a, b in combinations(seq, 2):
          # consider possible pairs of different values, one 
          # from each triple
          for a1, b1 in product(a, b):
            # look for two different values with the remaining
            # values in the two triples the same
            if a1 != b1 and set(a) - {a1} == set(b) - {b1}:
              ns = tuple(s for s in seq if s not in {a, b})
              # continue to make the next pairing
              yield from pairs(n - 1, ns, ps + [(a, b)])
    
    # return true if a three digit number has three different digits
    def f3d(x):
      return len(set(str(x))) == 3
    
    # three digit squares with three different digits
    sqs = filter(f3d,  (x * x for x in range(10, 32)))
    # three digit triangular numbers with three different digits
    trs = filter(f3d, (x * (x + 1) // 2 for x in range(14, 45)))
    # three digit Fibonacci numbers with three different digits
    fbs = []
    a, b = 1, 1
    while b < 1000:
      a, b = b, a + b
      if 100 <= b < 1000 and f3d(b):
        fbs.append(b)
    
    # list triples of three digit square, triangular and Fibonacci
    # numbers that use nine different digits among them 
    qtf = []
    for q, t, f in product(sqs, trs, fbs):
      if len(set(c for x in (q, t, f) for c in str(x))) == 9:
        qtf.append((q, t, f))
    
    # find three pairs of triples in which all six triples are 
    # different and each of the three pairs of triples have two
    # common and two different values; save unmatched triples   
    rset = set()
    for (a, b, c), r in pairs(3, qtf):
      rset.add(r)
    sol, = rset
    print('Not found:', tuple(sorted(*sol)))
    

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: