cp's OEIS Frontend

A118312 Number of squares on infinite chessboard that a knight can reach in n moves from a fixed square.

%I A118312 #43 Dec 27 2024 13:00:55
%S A118312 1,8,33,76,129,196,277,372,481,604,741,892,1057,1236,1429,1636,1857,
%T A118312 2092,2341,2604,2881,3172,3477,3796,4129,4476,4837,5212,5601,6004,
%U A118312 6421,6852,7297,7756,8229,8716,9217,9732,10261,10804,11361,11932,12517,13116,13729,14356,14997,15652
%N A118312 Number of squares on infinite chessboard that a knight can reach in n moves from a fixed square.
%C A118312 Related to A018842: a(n) = A018842(n) + A018842(n-2) + A018842(n-4) + ... .
%D A118312 M. Petkovic, Mathematics and Chess, Dover Publications (2003), Problem 3.11.
%H A118312 Vincenzo Librandi, <a href="/A118312/b118312.txt">Table of n, a(n) for n = 0..1000</a>
%H A118312 Mordechai Katzman, <a href="http://www.katzman.staff.shef.ac.uk/ComputerAlgebra/knight.ps">Knight's moves on an infinite board</a>
%H A118312 Mordechai Katzman, <a href="https://arxiv.org/abs/math/0504113">Counting monomials</a>, arXiv:math/0504113 [math.AC], 2005.
%H A118312 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-3,1).
%F A118312 a(n) = -3 + 4*n + 7*n^2 + 4*sign((n-2)*(n-1)).
%F A118312 G.f.: (1 + 5*x + 12*x^2 - 8*x^4 + 4*x^5)/(1 - x)^3.
%F A118312 a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - _Vincenzo Librandi_, Jul 09 2012
%F A118312 For n >= 3, a(n) = A005892(n).
%F A118312 E.g.f.: exp(x)*(1 + 11*x + 7*x^2) - 2*x*(x + 2). - _Stefano Spezia_, Jul 27 2022
%e A118312 a(2)=33 because knight in 2 moves from square (0,0) can reach one of the following squares: {{0,0}, {-4,-2}, {-4,0}, {-4,2}, {-3,-3}, {-3,-1}, {-3,1}, {-3,3}, {-2,-4}, {-2,0}, {-2,4}, {-1,-3}, {-1,-1}, {-1,1}, {-1,3}, {0,-4}, {0,-2}, {0,2}, {0,4}, {1,-3}, {1,-1}, {1,1}, {1,3}, {2,-4}, {2,0}, {2,4}, {3,-3}, {3,-1}, {3,1}, {3,3}, {4,-2}, {4,0}, {4,2}}.
%t A118312 Table[ -3 + 4*n + 7*n^2 + 4*Sign[(n - 2)(n - 1)], {n, 0, 100}]
%t A118312 CoefficientList[Series[(1+5*x+12*x^2-8*x^4+4*x^5)/(1-x)^3,{x,0,50}],x] (* _Vincenzo Librandi_, Jul 09 2012 *)
%t A118312 Join[{1,8,33},LinearRecurrence[{3,-3,1},{76,129,196},50]] (* _Harvey P. Dale_, Dec 05 2014 *)
%o A118312 (Magma) I:=[1, 8, 33, 76, 129, 196, 277]; [n le 7 select I[n] else 3*Self(n-1)-3*Self(n-2)+Self(n-3): n in [1..50]]; // _Vincenzo Librandi_, Jul 09 2012
%o A118312 (PARI) a(n)=7*n^2 + 4*n - 3 + 4*sign((n-2)*(n-1)) \\ _Charles R Greathouse IV_, Feb 09 2017
%Y A118312 Cf. A005892, A018842 (squares in EXACTLY n moves), A018836 (squares in <=n moves).
%K A118312 easy,nice,nonn
%O A118312 0,2
%A A118312 Anton Chupin (chupin(AT)icmm.ru), May 14 2006
%E A118312 Link updated by _Tristan Miller_, Jun 13 2013