login
A341770
Largest number m on the square spiral board such that it takes n steps to reach square 1 from square m along the shortest path without stepping on any prime number.
0
1, 8, 23, 34, 61, 62, 97, 138, 189, 248, 315, 390, 473, 564, 663, 770, 885, 1008, 1139, 1278, 1425, 1580, 1743, 1914, 2093, 2280, 2475, 2678, 2889, 3108, 3335, 3570, 3813, 4064, 4323, 4590, 4865, 5148, 5439, 5738, 6045, 6360, 6683, 7014, 7353, 7700, 8055, 8418
OFFSET
0,2
COMMENTS
If stepping on prime squares is permitted, a(n) = 4*n^2 + 3*n + 1.
For n >= 7, a(n) = 4*n^2 - 9*n + 5 = 4*(n-1)^2 - (n-1), which is A033991(n-1).
PROG
(Python)
from sympy import prime, isprime
from math import sqrt, ceil
def neib(m):
if m == 1: L = [4, 6, 8, 2]
else:
n = int(ceil((sqrt(m) - 1.0)/2.0))
z1 = 4*n*n - 4*n + 2; z2 = 4*n*n - 2*n + 1; z3 = 4*n*n + 1
z4 = 4*n*n + 2*n + 1; z5 = 4*n*n + 4*n + 1;
if m == z1: L = [m + 1, m - 1, m + 8*n - 1, m + 8*n + 1]
elif m > z1 and m < z2: L = [m + 1, m - 8*n + 7, m - 1, m + 8*n + 1]
elif m == z2: L = [m + 8*n + 3, m + 1, m - 1, m + 8*n + 1]
elif m > z2 and m < z3: L = [m + 8*n + 3, m + 1, m - 8*n + 5, m - 1]
elif m == z3: L = [m + 8*n + 3, m + 8*n + 5, m + 1, m - 1]
elif m >z3 and m < z4: L = [m - 1, m + 8*n + 5, m + 1, m - 8*n + 3]
elif m == z4: L = [m - 1, m + 8*n + 5, m + 8*n + 7, m + 1]
elif m > z4 and m < z5: L = [m - 8*n + 1, m - 1, m + 8*n + 7, m + 1]
elif m == z5: L = [m - 8*n + 1, m - 1, m + 8*n + 7, m + 1]
return L
print(1)
L_1 = [1]; L_in = [1]; step_max = 60
for step in range(1, step_max + 1):
L = []
for j in range(0, len(L_1)):
m = L_1[j]
if isprime(m) == 0:
for k in range(4):
m_k = neib(m)[k]
if m_k not in L_in: L.append(m_k); L_in.append(m_k)
print(max(L))
L_1 = L
CROSSREFS
KEYWORD
nonn
AUTHOR
Ya-Ping Lu, Feb 19 2021
STATUS
approved