A335661 The squares visited on a square (Ulam) spiral, with a(1) = 1 and a(2) = 2, when stepping to the closest unvisited square containing a number that shares a common divisor > 1 with the number in the current square. If two or more such squares are the same distance from the current square then the one with the smallest number is chosen.

1, 2, 4, 6, 8, 22, 20, 40, 18, 39, 69, 105, 150, 104, 66, 38, 36, 63, 98, 62, 34, 14, 12, 3, 15, 5, 35, 60, 33, 30, 55, 88, 54, 87, 129, 177, 234, 299, 455, 375, 456, 374, 300, 235, 130, 90, 57, 93, 135, 186, 134, 92, 58, 32, 56, 91, 133, 182, 132, 180, 237

Offset: 1

Author

Scott R. Shannon, Jun 17 2020

Keywords

• nonn
• walk

Comments

Any even number on the square spiral has 4 diagonally adjacent squares which contain an even number and thus, unless all four such squares have been previously visited, a step to one of those adjacent squares, the one containing the smallest number, will always be possible. Any visited square containing a prime number will need to step to, and be stepped to from, a square containing a multiple of that prime number.

In the first 10 million terms the longest required step is from a(97528) = 5981, a prime number which has coordinates (39,13) relative to the starting 1-square, to a(97529) = 167468 (27*5981), with coordinates (205,-18), a step of length sqrt(28517), approximately 168.9 units. This is an extremely large step length relative to the total number of steps taken up to that point - see the attached link image. It is not surpassed by any subsequent step up to 10 million steps. If the maximum step distance between adjacent terms has a finite value or is unbounded as n increases is unknown. The largest difference between terms is for a(9404208) = 8964653 to a(9404209) = 10485343, a difference of 1520690.

In the first 10 million terms the smallest unvisited square is 37, which has coordinates (-3,3) relative to the starting 1-square. It is unknown if this square, and similar unvisited squares near the origin, is eventually visited for very large values of n or is never visited. The longest run of diagonal steps in the same direction to adjacent smaller even numbers is 52, from a(3979714) = 5051162 to a(3979766) = 4594498.

Examples

			a(3) = 4 as a(2) = 2 is surrounded by eight adjacent squares with numbers 3,4,1,8,9,10,11,12. The unvisited squares 1 unit away, 3,9,11 have no common factor with 2. Of the other squares sqrt(2) units away, 4,8,10,12, all share the common factor 2 with a(2), and the smallest of those is 4.
a(10) = 39 as a(9) = 18 is surrounded by adjacent squares 5,6,19,40,39,38,17,16. The square containing 39 is 1 unit directly left of 18 and shares the common factor 3. The other squares one unit away, 5,17,19, have no common factor with 18.
		

Links

• Scott R. Shannon, Image of the steps from 1 to 20001. The green dot shows the starting square 1, the red dot the final square 26453, and the yellow dot the smallest unvisited square 11. The orange line shows the largest step distance, sqrt(976), from a(8538) = 233 to a(8539) = 3029. The blue line shows the longest run of adjacent diagonal steps, each of length sqrt(2), to a lower even number in the same direction, from a(3747) = 7880 and lasts for 19 steps. The pink line shows the largest change in value for a single step, from a(19032) = 15023 to a(19033) = 25159, a difference of 10136.
• Scott R. Shannon, Image of the steps from 1 to 20001 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. Note how green colored steps, those around n = 10000, approach the origin, showing that all numbers near the origin may eventually be visited for very large values of n.
• Scott R. Shannon, Image of the steps from 1 to 100000. The orange line shows the step length of sqrt(28517) units at a(97528), from 5981 to 167468. The blue line shows the new longest run of adjacent diagonal steps to lower even numbers, a series of 24 steps. The yellow dot shows the new lowest unvisited square 13, square 11 being visited at a(26321).
• Scott R. Shannon, Image of the steps from 1 to 5000000 with color. Note how some violet colored steps, those around n = 4200000, approach the origin. The yellow dot shows the new lowest unvisited square 37, square 13 being visited at a(105263). Also note the visited area forms a roughly square pattern, following the largest outer numbers of the spiral. This becomes more pronounced as n increases.

Crossrefs

Cf. A000005, A032741, A063826, A214665, A330979, A331027, A332767, A335710.