Enigmatic Code

Programming Enigma Puzzles

Enigma 1741: Four squares

From New Scientist #2909, 23rd March 2013 [link]

I have before me five two-digit numbers, with no leading zeros. All the digits are different and none of the numbers is prime. The sum of the five numbers is a perfect square. If I remove one of the numbers, the sum of the remaining four is also a perfect square. If I remove another number, the sum of the remaining three is again a perfect square, and if I remove a third number, the sum of the last two is again a perfect square.

What are my five numbers?

[enigma1741]

Advertisements

8 responses to “Enigma 1741: Four squares

  1. Jim Randell 20 March 2013 at 6:40 pm

    This Python program solves the problem recursively in 56ms.

    from enigma import irange, is_square, is_duplicate, csum, Primes, printf
    
    # primes up to 100
    primes = Primes(100)
    
    # two digit numbers with no duplicate digits that aren't prime
    ns = set(n for n in irange(10, 99) if not(is_duplicate(n) or n in primes))
    
    # n - list of numbers selected
    # d - digits used
    # s - partial sum
    def solve(n, d, s):
      # are we done?
      if len(n) == 5:
        printf("numbers = {n}, sums = {ss}", ss=list(csum(n))[1:])
        return
      # choose the next number
      for p in ns:
        # digits shouldn't be already used
        q = d.union(str(p))
        if len(q) != len(d) + 2: continue
        t = s + p
        # the sum of the numbers should be a square, if there's more than 1
        if len(n) > 0 and not(is_square(t)): continue
        solve(n + [p], q, t)
      
    solve([], set(), 0)
    

    Solution: The five numbers are 10, 39, 72, 48, 56.

  2. geoffrounce 20 March 2013 at 7:45 pm

    A solution using the permutations approach:

    from itertools import permutations
    from enigma import is_square
    
    def isprime(n): 
        for x in range(2, int(n**0.5)+1): 
            if n % x == 0: 
                return False 
        return True
    
    for p in permutations((1,2,3,4,5,6,7,8,9,0),10):
        a,b,c,d,e,f,g,h,i,j = p
        # ensure no leading zeroes for the 2 digit numbers
        if all(x!=0 for x in(a,c,e,g,i)):
            n1 = int(str(a) + str(b))
            n2 = int(str(c) + str(d))
            n3 = int(str(e) + str(f))
            n4 = int(str(g) + str(h))
            n5 = int(str(i) + str(j))
            if all (isprime(y)== False for y in (n1,n2,n3,n4,n5)):
                n6 = n1 + n2 + n3 + n4 + n5   # 5 2-digit nos.
                if is_square(n6):
                    n7 = n1 + n2 + n3 + n4    # 4 2-digit nos.
                    if is_square(n7):
                        n8 = n1 + n2 + n3     # 3 2-digit nos.
                        if is_square(n8):
                            n9 = n1 + n2      # 2 2-digit nos.
                            if is_square(n9):
                                print('Nos: :',n1,n2,n3,n4,n5,' Squares:  ',n6,n7,n8,n9)
    
  3. Brian Gladman 20 March 2013 at 8:37 pm

    Here is my version. There are at most 15 squares so its quicker to work with these rather than the numbers themselves.

    from enigma import Primes
    
    fs = '{:d}, {:d}, {:d}, {:d}, {:d} ({:d}, {:d}, {:d}, {:d})'
    # primes in the range 10 < p < 100
    pr = [x for x in Primes(100) if 10 < x < 100]
    # squares of integers 5 .. 18
    sq = [x ** 2 for x in range(5, 19)]
    
    # the first number (a)
    for a in range(10, 100):
      sa = set(str(a))
      if a in pr:
        continue
      # check squares the differ from a by a two digit number
      for bb in sq:
        # the second number (b)
        b, sb = bb - a, set(str(bb - a))
        # check that the second number has two different digits, both
        # different to those of a, and is not a prime
        if not 10 <= b < 100 or len(sb) != 2 or sa & sb or b in pr:
          continue
        # check squares the differ from b by a two digit number
        for cc in sq:
          # the third number (c)
          c, sc = cc - bb, set(str(cc - bb))
          # check that the third number has two different digits, both
          # different to those of a and b, and is not a prime
          if not 10 <= c < 100 or len(sc) != 2 or (sa | sb) & sc or c in pr:
            continue
          # check squares the differ from c by a two digit number
          for dd in sq:
            # the fourth number (d)
            d, sd = dd - cc, set(str(dd - cc))
            # check that the fourth number has two different digits, both
            # different to those of a, b and c, and is not a prime
            if (not 10 <= d < 100 or len(sd) != 2
                    or (sa | sb | sc) & sd or d in pr):
              continue
            # check squares the differ from d by a two digit number
            for ee in sq:
              # the fifth number (e)
              e, se = ee - dd, set(str(ee - dd))
              # check that the fifth number has two different digits, both
              # different to those of a, b, c and d, and is not a prime
              if (not 10 <= e < 100 or len(se) != 2
                      or (sa | sb | sc | sd) & se or e in pr):
                continue
              print(fs.format(a, b, c, d, e, bb, cc, dd, ee))
    
    • Jim Randell 20 March 2013 at 9:33 pm

      An interesting approach. Here’s my take on it.

      from itertools import combinations, permutations
      from enigma import irange, is_duplicate, Primes, printf
      
      # primes up to 100
      primes = Primes(100)
      
      # two digit numbers with no duplicate digits that aren't prime
      ns = set(n for n in irange(10, 99) if not(is_duplicate(n) or n in primes))
      
      # squares that sum 2 to 5 of the ns
      squares = list(i * i for i in irange(6, 18))
      
      # allowable digits
      ds0 = set('0123456789')
      
      # choose 4 increasing squares
      for sq in combinations(squares, 4):
        # compute the differences
        ds = list(sq[i + 1] - sq[i] for i in (0, 1, 2))
        # they must all be 2-digit non-primes
        if any(n not in ns for n in ds): continue
        # and there should be 4 unused digits
        rs = ds0.difference(*(str(d) for d in ds))
        if len(rs) != 4: continue
        # from which we can make 2 suitable numbers, that sum to sq[0]
        for (r1, r2) in permutations(rs, 2):
          a = int(r1 + r2)
          b = sq[0] - a
          if any(n not in ns for n in (a, b)): continue
          if rs.difference((r1, r2), str(b)): continue
      
          printf("numbers = {n}, squares = {sq}", n=[a, b] + ds)
      
      • Brian Gladman 21 March 2013 at 9:20 am

        I also rewrote it in a similar way to make it shorter:

        from itertools import permutations, combinations
        
        # primes in the range 10 < p < 100
        pr = set(x for x in range(11, 99, 2) if all(x % p for p in (2, 3, 5, 7)))
        
        # there are four squares from fourteen (5 ** 2 .. 18 ** 2)
        for sq in combinations((x ** 2 for x in range(5, 19)), 4):
          # the last three numbers are the differences between these squares
          cde = sq[1] - sq[0], sq[2] - sq[1], sq[3] - sq[2]
          # each of which must be two digit composites
          if all(10 <= x < 100 and x not in pr for x in cde):
            # now check that these values use six different digits by checking
            # for four unused digits
            t = [set(str(x)) for x in cde]
            s4 = set('0123456789') - (t[0] | t[1] | t[2])
            if len(s4) == 4:
              # now permute these unused digits to form the first two numbers
              for p, q, r, s in permutations(s4):
                a, b = ab = int(p + q), int(r + s)
                # which must be two digit non-primes that sum to the first square
                if a < b and a + b == sq[0]:
                  if all(10 <= x < 100 and x not in pr for x in ab):
                    print(ab + cde, sq)
        
      • Jim Randell 21 March 2013 at 11:31 am

        And here’s a recursive version.

        from itertools import permutations
        from enigma import irange, Primes, printf
        
        # primes up to 100
        primes = Primes(100)
        
        # decreasing squares
        squares = list(i * i for i in irange(18, 6, -1))
        
        # allowable digits
        digits = set('0123456789')
        
        # check for 2-digit, non-primes with no repeating digits
        def check(n):
          return (9 < n < 100 and n % 11 > 0 and n not in primes)
        
        # ss - selected squares
        # i, n - candidate squares[i:n]
        # ns - 2-digit numbers
        # ds - digits used in ns
        def solve(ss, i, n, ns, ds):
          # are we done?
          if len(ss) == 4:
            # make two 2-digit numbers from the remaining digits
            for (d1, d2) in permutations(digits.difference(ds), 2):
              a = int(d1 + d2)
              b = ss[0] - a
              if not(check(a) and check(b)): continue
              if len(ds.union((d1, d2), str(b))) != 10: continue
              printf("numbers = {ns}, squares = {ss}", ns=[a, b] + ns)
            return
          # choose the next square
          for j in range(i, n):
            s = squares[j]
            # compute the difference
            d = ss[0] - s
            # it needs to be a 2-digit, non-prime with different digits
            if not check(d): continue
            # and not use any of the digits we've already seen
            ds2 = ds.union(str(d))
            if len(ds2) != len(ds) + 2: continue
            solve([s] + ss, j + 1, n, [d] + ns, ds2)
        
        n = len(squares)
        for (i, s) in enumerate(squares):
          solve([s], i + 1, n, [], set())
        
  4. arthurvause 25 March 2013 at 1:51 pm

    Mine is a similar idea to Brian’s :

    from itertools import combinations as comb, permutations as perm
    
    squares = [x*x for x in xrange(6,19)]
    primes = set((11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97))
    candidates = set(range(10,100)) - primes - set(xrange(11,100,11))
    digits = set(range(10))
    
    for c in comb(squares,4):
      diffs = [c[n+1]-c[n] for n in xrange(3) ]
      if all(x in candidates for x in diffs):
        diff_digits = set([x%10 for x in diffs]) | set([x//10 for x in diffs])
        if len(diff_digits)==6:
          for p in perm(digits - diff_digits):
            n1 = p[0]*10+p[1]
            n2 = p[2]*10+p[3]
            if n1+n2==c[0] and n1<n2 and n1 in candidates and n2 in candidates :
              print [n1,n2]+diffs
    
  5. geoffrounce 22 August 2016 at 4:56 pm

    Here is another programme solution for Enigma 1471

    % A Solution in MiniZinc
    include "globals.mzn";
    
    var 1..9: A; var 0..9: B; var 0..9: C; var 1..9: D;
    var 1..9: E; var 0..9: F; var 0..9: G; var 1..9: H;
    var 0..9: I; var 1..9: J; 
    
    constraint A > 0 /\ C > 0 /\ E > 0 /\ G > 0 /\ I > 0
    /\ alldifferent([A,B,C,D,E,F,G,H,I,J]);
    
    var 10..99: AB = 10*A + B; 
    var 10..99: CD = 10*C + D; 
    var 10..99: EF = 10*E + F;
    var 10..99: GH = 10*G + H;
    var 10..99: IJ = 10*I + J;   
    
    predicate is_prime(var int: x) = 
      x > 1 /\ forall(i in 2..1 + ceil(sqrt(int2float(ub(x)))))
     ((i < x) -> (x mod i > 0));
    
    % none of the 2-digit numbers is prime
    constraint not is_prime(AB) /\ not is_prime(CD) /\ not is_prime(EF)
    /\ not is_prime(GH) /\ not is_prime(IJ);
    
    % sum of 2-5 digit square number totals 
    set of int: sq = {n*n | n in 4..23}; 
    
    % remove numbers in sequence and check sum of remaining numbers is a square
    constraint AB + CD + EF + GH + IJ in sq /\ AB + CD + EF + GH  in sq
    /\ AB + CD + EF in sq /\ AB + CD in sq;
    
    solve satisfy;
    
    output[ "Five numbers are "++ show(AB) ++ ", " ++ show(CD) 
     ++ ", " ++ show(EF) ++ ", " ++ show(GH) ++ ", " ++ show(IJ)];
    
    % Five numbers are 10, 39, 72, 48, 56
    %
    % Check: 10 + 39 = 49 (7^2), 10 + 39 + 72 = 121 (11^2), 
    % and 10 + 39 + 72 + 48 = 169 (13^2), 10 + 39 + 72 + 48 + 56 = 225 (15^2)
    % Finished in 93msec
    
    

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: