Programming Enigma Puzzles
From New Scientist #2405, 26th July 2003 [link]
I have placed six different non-zero digits evenly-spaced around the circumference of a circle of radius 10 centimetres. I can now write down all sorts of lists of digits by the following process:
Start at one of the digits, write it down, move to a digit exactly 10cm or 20cm away, write it down, move to a digit exactly 10cm or 20cm away, write it down, etc etc. (You are allowed to revisit digits in this way).
I have just produced a list of six digits in this way. The six-figure number which is formed by this list turns out to be a perfect fourth power. I have then started again and produced a list of four digits. The four-figure number which is formed by this list turns out to be a perfect cube.
What is that cube?
[enigma1249]
 | Frits on Enigma 1041: Lucky sixes |
 | Jim Randell on BrainTwister #17: Semi-one… |
 | GeoffR on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Jim Randell on Enigma 773: Duodecimal |
 | Brian Gladman on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
| Frits on Enigma 773: Duodecimal |
Enigmatic Code 
This one was a little bit more involved than I initially expected.
This Python 3 program runs in 52ms.
from collections import Counter from enigma import irange, int2base, printf # set of <n>-powers (as strings) between <a> and <b> # containing only non-zero digits def powers(n, a, b): r = list() for i in irange(a, b): s = int2base(i ** n) if '0' in s: continue r.append(s) return r # 4 digit 3rd powers (10 = intc(cbrt(1000)), 21 = intf(cbrt(99999))) p3s = powers(3, 10, 21) printf("[p3s = {p3s}]") # 6 digit 4th powers (18 = intc(pow(100000, 0.25)), 31 = intf(pow(999999, 0.25))) p4s = powers(4, 18, 31) printf("[p4s = {p4s}]") # return an update of list <r> at index <i> with value <v> def update(r, i, v): r = list(r) r[i] = v return r # generate (<r>, <s>) rings <r> with embedded sequence <s> # n = length of sequence # s = initial sequence # ss = candidate sequences # i = current position in the ring # ring = current state of the ring def generate(n, s, ss, i, ring): # are we done? l = len(s) if l == n: if s in ss: yield (s, ring) else: # try to extend s ss = list(x for x in ss if x.startswith(s)) # first pick a template for p in ss: # the next digit is d = p[l] # choose an amount to move by for j in (1, 3, 5): k = (i + j) % 6 if ring[k] is None: # it's a new position, check it's a new digit if d in ring: continue r2 = update(ring, k, d) else: # if it's in the ring, check it matches if ring[k] != d: continue r2 = ring yield from generate(n, s + d, ss, k, r2) # find rings containing both a 4th power and a 3rd power def solve(): # consider a non-zero starting digit for the 4th power for d1 in set(p[0] for p in p4s): # and find rings that can produce a 4th power for (p4, ring) in generate(6, d1, p4s, 0, [ d1, None, None, None, None, None ]): # consider a non-zero starting digit for the 3rd power for d2 in set(p[0] for p in p3s): if d2 in ring: # the starting digit is already in the ring for (p3, ring2) in generate(4, d2, p3s, ring.index(d2), ring): yield (p4, p3, ring2) else: # place the starting digit in an empty slot for (i, x) in enumerate(ring): if x is None: for (p3, ring2) in generate(4, d2, p3s, i, update(ring, i, d2)): yield (p4, p3, r2) # count the results by the cube r = Counter() for (p4, p3, ring) in solve(): r[p3] += 1 printf("[p4={p4} p3={p3} ring={ring}]") # output the solutions for (k, v) in r.items(): printf("cube = {k} [{v} solutions]")Solution: The cube is 2197 (= 13³).
There are 6 essentially different rings (along with their mirror images).
The 4th power is always 279841 (= 23⁴) which has no repeated digits, so fully populates the ring.
Some MMa code.
Timing[a=Tuples[Range[9],{6}]; b=Cases[a,{a_,b_,c_,d_,e_,f_}/;a!=b!=c!=d!=e!=f]; c=Select[FromDigits/@b,IntegerQ[Power[#, (4)^-1]]&]; d=IntegerDigits/@c;Do[Print[c[[q]]," ",Select[FromDigits/@Cases[Tuples[d[[q]],{4}],{a_,b_,c_,d_}/;a!=b!=c!=d],IntegerQ[Power[#, (3)^-1]]&]],{q,1,Length[d]}]] 279841 {2197,1728} {1.669211,Null}Quite a bit slower. Also we get two possible cubes, however we can see that 1728 wouldn’t be possible as it violates the move criteria.
Paul.
Yes, quite involved.
from itertools import combinations, permutations # four digit perfect cubes with no zero digits cubes = {str(x ** 3):x for x in range(10, 22) if '0' not in str(x ** 3)} # six digit perfect fourth powers with no zero digits pwr_4 = {str(x ** 4):x for x in range(18, 32) if '0' not in str(x ** 4)} # check that the digits in 'digits' can be generated from six (or less) # different digits placed around the circle (pos = last position placed, # nbr = the number so far placed, seq = the placed digits) def place(digits, pos, nbr, seq): # if all digits have been placed or checked if nbr == 6: # return the sequence with a '?' in unused positions yield [x if x else '?' for x in seq] # if the current digit has already been placed elif digits[nbr] in seq: # can it be reached from the current position? cpos = seq.index(digits[nbr]) if (cpos - pos) % 6 in (1, 3, 5): # if yes, proceed to the next digit yield from place(digits, cpos, nbr + 1, seq) else: # if the digit is the first, place it in the first position # if not, try it in each of the three positions that can be # reached from the current position if they are empty for i in ((1, 3, 5) if nbr else (0,)): npos = (pos + i) % 6 if not seq[npos]: seq[npos] = digits[nbr] yield from place(digits, npos, nbr + 1, seq) seq[npos] = 0 # check if a four digit value can be made from the given # six digit circle def check_cube(cube, seq, n): # does the value have digits not present in the sequence # and, if so, are there enough empty positions for them set_np = set(cube).difference(seq) if len(set_np) > seq.count('?'): return False # put the digits that are not present in empty positions mt_pos = [i for i, c in enumerate(seq) if c == '?'] for p in permutations(mt_pos): i, pos, seq2 = 0, None, seq[:] for c in set_np: seq2[p[i]] = c i += 1 # check if the value can now be made in this sequence for c in cube: pos, last_pos = seq2.index(c), pos if last_pos and (pos - last_pos) % 6 not in (1, 3, 5): break else: return True return False # for solutions sol = set() # try to place each six digit fourth power for p4 in pwr_4: # consider each possible placement of digits for s in place(p4, 0, 0, [0] * 6): print(s) for c in cubes: if check_cube(c, s, 0): sol.update([(c, p4)]) fs = 'The cube is {} ({}^3), the fourth power is {} ({}^4).' for cube, p4 in sol: print(fs.format(cube, cubes[cube], p4, pwr_4[p4]))cubes = [s for s in [list(str(x**3)) for x in xrange(10,23)] if set(s[0::2]) & set(s[1::2]) == set()] fourths = [s for s in [list(str(x**4)) for x in xrange(18,32)] if set(s[0::2]) & set(s[1::2]) == set()] for c in cubes: for f in fourths: if f[0]==c[0]: for flip in (0,1): if (set(c[0::2]) & set(f[flip::2]) == set() == set(c[1::2]) & set(f[1-flip::2])): if len(set(c[0::2]) | set(f[1-flip::2]))<=3 and len(set(c[1::2]) | set(f[flip::2]))<=3: print "Cube is ", int(''.join(c)), "(fourth power is ",int(''.join(f)),")"When I first read the puzzle, I didn’t twig that “starting again” meant starting from the same position, so I retrospectively added the check that the cube and fourth start with the same digit. The logic can actually be simplified to:
from itertools import product cubes = [s for s in [list(str(x**3)) for x in xrange(10,23)] if set(s[0::2]) & set(s[1::2]) == set()] fourths = [s for s in [list(str(x**4)) for x in xrange(18,32)] if set(s[0::2]) & set(s[1::2]) == set()] for c,f in product(*[cubes, fourths]): if f[0]==c[0]: if (set(c[0::2]) & set(f[1::2]) == set() == set(c[1::2]) & set(f[0::2])): if len(set(c[0::2]) | set(f[0::2]))<=3 and len(set(c[1::2]) | set(f[1::2]))<=3: print "Cube is ", int(''.join(c)), "(fourth power is ",int(''.join(f)),")"I’m not sure that “starting again” does necessarily mean that you have to start from the same position. My program doesn’t assume that, and it finds there is only one possible solution (although in that solution the fourth power and the cube do start with the same digit).
I do like the idea of considering the parity of the index of each digit within the numbers. As these must alternate in numbers we generate from the ring, this gives us a quick way to solve the problem manually. We can immediately discard any number which has repeated digits that occur at a different index parity (so any number with consecutive repeated digits is out, but so is any number with repeated digits where a digit appears at both an odd and an even index).
Of the 8 possible 6-digit fourth powers that consist of non-zero digits, only one of them survives this test: 279841.
This fully populates the ring so any 4-digit cube can only contain these digits. There are only two candidates: 1728 and 2197.
But looking at the index parities of the digits in the 4-digit cubes in the 6-digit fourth power we get: 1728 = (1, 1, 0, 1), 2197 = (0, 1, 0, 1). But these must alternate in any number generated from the ring, and as you can reach any of the odd parity digits from any of the even parity digits it follows that if we construct the ring for 279841 in any of the 12 possible ways it will always be possible to generate 2197 from the ring.
After reading the question again, I can see why my first solution produced 2 solutions – I allowed a fourth power containing zero to be considered. So version 3 is similart to version 1:
from itertools import product cubes = [s for s in [list(str(x**3)) for x in xrange(10,23)] if set(s[0::2]) & set(s[1::2]) == set() and '0' not in s] fourths = [s for s in [list(str(x**4)) for x in xrange(18,32)] if set(s[0::2]) & set(s[1::2]) == set() and '0' not in s] for c,f in product(*[cubes,fourths]): for flip in (0,1): if (set(c[0::2]) & set(f[flip::2]) == set() == set(c[1::2]) & set(f[1-flip::2])): if len(set(c[0::2]) | set(f[1-flip::2]))<=3 and len(set(c[1::2]) | set(f[flip::2]))<=3: print "Cube is ", int(''.join(c)), "(fourth power is ",int(''.join(f)),")"If you allow 0 in the ring you can find a second solution. The fourth power is 707281 (=29⁴), and we can make 1728 (=12³) from the same ring.
As the 707281 has a repeated digit the ring is not fully populated, but 1728 is made up of digits included only in the fourth power, so it doesn’t matter what digit is in the unused position in the ring (as it does not appear in either of the numbers).
Here’s a Python program that uses the idea of index parities to solve the problem.
# when we generate numbers from the ring we must alternate digits at # positions 0, 2, 4 with digits at position 1, 3, 5. # # so for any number generated by a ring the digits at even indices # must be disjoint from the digits at odd indices # # and for two numbers generated from the same ring the shared digits # must always have the same or opposite parity # # also because every odd parity digit is reachable from every even # parity digit then any number whose digits are included in the ring # that satisfies these conditions can be generated from enigma import irange, int2base, printf # set of <n>-powers (as strings) from <a>^<n> to <b>^<n> # with non-zero index and consistent index parity def powers(n, a, b): r = list() for i in irange(a, b): s = int2base(i ** n) if '0' in s: continue if set(s[::2]).intersection(s[1::2]): continue r.append(s) return r # 4 digit 3rd powers (10 = intc(cbrt(1000)), 21 = intf(cbrt(99999))) p3s = powers(3, 10, 21) printf("[p3s = {p3s}]") # 6 digit 4th powers (18 = intc(pow(100000, 0.25)), 31 = intf(pow(999999, 0.25))) p4s = powers(4, 18, 31) printf("[p4s = {p4s}]") # consider the fourth power for p4 in p4s: # determine the digits of parity 0 and 1 (p40, p41) = (p4[::2], p4[1::2]) # now consider possible cubes for p3 in p3s: # find the parity of the digits in the cube (p30, p31) = (set(p3[::2]), set(p3[1::2])) # find matching parities for (p0, p1) in ((p30, p31), (p31, p30)): # reject any inconsistent parities if p0.intersection(p41) or p1.intersection(p40): continue # accumulate digits of matching parity (r0, r1) = (p0.union(p40), p1.union(p41)) # can they make a ring? if len(r0) > 3 or len(r1) > 3: continue printf("p4={p4} p3={p3} [r0={r0} r1={r1}]")I enjoyed this puzzle. A good programming practise I guess.
import time time1=time.time() fourths,Cubes=[],[i**3 for i in range(10,30)] path,ways,pathcube=[],[1,2,-1,-2],[] def FindCube(circle): for i in range(len(ways)): pathcube.append(ways[i]) if len(pathcube)<3: FindCube(circle) else: place=[-1]*4 for orgin in range(6): neworgin=orgin for j in range(3): neworgin=(neworgin+pathcube[j])%6 place[j]=neworgin number=circle[orgin] for j in range(3): number=number+circle[place[j]] if int(number) in Cubes: print("Found",number) return pathcube.pop() def Replace(numbers): for i in range(len(ways)): path.append(ways[i]) if len(path)<5: Replace(numbers) else: place,circle=[-1]*6,'' circle+=numbers[0] orgin=0 for j in range(5): orgin=(orgin+path[j])%6 place[j]=orgin; if 0 not in place: for j in range(5): circle=circle+numbers[place[j]] if len(circle)==len(set(circle)): #print("place=",place,path) #print(circle,numbers) if FindCube(circle): return path.pop() def Solve(): numbers=[0]*6 for i in range(18,32): number=i**4 strnumber=str(number) setnumber=set(strnumber) #print(setnumber) if (('0' not in strnumber) and len(setnumber)==len(strnumber)): fourths.append(number) for number in fourths: strnumber=str(number) for j in range(len(strnumber)): numbers[j]=strnumber[j] Replace(numbers) Solve() print((time.time()-time1)*1000)