cp's OEIS Frontend

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

%I A341541 #26 Jul 29 2021 01:03:33
%S A341541 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 A341541 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 A341541 5,4,5,6,7,8,9,10,17,18,19,18,-1,16,15,14,13,12
%N A341541 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 A341541 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 A341541 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 A341541 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 A341541 (Python)
%o A341541 from sympy import prime, isprime
%o A341541 from math import sqrt, ceil
%o A341541 def neib(m):
%o A341541     if m == 1: L = [4, 6, 8, 2]
%o A341541     else:
%o A341541         n = int(ceil((sqrt(m) + 1.0)/2.0))
%o A341541         z1 = 4*n*n - 12*n + 10; z2 = 4*n*n - 10*n + 7; z3 = 4*n*n - 8*n + 5
%o A341541         z4 = 4*n*n - 6*n + 3; z5 = 4*n*n - 4*n + 1
%o A341541         if m == z1:             L = [m + 1, m - 1, m + 8*n - 9, m + 8*n - 7]
%o A341541         elif m > z1 and m < z2: L = [m + 1, m - 8*n + 15, m - 1, m + 8*n - 7]
%o A341541         elif m == z2:           L = [m + 8*n - 5, m + 1, m - 1, m + 8*n - 7]
%o A341541         elif m > z2 and m < z3: L = [m + 8*n - 5, m + 1, m - 8*n + 13, m - 1]
%o A341541         elif m == z3:           L = [m + 8*n - 5, m + 8*n - 3, m + 1, m - 1]
%o A341541         elif m > z3 and m < z4: L = [m - 1, m + 8*n - 3, m + 1, m - 8*n + 11]
%o A341541         elif m == z4:           L = [m - 1, m + 8*n - 3, m + 8*n - 1, m + 1]
%o A341541         elif m > z4 and m < z5: L = [m - 8*n + 9, m - 1, m + 8*n - 1, m + 1]
%o A341541         elif m == z5:           L = [m - 8*n + 9, m - 1, m + 8*n - 1, m + 1]
%o A341541     return L
%o A341541 step_max = 20; L_last = [1]; L2 = L_last; L3 = [[1]]
%o A341541 for step in range(1, step_max + 1):
%o A341541     L1 = []
%o A341541     for j in range(0, len(L_last)):
%o A341541         m = L_last[j]; k = 0
%o A341541         while k <= 3 and isprime(m) == 0:
%o A341541             m_k = neib(m)[k]
%o A341541             if m_k not in L1 and m_k not in L2: L1.append(m_k)
%o A341541             k += 1
%o A341541     L2 += L1; L3.append(L1); L_last = L1
%o A341541 i = 1
%o A341541 while i:
%o A341541     if isprime(neib(i)[0])*isprime(neib(i)[1])*isprime(neib(i)[2])*isprime(neib(i)[3]) == 1: print(-1)
%o A341541     elif i not in L2: break
%o A341541     for j in range(0, len(L3)):
%o A341541         if i in L3[j]: print(j); break
%o A341541     i += 1
%Y A341541 Cf. A341542, A341672, A330979, A332767, A335364, A335661, A336494, A336576.
%K A341541 sign
%O A341541 1,3
%A A341541 _Ya-Ping Lu_, Feb 14 2021