Enigmatic Code

Programming Enigma Puzzles

Enigma 49: A square problem

10 Comments Posted by on 24 January 2013

From New Scientist #1192, 31st January 1980 [link] [link]

Young James was playing with his new calculator when a fault in the circuitry caused only the last four digits of the display to light up. Nothing else appeared to be wrong until he fed in a certain four-figure number. When he pressed the “square” button the number was unchanged, and on pressing the “square root” button the number again failed to change.

He showed this curious result to his elder sister, Camilla, who, after a calculation, was able to tell him that he happened to have picked the only four-figure number which when squared ends in the same four digits in the same order.

What was the number?

[enigma49]

enigma, enigma-book-1982

10 responses to “Enigma 49: A square problem”

  1. Jim Randell 24 January 2013 at 12:23 pm

    It’s very straightforward to write a program that checks all 4-digit numbers, but here’s a program that computes increasing n-digit numbers, so you can use it to find much larger numbers if you like. It takes 35ms to find the 4-digit solution.

    from enigma import (irange, arg,printf)

N = arg(4, 0, int, prompt="Number of digits")
P = arg(2, 0, int, prompt="Power")

# find n-digit numbers x, where the last n digits of x^P are x
(n, xs, p, q) = (1, [0], 1, 10)
while not(n > N):
  xs2 = []
  for i in irange(0, 9):
    for j in xs:
      x = i * p + j
      r = pow(x, P, q)
      if r == x: xs2.append(r)
  printf("[n={n}] {xs2}")      
  (n, xs, p, q) = (n + 1, xs2, q, q * 10)

# select N-digit numbers
for x in xs:
  if len(str(x)) == N: printf("{x}^{P} = {p}", p=x**P)

    Solution: The number was 9376.

    More details on Automorphic Numbers can be found at Wikipedia and Wolfram Alpha.

    Interestingly the number 9376 corresponds to ZERO on a phone keypad.

    Reply
    • Naim Uygun 24 January 2013 at 5:41 pm 
      for n in range(9999,31,-1):
    k=str(n*n)
    #compare last 4 digits of the square with n
    if k[-4:] != str(n): continue
    print("four digits number={0},  square={1}".format(n,k))
      Reply
  2. Naim Uygun 24 January 2013 at 10:17 pm

    A generalized version for different powers and length

    for i in range(2,5):
    for x in range(2,7):
        #Find n-digits number(s)  whose its power ends with that n-digits number
        q=(10**x)-1
        for n in range(q,2,-1):
            u=len(str(n))
            if u < x : break
            k=str(n**i)
            #compare last n digits of a power with n
            if k[-u:] != str(n): continue
            print("{0}^{2}={1}".format(n,k,i))
    Reply
  3. arthurvause 27 January 2013 at 11:40 am

    z2 = z mod 10N  →  z(z − 1)= 0 mod 10N. One factor of z(z − 1) is odd, the other even. The even factor is a multiple of 2N.

    For a solution other than 0 or 1, the odd factor of z(z − 1) must be a multiple of 5N (if the even factor is a multiple of 5 it is a multiple of 10, so the odd factor is congruent to 1 or 9 mod 10 and therefore not a multiple of 5, so the even factor is a multiple of 10N).

    So the solution is one of
    a) z = 2Nx,    z − 1 = 5Ny 
    b) z − 1 = 2Nx,   z = 5Ny

    Solutions to the Diophantine equation 2Nx + 5Ny = 1  produce the solutions
    a) z = 2N(x mod 5N)
    b) z = 5N(y mod 2N)

    So, some code. Function egcd is a standard recursive implementation of the Extended Euclidean Algorithm to find solutions to a linear Diophantine equation (and the gcd as a by-product). 

    def egcd(a,b):
  if b == 0:
    return [1,0,a]
  else:
    x,y,g = egcd(b, a%b)
    return [y, x - (a//b)*y, g] 

for N in range(1,40):
  x,y,g = egcd(5**N, 2**N)
  print "N =",N, sorted([(x%2**N)*5**N, (y%5**N)*2**N])
    Reply
    • arthurvause 27 January 2013 at 11:49 am

      The formatting didn’t come out as I had hoped. There should be some superscripts in the text. I have posted a properly formatted version on my blog

      Reply
    • Jim Randell 29 January 2013 at 8:56 am

      That’s a neat bit of analysis, and an efficient solution.

      (I think I’ve fixed up the superscripts for you).

      Reply
      • arthurvause 30 January 2013 at 9:09 pm

        Thanks for fixing the superscripts, Jim.

        As it turns out, a recent Project Euler problem, number 407 has some similarities to Enigma 49 (but is more generalised).

        Reply
    • Hugh Casement 26 August 2014 at 2:18 pm

      Should the Diophantine equation read something like x2^n – y5^n = ±1
      (expressing the difference between z and z – 1),
      or is there a mental leap that was too great for me?
      As you see, I’ve avoided those troublesome superscripts!

      Reply
  4. geoffrounce 13 August 2016 at 9:37 am 
    % 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;  
constraint E > 0 /\ A > 0;

var 1000..9999: ABCD = 1000*A + 100*B + 10*C + D;
var 10000000..99999999 :  EFGHABCD = D + 10*C + 100*B + 1000*A 
+ 10000*H + 100000*G + 1000000*F + E*10000000;

constraint EFGHABCD == ABCD * ABCD;

solve satisfy;
output["The number was ",show(A),show(B),show(C), show(D)];

% The number was 9376
% Finished in 102msec
    Reply
  5. Jim Randell 13 August 2016 at 10:10 am

    We can use the general Alphametic expression solver [[ SubstitutedExpression() ]] from the enigma.py library to solve this puzzle without needing to write a program.

    Here’s the command and its output:

    % python -m enigma SubstitutedExpression \
    --distinct="" \
    "(ABCD ** 2) % 10000 = ABCD"
((ABCD ** 2) % 10000 = ABCD)
((9376 ** 2) % 10000 = 9376) / A=9 B=3 C=7 D=6
[1 solution]

    The command runs in 80ms.

    We use the [[ --distinct="" ]] parameter to allow different letters to stand for the same digit.

    Reply

Leave a Comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.