login
Squares visited by the chess king on a spiral-numbered board, where the king moves to the square with the fewest steps to reach 1 using the 3x+1 function. In case of a tie, the king moves to the square with the smallest number.
0

%I #29 Aug 07 2023 09:55:27

%S 1,2,4,16,5,6,8,24,10,26,48,80,120,168,122,170,226,227,228,172,173,

%T 174,232,176,128,88,56,90,92,136,93,58,32,13,3,12,11,28,52,84,85,53,

%U 29,30,31,57,89,130,180,181,131,132,133,184,244,186,245,312,246,314

%N Squares visited by the chess king on a spiral-numbered board, where the king moves to the square with the fewest steps to reach 1 using the 3x+1 function. In case of a tie, the king moves to the square with the smallest number.

%C The king moves to the square with the fewest steps to reach 1 using the 3x+1 function. The function works as follows: start with the number, and if it is even, divide it by 2. Otherwise, multiply it by 3 and add 1, and repeat the process until you reach 1. If there are two squares with the same number of steps, the king picks the square with the smaller number.

%C The sequence contains 511 terms; the king gets stuck because all the adjacent squares are already taken.

%C The last square visited is numbered a(511) = 6619.

%C The highest-numbered square reached is a(327) = 12853.

%e The spiral board:

%e 17--16--15--14--13 .

%e | | .

%e 18 5---4---3 12 29

%e | | | | |

%e 19 6 1---2 11 28

%e | | | |

%e 20 7---8---9--10 27

%e | |

%e 21--22--23--24--25--26

%e a(1) = 1, the initial square.

%e a(2) = 2 because 2 has the fewest steps to reach 1 applying the function {n/2 if n is even, 3n + 1 if n is odd} repeatedly.

%o (Python)

%o class Spiral:

%o def __init__(self):

%o self.spiral = [[1]]

%o def increment(self, increment_size):

%o if increment_size == 0: # Recursion stop condition

%o return

%o size = len(self.spiral)

%o count = size ** 2 + 1

%o if size % 2 != 0:

%o self.spiral.insert(0, [])

%o for i in reversed(range(0, size + 1)):

%o self.spiral[i].append(count)

%o count += 1

%o for _ in range(size):

%o self.spiral[0].insert(0, count)

%o count += 1

%o else:

%o self.spiral.append([])

%o for i in range(0, size + 1):

%o self.spiral[i].insert(0, count)

%o count += 1

%o for _ in range(size):

%o self.spiral[-1].append(count)

%o count += 1

%o self.increment(increment_size - 1)

%o def find_position(self, target):

%o for i, row in enumerate(self.spiral):

%o for j, element in enumerate(row):

%o if element == target:

%o return (i, j)

%o def find_king_neighbours(self, target):

%o i, j = self.find_position(target)

%o neighbours_position = (

%o (i - 1, j - 1), (i - 1, j), (i - 1, j + 1),

%o (i, j - 1), (i, j + 1),

%o (i + 1, j - 1), (i + 1, j), (i + 1, j + 1)

%o )

%o return [self.spiral[i][j] for i, j in neighbours_position]

%o def steps(x):

%o count = 0

%o while x != 1:

%o if x % 2 == 0:

%o x //= 2

%o else:

%o x = 3 * x + 1

%o count += 1

%o return count

%o def min_steps(lst):

%o """Find the value with the minimal amount of steps with the 3x+1 function (the smallest in case of tie)"""

%o if len(lst) == 0:

%o raise ValueError("Empty list")

%o min_steps_seen, min_seed = float("inf"), float("inf")

%o for n in lst:

%o step = steps(n)

%o if step < min_steps_seen or step == min_steps_seen and n < min_seed:

%o min_steps_seen = step

%o min_seed = n

%o return min_seed

%o spiral = Spiral()

%o sequence = [1]

%o count = 1

%o print(count, 1)

%o while True:

%o count += 1

%o spiral.increment(2)

%o neighbours = spiral.find_king_neighbours(sequence[-1])

%o neighbours = [n for n in neighbours if n not in sequence]

%o try:

%o next_square = min_steps(neighbours)

%o except ValueError:

%o print("End of the sequence.")

%o break

%o sequence.append(next_square)

%o print(count, sequence[-1])

%Y Cf. A014682, A006577, A335816, A316667, A330008, A329520, A326922, A328928, A328929.

%K nonn,walk,fini

%O 1,2

%A _Wagner Martins_, Jul 15 2023