Enigmatic Code

Programming Enigma Puzzles

Enigma 40: Six Squares

From New Scientist #1182, 22nd November 1979 [link]

“Since last year”, said Mr Knull, “when I read in M500/52 of a puzzle which its proposer John Hulbert described as a ‘glorious time waster’, I have been struggling with two versions of it. I wonder if you can help me with the easier version? It is quite simple to state. Find three different integers, P, Q and R, such that P+Q, P+R, Q+R, P−Q, P−R, and Q−R are all perfect squares. Any questions?”

“Just one”, I said. “Is 0 an integer? I always forget.”

“Of course it is”, said Mr Knull. “And so of course are −1, −2 and so on”.

What is the smallest such set of three different integers you can find? By smallest I mean with P+Q+R as small as possible.

This puzzle is revisited in Enigma 45.

[enigma40]

Advertisements

2 responses to “Enigma 40: Six Squares

  1. jimrandell 30 January 2012 at 3:11 pm

    Having previously solved Enigma 45, this is a simple modification. You just need to remove the condition that R > 0. Although having said that I probably wouldn’t have come up with a solution that was as efficient if I hadn’t tackled Enigma 45.

    This program runs in 36ms.

    # consider: P+Q = a^2, P+R = b^2, Q+R = c^2
    # a^2 + b^2 + c^2 = 2(P+Q+R) so we can minimize that
    
    # also: P > Q > R
    # so: a^2 > b^2 > c^2
    
    # and also the following must be squares:
    # b^2 - c^2 = P-Q
    # a^2 - c^2 = P-R
    # a^2 - b^2 = Q-R
    
    from itertools import count
    from enigma import is_square, first, printf
    
    def solve():
    
      for a in count(2):
        a2 = a * a
        for b in range(1, a):
          b2 = b * b
          if not is_square(a2 - b2): continue
          for c in range(0, b):
            c2 = c * c
            if not is_square(a2 - c2): continue
            if not is_square(b2 - c2): continue
    
            (S, r) = divmod(a2 + b2 + c2, 2)
            if r > 0: continue
            (P, r) = divmod(a2 + b2 - c2, 2)
            if r > 0: continue
            (Q, r) = divmod(a2 + c2 - b2, 2)
            if r > 0: continue
            (R, r) = divmod(b2 + c2 - a2, 2)
            if r > 0: continue
            if not(P > Q > R): continue
    
            yield (S, P, Q, R)
    
    
    # how many solutions to find
    import sys
    n = (1 if len(sys.argv) < 2 else int(sys.argv[1]))
    
    for (S, P, Q, R) in first(solve(), n):
      printf("S={S} P={P} Q={Q} R={R}")
    

    Solution: P = 17, Q = 8, R = −8, P + Q + R = 17.

    • geoffrounce 27 January 2016 at 6:26 pm
      % A suitable candidate for a MiniZinc solution
      
      include "globals.mzn";
      var -50..50: P; var -50..50: Q; var -50..50: R;
      
      predicate is_square(var int: c) =
         let {
            var 0..ceil(pow(int2float(ub(c)),(1/2.0))): z
         } in z * z = c ;
      
      constraint all_different([P,Q,R]); 
      
      constraint is_square (P+Q) /\ is_square(P+R) /\ is_square(Q+R)
              /\ is_square(P-Q) /\ is_square(P-R) /\ is_square(Q-R);
      
      solve minimize(P+Q+R);
      
      output["P, Q, R = ",show(P)," , ",show(Q)," , ",show(R)];
      
      % Output
      % P, Q, R = 17 , 8 , -8
      

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: