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.

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

Author

Ya-Ping Lu, Feb 19 2021

Keywords

• nonn

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

Crossrefs

Cf. A341541, A341542, A341672, A033991.

Programs

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