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]

Advertisements

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)
    

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: