import numpy # [1,1] is solvable in 1 move by going to [2]: status = {bytes([1,1]): (1, bytes([2]))} def moves(pos): results = [] for which in range(0, len(pos)): if pos[which] == 0: continue leftDest = which - pos[which] if (leftDest >= 0 and pos[leftDest] > 0): newpos = bytearray(pos) newpos[leftDest] += newpos[which] newpos[which] = 0 results.append(bytes(numpy.trim_zeros(newpos))) rightDest = which + pos[which] if (rightDest < len(pos) and pos[rightDest] > 0): newpos = bytearray(pos) newpos[rightDest] += newpos[which] newpos[which] = 0 results.append(bytes(numpy.trim_zeros(newpos))) return results empty = bytes([]) def solve(pos): if pos in status: return status[pos] if len(pos) == 1: return (0, empty) nexts = moves(pos) for next in moves(pos): (nextn, nextpos) = solve(next) if nextn >= 0: result = (nextn+1, next) status[pos] = result return result return (-1, empty) # returns a byteArray def posOf(n): if n == 1: return bytearray([1]) last = n % 2 rest = posOf(n // 2) rest.append(last) return rest hits = 0 find = 10000 n = 1 allhits = [] while True: (m, dummy) = solve(bytes(posOf(n))) if (m >= 0): hits += 1 print(hits, n) allhits.append(str(n)) if hits == find: break n += 2