A336576 -id:A336576 - 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.

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, 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, 5, 4, 5, 6, 7, 8, 9, 10, 17, 18, 19, 18, -1, 16, 15, 14, 13, 12

Offset: 1

Ya-Ping Lu, Feb 14 2021

sign

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.

			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.

Ya-Ping Lu, Illustration of the shortest paths from n to 1 on the square spiral board without stepping on any prime number

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

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
step_max = 20; L_last = [1]; L2 = L_last; L3 = [[1]]
for step in range(1, step_max + 1):
    L1 = []
    for j in range(0, len(L_last)):
        m = L_last[j]; k = 0
        while k <= 3 and isprime(m) == 0:
            m_k = neib(m)[k]
            if m_k not in L1 and m_k not in L2: L1.append(m_k)
            k += 1
    L2 += L1; L3.append(L1); L_last = L1
i = 1
while i:
    if isprime(neib(i)[0])*isprime(neib(i)[1])*isprime(neib(i)[2])*isprime(neib(i)[3]) == 1: print(-1)
    elif i not in L2: break
    for j in range(0, len(L3)):
        if i in L3[j]: print(j); break
    i += 1

A336494 The number of steps for a walk on a square spiral numbered board when starting on square 1 and stepping to an unvisited square containing the lowest prime number, where the square is within a block of size (2n+1) X (2n+1) centered on the current square. If no unvisited prime numbered squares exist within the block the walk ends.

Original entry on oeis.org

7, 37, 65, 308, 654, 7214, 21992, 49850, 222791, 1146922, 1912101, 6372680, 23077800

Offset: 1

Scott R. Shannon, Jul 23 2020

For n = 1 this sequence is similar to A335856 except that only prime numbers can be stepped to; if no adjacent prime number exists then the walk ends. In general for a(n) the walk can step to any unvisited square containing the lowest prime number within a block of size (2n+1) X (2n+1) centered on the current square.

See A336576 for the final square number of the walks.

			The board is numbered with the square spiral:
.
  17--16--15--14--13   .
   |               |   .
  18   5---4---3  12   29
   |   |       |   |   |
  19   6   1---2  11   28
   |   |           |   |
  20   7---8---9--10   27
   |                   |
  21--22--23--24--25--26
.
a(1) = 7. Starting from the square 1 the sequence of adjacent unvisited lowest primes the walk can step to are 2,3,11,29,13,31,59. Once the square 59 is visited there are no other unvisited adjacent squares containing primes, so the walk terminates after 7 steps. See the first linked image.
a(2) = 38. This walk also starts by stepping to 2 and then 3. But the next lowest prime 5 is now two units away so is reachable and is thus the next stepped to square. Further steps are 7,19,17,37...,827,829,719,947. Once the square 947 is visited there are no other unvisited squares containing primes within the surrounding 5x5 block of squares, so the walk terminates after 38 steps. See the second linked image.
Also see the linked images for n=3,4,5,6.

Scott R. Shannon, Image showing the 7 steps of the walk for n = 1. For this and other images a green square shows the starting 1 square, a red square shows the final square, and a thick white line is the path between visited squares. All visited prime numbered squares are shown in yellow, while those unvisited squares containing primes are shown in grey. Blue squares mark out the (2n+1)x(2n+1) block of squares around the final square which contains no further unvisited primes. The square spiral numbering of the board is shown as a thin white line.
Scott R. Shannon, Image showing the 37 steps of the walk for n = 2. Click on this and other images to zoom in.
Scott R. Shannon, Image showing the 65 steps of the walk for n = 3.
Scott R. Shannon, Image showing the 308 steps of the walk for n = 4.
Scott R. Shannon, Image showing the 654 steps of the walk for n = 5.
Scott R. Shannon, Image showing the 7214 steps of the walk for n = 6.
Wikipedia, Ulam Spiral.

Cf. A336576 (final square number), A335856, A000040, A136626, A336092, A330979, A332767, A335661, A335364.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python