login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

a(n) is the number of steps to reach square 1 for a walk starting from square n along the shortest path on the square spiral board without stepping on any prime number. a(n) = -1 if such a path does not exist.
4

%I #26 Jul 29 2021 01:03:33

%S 0,1,2,1,2,1,2,1,2,3,4,-1,4,3,2,3,4,19,2,17,16,15,2,3,4,5,4,5,6,11,6,

%T 5,4,3,4,5,6,19,18,19,18,17,16,15,14,13,4,5,6,7,6,5,6,9,10,11,10,9,6,

%U 5,4,5,6,7,8,9,10,17,18,19,18,-1,16,15,14,13,12

%N a(n) is the number of steps to reach square 1 for a walk starting from square n along the shortest path on the square spiral board without stepping on any prime number. a(n) = -1 if such a path does not exist.

%C Conjecture: There is no "island of two or more nonprimes" enclosed by primes on the square spiral board. If the conjecture is true, then numbers n such that a(n) = -1 are the terms in A341542.

%H Ya-Ping Lu, <a href="/A341541/a341541.pdf">Illustration of the shortest paths from n to 1 on the square spiral board without stepping on any prime number</a>

%e The shortest paths for a(n) <= 20 are illustrated in the figure attached in Links section. If more than one path are available, the path through the smallest number is chosen as the shortest path.

%o (Python)

%o from sympy import prime, isprime

%o from math import sqrt, ceil

%o def neib(m):

%o if m == 1: L = [4, 6, 8, 2]

%o else:

%o n = int(ceil((sqrt(m) + 1.0)/2.0))

%o z1 = 4*n*n - 12*n + 10; z2 = 4*n*n - 10*n + 7; z3 = 4*n*n - 8*n + 5

%o z4 = 4*n*n - 6*n + 3; z5 = 4*n*n - 4*n + 1

%o if m == z1: L = [m + 1, m - 1, m + 8*n - 9, m + 8*n - 7]

%o elif m > z1 and m < z2: L = [m + 1, m - 8*n + 15, m - 1, m + 8*n - 7]

%o elif m == z2: L = [m + 8*n - 5, m + 1, m - 1, m + 8*n - 7]

%o elif m > z2 and m < z3: L = [m + 8*n - 5, m + 1, m - 8*n + 13, m - 1]

%o elif m == z3: L = [m + 8*n - 5, m + 8*n - 3, m + 1, m - 1]

%o elif m > z3 and m < z4: L = [m - 1, m + 8*n - 3, m + 1, m - 8*n + 11]

%o elif m == z4: L = [m - 1, m + 8*n - 3, m + 8*n - 1, m + 1]

%o elif m > z4 and m < z5: L = [m - 8*n + 9, m - 1, m + 8*n - 1, m + 1]

%o elif m == z5: L = [m - 8*n + 9, m - 1, m + 8*n - 1, m + 1]

%o return L

%o step_max = 20; L_last = [1]; L2 = L_last; L3 = [[1]]

%o for step in range(1, step_max + 1):

%o L1 = []

%o for j in range(0, len(L_last)):

%o m = L_last[j]; k = 0

%o while k <= 3 and isprime(m) == 0:

%o m_k = neib(m)[k]

%o if m_k not in L1 and m_k not in L2: L1.append(m_k)

%o k += 1

%o L2 += L1; L3.append(L1); L_last = L1

%o i = 1

%o while i:

%o if isprime(neib(i)[0])*isprime(neib(i)[1])*isprime(neib(i)[2])*isprime(neib(i)[3]) == 1: print(-1)

%o elif i not in L2: break

%o for j in range(0, len(L3)):

%o if i in L3[j]: print(j); break

%o i += 1

%Y Cf. A341542, A341672, A330979, A332767, A335364, A335661, A336494, A336576.

%K sign

%O 1,3

%A _Ya-Ping Lu_, Feb 14 2021