A330979 The squares visited on the Ulam Spiral when starting at square 1 and then stepping to the closest unvisited square which contains a prime number. If two or more squares are the same distance from the current square then the one with the smallest prime number is chosen.

1, 2, 3, 11, 29, 13, 31, 59, 61, 97, 139, 191, 251, 193, 101, 103, 67, 37, 17, 5, 19, 7, 23, 47, 79, 163, 281, 353, 283, 433, 521, 617, 523, 619, 439, 359, 223, 167, 83, 173, 229, 293, 227, 367, 449, 541, 743, 857, 977, 853

Offset: 1

Author

Scott R. Shannon, Jan 05 2020

Keywords

• nonn
• walk

Comments

The first term at which a step to a non-adjacent square is required is a(9) = 61; the previous square 59 has adjacent squares 31,32,33,58,60,93,94,95 of which only 31 is prime, but 31 has already been visited at a(7).

In the first 10 million terms the longest required step is from a(8165267) = 22147771, which has coordinates (-2353,1019) relative to the starting 1-square, to a(8165268) = 8236981 with coordinates (-1435,1355), a step of length sqrt(955620), approximately 977.6 units. See A331027 for the progression of step length records. If the maximum step distance between adjacent prime terms has a finite value or is unbounded as n increases is unknown. The largest difference between adjacent prime terms is for a(8176270) = 32960287 to a(8176271) = 18983957, a difference of 13976330.

In the first 10 million terms the smallest unvisited prime is 2701871, which has coordinates (44,822) relative to the starting 1-square. The smallest unvisited term is found to slowly increase as the number of steps increases, indicating that eventually all primes will be visited, although this is unknown. It may require an extremely large number of steps before all primes below a certain value are visited due to the decreasing likelihood of the walk taking the long steps required to visit those primes near the origin which were unvisited in earlier steps.

Examples

			a(4) = 11 as a(3) = 3, and in the Ulam Spiral 3 has adjacent surrounding neighbors 1,2,4,11,12,13,14,15. 2 is only 1 unit away but has already been visited. The other closest primes are 11 and 13, both of which are sqrt(2) units away, but 11 is chosen as 11 is less than 13.
		

Links

• Scott R. Shannon, Table of n, a(n) for n = 1..20000
• Scott R. Shannon, Image for the steps from n = 1 to 20000. The starting square a(1) = 1 is shown as a green dot and the square a(20000) = 1449733 is shown as a red dot. The smallest unvisited prime 727 is shown as a yellow dot. The longest step of sqrt(674) from a(7877) is shown as an orange line, and the largest difference between terms of 85126 from a(18627) is shown as a pink line.
• Scott R. Shannon, Image for the steps from n = 1 to 20000 with color. The color of each step is graduated across the spectrum from red to violet to show the relative visit order of the squares.
• Scott R. Shannon, Image for the steps from n = 1 to 10 million with color. The lowest unvisited prime 2701871 is show as a yellow dot on the left edge of an unvisited patch of squares directly above the starting square, which is shown as a larger white square. This is a large image which may take some seconds to load.
• Wikipedia, Ulam Spiral.

Crossrefs

Cf. A000040, A063826, A214664, A214665, A136626, A115258, A331027.

Extensions

a(121) and beyond, and associated images, correct by Scott R. Shannon, Feb 02 2020