A049604 Array T read by diagonals: T(i,j)=least number of knight's moves on unbounded chessboard from corner (0,0) to square (i,j).
0, 3, 3, 2, 4, 2, 3, 1, 1, 3, 2, 2, 4, 2, 2, 3, 3, 3, 3, 3, 3, 4, 4, 2, 2, 2, 4, 4, 5, 3, 3, 3, 3, 3, 3, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 3, 3, 3, 3, 5, 5, 5, 6, 6, 4, 4, 4, 4, 4, 4, 4, 6, 6, 7, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 7, 6, 6, 6, 6, 4, 4, 4, 4, 4, 6, 6, 6, 6, 7, 7, 7, 5, 5, 5, 5, 5, 5, 5, 5, 7, 7, 7
Offset: 0
Examples
Array T begins: 0, 3, 2, 3, 2, 3, 4, 5, 4, 5, 6, ... 3, 4, 1, 2, 3, 4, 3, 4, 5, 6, 5, ... 2, 1, 4, 3, 2, 3, 4, 5, 4, 5, 6, ... 3, 2, 3, 2, 3, 4, 3, 4, 5, 6, 5, ... 2, 3, 2, 3, 4, 3, 4, 5, 4, 5, 6, ... 3, 4, 3, 4, 3, 4, 5, 4, 5, 6, 5, ... 4, 3, 4, 3, 4, 5, 4, 5, 6, 5, 6, ... 5, 4, 5, 4, 5, 4, 5, 6, 5, 6, 7, ... 4, 5, 4, 5, 4, 5, 6, 5, 6, 7, 6, ... 5, 6, 5, 6, 5, 6, 5, 6, 7, 6, 7, ... 6, 5, 6, 5, 6, 5, 6, 7, 6, 7, 8, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..140, flattened
Programs
-
Maple
A := proc(n,k) option remember; local x; if k = 0 then if n = 1 then 3 else 2*floor(n/4)+ `mod`(n, 4) end if; elif k = 1 then x := n - k + 1; if x = 1 then 3 elif x = 2 then 4 else 2*floor((n+1)*(1/4))-1 + `mod`(n+1, 4) end if ; elif n < 2*k then A(n, n - k) else ## n >= 2*k and n >= k >= 2 1 + min(A(n-3,k-2), A(n-3,k-1)) end if; end proc: # Yu-Sheng Chang, Jun 10 2020 -
Mathematica
A[n_ /; n >= 0, k_ /; k >= 0] := A[n, k] = Module[{x}, Which[ k == 0, If[n == 1, 3, 2*Floor[n/4] + Mod[n, 4]], k == 1, x = n - k + 1; Which[x == 1, 3, x == 2, 4, True, 2*Floor[(n + 1)*(1/4)] - 1 + Mod[n + 1, 4]], n < 2*k, A[n, n - k], True, 1 + Min[A[n - 3, k - 2], A[n - 3, k - 1]]]]; A[, ] = 0; T[n_, k_] := A[n + k, k]; Table[T[n - k, k], {n, 0, 13}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 20 2022, after Yu-Sheng Chang *)
Formula
From Yu-Sheng Chang, Jun 10 2020: (Start)
We separate the generating function, F(z,v), into four parts: Left, Middle, Right and Remaining.
First, changing some entries and these lost terms are the Remaining part, X(z,v): T(1,0)=T(0,1)=1, T(2,2)=0, T(3,4)=T(4,3)=0, so X(z,v) = 2*(1+v)*z+4*v*z^2+4*v^2*z^4+3*(1+v)*v^2*z^5.
Second, the left and right parts, L(z,v) and R(z,v), collect coefficients like:
0
1 1
2 - 2
3 1 1 3
2 2 - 2 2
3 3 - - 3 3
4 4 2 - 2 4 4
5 3 3 - - 3 3 5
4 4 4 - - - 4 4 4
5 5 5 3 - - 3 5 5 5
6 6 4 4 - - - 4 4 6 6
7 5 5 5 - - - - 5 5 5 7
6 6 6 6 4 - - - 4 6 6 6 6
7 7 7 5 5 - - - - 5 5 7 7 7
Then R(z,v) = Sum_{j>=0} ((v^2*z^3)^j*(Sum_{i>=0} (((2*i+j)*(v*z)^0+(2*i+j+1)*(v*z)^1+(2*i+j+2)*(v*z)^2+(2*i+j+3)*(v*z)^3)*(v*z)^(4*i)))) = v*z*(1+z*v+z^2*v+z^2*v^2-z^3*v^2-z^3*v^3-z^4*v^3-z^5*v^4)/((1+z*v)*(1+z^2*v^2)*(1-z*v)^2*(1-z^3*v^2)^2) and L(z,v) = R(v*z,1/v) since it's symmetric.
Third, the middle part, M(z,v) collects:
-
- -
- - -
- - - -
- - - - -
- - - - - -
- - - 2 - - -
- - - 3 3 - - -
- - - 4 4 4 - - -
- - - - 3 3 - - - -
- - - - 4 4 4 - - - -
- - - - 5 5 5 5 - - - -
- - - - - 4 4 4 - - - - -
- - - - - 5 5 5 5 - - - - -
- - - - - 6 6 6 6 6 - - - - -
Then M(z,v) = Sum_{i=>0} (v^3*z^6*(v*z^3)^i*((i+2)*(1-v^(i+1))/(1-v)+(i+3)*(1-v^(i+2))*z/(1-v)+(i+4)*(1-v^(i+3))*z^2/(1-v))) = v^3*z^6*(2+3*z+3*z*v+4*z^2+4*z^2*v+4*z^2*v^2-z^3*v-z^3*v^2-2*z^4*v-8*z^4*v^2-3*z^5*v-2*z^4*v^3-11*z^5*v^2-11*z^5*v^3-3*z^5*v^4+4*z^7*v^3+4*z^7*v^4+6*z^8*v^3+10*z^8*v^4+6*z^8*v^5-2*z^10*v^5-3*z^11*v^5-3*z^11*v^6)/((1-z^3*v^2)^2*(1-z^3*v)^2).
Finally, F(z,v) = L(z,v) + M(z,v) + R(z,v) + X(z,v), so we have:
O.g.f.: F(z,v) = (2*v^10*z^20-2*v^9*(v+1)*z^19+4*v^9*z^18-2*v^8*(v+1)*z^17-2*v^6*(v^4-v^2+1)*z^16+2*v^5*(v+1)*(v^4-v^2+1)*z^15-2*v^5*(2*v^4-v^2+2)*z^14+v^4*(v+1)*(2*v^4+2*v^3-v^2+2*v+2)*z^13-v^4*(2*v^4+v^3-4*v^2+v+2)*z^12+v^3*(v+1)*(2*v^4-v^3-3*v^2-v+2)*z^11-v^3*(3*v^2-5*v+3)*(v+1)^2*z^10-v*(v+1)*(2*v^6+3*v^3+2)*z^9+v*(2*v^6-v^5+2*v^4+4*v^3+2*v^2-v+2)*z^8+v*(v+1)*(v^4+2*v^3-4*v^2+2*v+1)*z^7+(2*v^6+v^5+4*v^3+v+2)*z^6-(v+1)*(2*v^4-2*v^3+v^2-2*v+2)*z^5-(v^4+3*v^3+3*v+1)*z^4+(v+1)*(v^2-3*v+1)*z^3-(v+1)^2*z^2+3*(v+1)*z)/(v*z+1)/(z+1)/(v^2*z^2+1)/(z^2+1)/(v*z-1)^2/(z-1)^2/(v^2*z^3-1)/(v*z^3-1).
(End)