A332767 The squares visited on the 2D square (Ulam) spiral when starting at square 1 and then stepping to the closest unvisited square which contains a composite number. If two or more squares are the same distance from the current square then the one with the smallest composite number is chosen.

1, 4, 15, 14, 33, 32, 30, 55, 54, 87, 86, 85, 52, 27, 10, 9, 8, 6, 18, 39, 38, 36, 35, 16, 34, 60, 95, 94, 93, 58, 57, 56, 88, 129, 128, 177, 176, 175, 126, 125, 84, 51, 26, 25, 24, 46, 45, 22, 21, 20, 40, 69

Offset: 1

Author

Scott R. Shannon, Feb 23 2020

Keywords

• nonn
• walk

Comments

This sequence is the complement to A330979; here only composite numbers can be stepped to, while in A330979 only prime numbers can be stepped to. Due to the existence of many more composite numbers than primes the walk here forms a much tigher spiral and generally stays as close as possible to the origin. However the primes occasionally block this preferred path and causes the walk to detour away from the origin, which leaves gaps in the visited squares with composite numbers. Some of these gaps are eventually visited by later steps in the walk.

The first term at which a step to a non-adjacent square is required is a(154) = 74, which steps to a(155) = 158, a distance of sqrt(8) units away. The square with number 74 is surrounded by three primes 43,73,113 and five composites 44,72,75,112,114, all of which have been previously visited.

In the first 1 million terms the longest required step is from a(149464) = 64666, which has coordinates (-127,-22) relative to the starting 1-square, to a(149465) = 67774 with coordinates (-130,-43), a step of length sqrt(450), approximately 21.2 units. See A330782 for the progression of step length records. If the maximum step distance between adjacent composite terms has a finite value or is unbounded as n increases is unknown. The largest difference between adjacent composite terms is for a(650382) = 863400 to a(650383) = 939342, a difference of 75942.

In the first 1 million terms the smallest unvisited composite is 12, which is at coordinates (2,1) relative to the starting square. This square is surrounded by four primes so the walk is never required to step to it during the initial walk steps. See the image in the links. Given the composites become more frequent relative to the primes as n increases it would require a very large detour from the spiral pattern for this square to be visited, so it is likely, although unknown, this square will never be visited. However the link image for 1 million steps shows the path can make detours toward the central square when it is trapped by surrounding paths, so the possibility remains the inner unvisited squares could eventually be visited, although the number of walk steps required before such a detour occurs could be extremely large.

Examples

			a(2) = 4 as the starting square numbered 1 has three adjacent squares 1 unit away with numbers 4,6,8, and 4 is the smallest number of those.
a(4) = 14 as the previous visited square 15 has three unvisited adjacent composite number 14,16,34, and 14 is the smallest number of those.
a(7) = 30 as the previous number 32 is has three primes and one visited composite square one unit away. The next closest unvisited composites, sqrt(2) units away, are 30,58,60, and 30 is the smallest of those.
		

Links

• Scott R. Shannon, Illustration of a section of the walk up to n = 450. This shows how the square with number 12, which has four adjacent primes 1 unit away, is not visited during the initial part of the walk. Various other unvisited composites can also be seen.
• Scott R. Shannon, Illustration of the walk up to n = 1000000. The color of each step is graduated across the spectrum from red to violet to show the relative visit order of the squares. The starting square is shown as a white dot and the smallest unvisited composite square with number 12 is shown as a yellow dot. Note the walk steps shown in yellow which make a detour toward the central squares after about 150,000 steps. Click on the image to zoom in.
• Wikipedia, Ulam Spiral.

Crossrefs

Cf. A330782, A000040, A063826, A136626, A331027, A330979 (same rules but stepping to prime numbers).