Enigmatic Code

Programming Enigma Puzzles

Enigma 1736: Child’s play

From New Scientist #2904, 16th February 2013 [link]

The letters S, N, A and P denote different digits, and SNAP is the corresponding four-figure number, which varies depending on choice of digits. It can be verified that, when SNAP is 1249, SNAP³ = 194844SNAP.

What is the largest value SNAP can take and have SNAP³ ending with SNAP?

[enigma1736]

Advertisements

13 responses to “Enigma 1736: Child’s play

  1. Jim Randell 13 February 2013 at 6:22 pm

    A straightforward program quickly finds the answer. This Python program runs in 34ms.

    from enigma import irange, is_duplicate, printf
    
    for SNAP in irange(9876, 1234, step=-1):
      if is_duplicate(SNAP): continue
      if pow(SNAP, 3, 10000) != SNAP: continue
      printf("SNAP={SNAP}")
      break # we only need the largest value
    

    Solution: SNAP = 9376.

    Interestingly, the solution, if entered on a phone keypad, spells out the word ZERO.

    For more details on Trimorphic Numbers see Wikipedia or Wolfram Alpha.

    • Jim Randell 13 February 2013 at 11:02 pm

      Indeed, as Arthur points out, the same approach as that to the recently published here (but originally set 33 years ago) Enigma 49 will yield the answer (and the answer is the same). Indeed this code can be run with command line arguments of “4” and “3” to find 4-digit numbers whose cube ends in the same 4 digits as the original number.

      This is the same code augmented to only consider numbers with distinct digits. It also runs in 34ms.

      from enigma import irange, printf
      
      import sys
      N = 4 if len(sys.argv) < 2 else int(sys.argv[1])
      P = 3 if len(sys.argv) < 3 else int(sys.argv[2])
      
      # 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
            if pow(x, P, q) != x: continue
            s = str(x)
            if len(s) != len(set(s)): continue
            xs2.append(x)
        printf("[n={n}] {xs2}")      
        (n, xs, p, q) = (n + 1, xs2, q, q * 10)
      
      # select N-digit numbers, with distinct digits
      for x in xs:
        if len(str(x)) == N:
          printf("{x}^{P} = {p}", p=x ** P)
      
  2. arthurvause 13 February 2013 at 7:01 pm

    Another one for the diophantine solver (see Enigma 49)

    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] 
    
    x,y,g = egcd(5**4, 2**4)
    print max([snap for snap in [(x%2**4)*5**4, (y%5**4)*2**4]
               if 999 < snap < 10000
               and len(set([x for x in str(snap)]))==4])  
    
  3. ahmet cetinbudaklar 13 February 2013 at 8:01 pm

    P can have a value of one of 0 , 1 , 4 , 5 ,6 and 9 and looking at the cube number listing one can arrive at the solution with the highest value for SNAP

    • Naim Uygun 13 February 2013 at 8:33 pm
      from itertools import permutations
      result=set()
      for s,n,a,p  in permutations("9876543210",4):
          if s=='0': continue
          snap=int(s+n+a+p)
          cube=(snap**3)
          r=cube%10000
          if r==snap:
             result.add(snap)
      print("max SNAP =", max(result))
      
  4. ahmet çetinbudaklar 14 February 2013 at 4:56 am

    I further must add that 0 eliminates itself as SNAP must contain 4 different digits

  5. arthurvause 14 February 2013 at 9:33 am

    On second thoughts, my diophantine solution is too simplistic – it should also cater for the situations where the factors of 2^4 are split between (x-1) and (x+1), and 5^4 could be in any of (x-1), x, (x+1). This makes the diophantine solution much messier, so here is an alternative, based on the simpler observation that 5^4 is a factor of only one of (x-1), x, (x+1)

    candidates=set()
    for fives in xrange(5**4,10000,5**4):
      for offset in (-1,0,1):
        x=fives+offset
        if pow(x,3,10000)==x and len(set(str(x)))==4:
          candidates.add(x)
    
    print "all candidates:", sorted(candidates)
    
    • Jim Randell 14 February 2013 at 11:35 pm

      I like this. A neat bit of analysis, leading to a neat bit of code. And you produce the candidates in numerical order anyway, so if you only wanted to find the largest candidate you could just reverse the direction of the search and finish when you found the first solution (which turns out to be the first value you try anyway, so it works just as well for a manual solution).

      from enigma import printf
      
      def solve():
        S = 5 ** 4
        for f in range(S * (9999 // S), 999, -S):
          for x in (f + 1, f, f - 1):
            printf("[considering {x}]")
            if pow(x, 3, 10000) == x and len(set(str(x))) == 4:
              return x
      
      s = solve()
      printf("solution = {s}")
      
  6. arthurvause 15 February 2013 at 5:19 pm

    Here is a generalised solution using diophantine equations for N digits (without the constraint of all digits being different), tested for values of N from 3 to 100.
    It turned out to be quite convoluted, so I have put an explanation on a blog entry

    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] 
    
    s = set()
    
    for N in range(3,101):
      s = set((0,1,10**N-1, (10**N)//2-1,(10**N)//2+1))
      
      # 1st diophantine 
      x,y,g = egcd(5**N, 2**N)
      z = (x%2**N )*5**N
      s|= set((z,10**N-z))
    
      z = (y%5**N )*2**N
      s|= set((z,10**N-z))
    
      # 2nd diophantine 
      x,y,g = egcd(5**N, 2**(N-1))
    
      z=(x%2**(N-1))*5**N
      s|= set((z,10**N-z))
    
      z=(y%5**N)*2**(N-1) - 1
      s|= set((z,10**N-z))
    
      # 3rd diophantine 
      x,y,g = egcd(5**N, 2**(N-2))
    
      z = 2*(x%2**(N-2) )*5**N - 1
      while z < 10**N:
        s|= set((z,10**N-z))
        z+= 5**N*2**(N-1)
    
      # sanity check
      if len(s)<>15:
        print "ERROR, wrong number of solutions",len(s)
      for a in s:
        if pow(a,3,10**N) <> a:
          print "ERROR, Invalid value", a
          
      print "N=",N,"digits:", len(s),
      print "solutions, max non-trivial solution =", max( s-{10**N-1})
    
  7. Elizabeth Fullwood (@hednhart) 17 February 2013 at 1:25 pm

    The square of SNAP must be a number of the form zxcv0001, where z,x,c,v can take any values (they could all be 0 if SNAP was not constrained to be made up of 4 different digits). Could this be programmed too?

    • Jim Randell 17 February 2013 at 3:02 pm

      For the value of SNAP that is the required solution, SNAPn ends in SNAP for integers n > 0. You can show this by induction.

      You can use the code I published to solve Enigma 49 to play around with N-digit numbers where NP ends in N.

    • Hugh Casement 8 November 2014 at 7:13 pm

      In the case of 1249, 3751, 6249, 8751 (and 0001, 4999, 5001, 9999 if we allow them: note the reflections about 5000), it’s true that SNAP² mod 10000 = 1. So then SNAP to any odd power, taken modulo 10000, equals SNAP. But here we have the case (the only one) where SNAP² mod 10000 = SNAP, and therefore so does SNAP³ and indeed SNAP to any power, as Jim points out.
      I confess there was nothing remotely sophisticated (Diophantine, Eulerian, Gaussian, etc.) in my sledgehammer approach to find that out.

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: