# Enigmatic Code

Programming Enigma Puzzles

## Enigma 1249: Root routes

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]

### 10 responses to “Enigma 1249: Root routes”

1. Jim Randell 12 March 2015 at 8:18 am

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.

2. Paul 12 March 2015 at 2:10 pm

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.

3. Brian Gladman 12 March 2015 at 2:46 pm

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]))
```
4. arthurvause 14 March 2015 at 4:17 pm
```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)),")"
```
• arthurvause 15 March 2015 at 11:20 am

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)),")"
```
• Jim Randell 15 March 2015 at 7:14 pm

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.

• arthurvause 16 March 2015 at 9:46 am

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)),")"
```
5. Jim Randell 16 March 2015 at 7:44 am

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).

6. Jim Randell 16 March 2015 at 9:14 am

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}]")
```
7. saracogluahmet 21 March 2015 at 2:02 pm

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)
```

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