A341672 a(n) is the number of numbers on the square spiral board such that it takes n steps for them to reach square 1 along the shortest path without stepping on any prime number.

1, 4, 7, 5, 9, 8, 12, 10, 14, 23, 29, 32, 35, 38, 46, 47, 52, 59, 65, 64, 67, 76, 78, 84, 90, 91, 94, 100, 106, 110, 111, 110, 119, 126, 131, 137, 139, 138, 143, 153, 154, 144, 152, 144, 152, 156, 170, 195, 193, 193, 192, 198, 203, 215, 215, 209, 216, 222, 225

Offset: 0

Author

Ya-Ping Lu, Feb 17 2021

Keywords

• nonn

Comments

a(n) is the number of terms in A341541 whose value equals n.

If stepping on prime squares is permitted, a(n) = 4*n. Conjecture: lim_{n->oo} a(n)/n = 4.

Crossrefs

Cf. A341541, A341542.

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 - 12*n + 10; z2 = 4*n*n - 10*n + 7; z3 = 4*n*n - 8*n + 5; z4 = 4*n*n - 6*n + 3; z5 = 4*n*n - 4*n + 1
        if m == z1:             L = [m + 1, m - 1, m + 8*n - 9, m + 8*n - 7]
        elif m > z1 and m < z2: L = [m + 1, m - 8*n + 15, m - 1, m + 8*n - 7]
        elif m == z2:           L = [m + 8*n - 5, m + 1, m - 1, m + 8*n - 7]
        elif m > z2 and m < z3: L = [m + 8*n - 5, m + 1, m - 8*n + 13, m - 1]
        elif m == z3:           L = [m + 8*n - 5, m + 8*n - 3, m + 1, m - 1]
        elif m >z3 and m < z4:  L = [m - 1, m + 8*n - 3, m + 1, m - 8*n + 11]
        elif m == z4:           L = [m - 1, m + 8*n - 3, m + 8*n - 1, m + 1]
        elif m > z4 and m < z5: L = [m - 8*n + 9, m - 1, m + 8*n - 1, m + 1]
        elif m == z5:           L = [m - 8*n + 9, m - 1, m + 8*n - 1, m + 1]
    return L
print(1)
L_1 = [1]; L_in = [1]; step_max = 100
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(len(L))
    L_1 = L