login
Squares visited by a knight moving on a square-spiral numbered board where the knight moves to an unvisited square with the lowest prime spiral number, or lowest composite number if no primes are available.
7

%I #17 Jun 27 2020 03:05:55

%S 1,10,3,6,17,4,7,2,5,8,11,14,29,32,61,16,19,22,41,18,37,62,139,60,13,

%T 28,9,12,31,54,89,30,53,26,47,76,23,20,43,70,109,42,73,44,71,40,67,36,

%U 97,34,59,56,131,88,127,52,83,80,167,82,173,84,27,24,79,46,21,72,107

%N Squares visited by a knight moving on a square-spiral numbered board where the knight moves to an unvisited square with the lowest prime spiral number, or lowest composite number if no primes are available.

%C The squares are numbered starting with 1 at the origin (0,0). The sequence is finite: when arriving on square number a(209) = 147, there is no free square within reach for the next move. - _M. F. Hasler_, Jan 26 2020

%H Simon S. Gurvets, <a href="/A330008/b330008.txt">Table of n, a(n) for n = 1..209</a>

%H N. J. A. Sloane and Brady Haran, <a href="https://www.youtube.com/watch?v=RGQe8waGJ4w">The Trapped Knight</a>, Numberphile video (2019).

%H Scott R. Shannon, <a href="/A330008/a330008.png">Image showing the steps of the knight's path</a>. A green dot marks the starting 1 square and a red dot the final square with number 147. The red dot is surrounded by eight blue dots to show the occupied neighboring squares. A yellow dots marks the smallest unvisited square with number 15. Purple dots mark the visited squares containing a prime number. The path after square 1 contains 67 primes and 141 composites.

%o (PARI) local(U); my(v(p)=if(bittest(U,p),[9,0],[1-isprime(p+1),p]), nxt(x)=vecsort([v(pos(x+k))|k<-K])[1][2], K=[[(-1)^(i\2)<<(i>4),(-1)^i<<(i<5)]|i<-[1..8]], pos(x,y=x[2])=if(y>=abs(x=x[1]),4*y^2-y-x,-x>=abs(y),4*x^2-x-y,-y>=abs(x),(4*y-3)*y+x,(4*x-3)*x+y), xy(n,m=sqrtint(n),k=m\/2)=if(m<=n-=4*k^2,[n-3*k,-k],n>=0,[-k,k-n],n>=-m,[-k-n,k],[k,3*k+n]), A=List(0)); until(!listput(A,nxt(xy(A[#A]))), U+=1<<A[#A]); A330008=[t+1|t<-A[^-1]] \\ _M. F. Hasler_, Jan 26 2020

%Y Cf. A316667.

%K nonn,fini,full

%O 1,2

%A _Simon S. Gurvets_, Nov 26 2019