A104144 - OEIS

%I #74 Sep 01 2024 10:25:00

%S 0,0,0,0,0,0,0,0,1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144,

%T 16272,32512,64960,129792,259328,518145,1035269,2068498,4132920,

%U 8257696,16499120,32965728,65866496,131603200,262947072,525375999,1049716729,2097364960

%N a(n) = Sum_{k=1..9} a(n-k); a(8) = 1, a(n) = 0 for n < 8.

%C Sometimes called the Fibonacci 9-step numbers.

%C For n >= 8, this gives the number of integers written without 0 in base ten, the sum of digits of which is equal to n-7. E.g., a(11) = 8 because we have the 8 numbers: 4, 13, 22, 31, 112, 121, 211, 1111.

%C The offset for this sequence is fairly arbitrary. - _N. J. A. Sloane_, Feb 27 2009

%H T. D. Noe, <a href="/A104144/b104144.txt">Table of n, a(n) for n = 0..208</a>

%H Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, <a href="http://www.emis.de/journals/JIS/VOL18/Szczyrba/sz3.html">Analytic Representations of the n-anacci Constants and Generalizations Thereof</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.

%H Taras Goy and Mark Shattuck, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Shattuck/shattuck20.html">Some Toeplitz-Hessenberg Determinant Identities for the Tetranacci Numbers</a>, J. Int. Seq., Vol. 23 (2020), Article 20.6.8.

%H Kai Wang, <a href="https://www.researchgate.net/publication/344295426_IDENTITIES_FOR_GENERALIZED_ENNEANACCI_NUMBERS">Identities for generalized enneanacci numbers</a>, Generalized Fibonacci Sequences (2020).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>

%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,1,1,1,1,1,1).

%F a(n) = Sum_{k=1..9} a(n-k) for n > 8, a(8) = 1, a(n) = 0 for n=0..7.

%F G.f.: x^8/(1-x-x^2-x^3-x^4-x^5-x^6-x^7-x^8-x^9). - _N. J. A. Sloane_, Dec 04 2011

%F Another form of the g.f. f: f(z) = (z^8-z^9)/(1-2*z+z^(10)), then a(n) = Sum_((-1)^i*binomial(n-8-9*i,i)*2^(n-8-10*i), i=0..floor((n-8)/10))-Sum_((-1)^i*binomial(n-9-9*i,i)*2^(n-9-10*i), i=0..floor((n-9)/10)) with Sum_(alpha(i), i=m..n)=0 for m>n. - _Richard Choulet_, Feb 22 2010

%F From _N. J. A. Sloane_, Dec 04 2011: (Start)

%F Let b be the smallest root (in magnitude) of g(x) := 1-x-x^2-x^3-x^4-x^5-x^6-x^7-x^8-x^9, b = 0.50049311828655225605926845999420216157202861343888...

%F Let c = -b^8/g'(b) = 0.00099310812055463178382193226558248643030626601288701...

%F Then a(n) is the nearest integer to c/b^n. (End)

%p for n from 0 to 50 do k(n):=sum((-1)^i*binomial(n-8-9*i,i)*2^(n-8-10*i),i=0..floor((n-8)/10))-sum((-1)^i*binomial(n-9-9*i,i)*2^(n-9-10*i),i=0..floor((n-9)/10)):od:seq(k(n),n=0..50);a:=taylor((z^8-z^9)/(1-2*z+z^(10)),z=0,51);for p from 0 to 50 do j(p):=coeff(a,z,p):od :seq(j(p),p=0..50); # _Richard Choulet_, Feb 22 2010

%t a={1, 0, 0, 0, 0, 0, 0, 0, 0}; Table[s=Plus@@a; a=RotateLeft[a]; a[[ -1]]=s, {n, 50}]

%t LinearRecurrence[{1, 1, 1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 1}, 50] (* _Vladimir Joseph Stephan Orlovsky_, May 25 2011 *)

%t With[{nn=9},LinearRecurrence[Table[1,{nn}],Join[Table[0,{nn-1}],{1}],50]] (* _Harvey P. Dale_, Aug 17 2013 *)

%o (PARI) a(n)=([0,1,0,0,0,0,0,0,0; 0,0,1,0,0,0,0,0,0; 0,0,0,1,0,0,0,0,0; 0,0,0,0,1,0,0,0,0; 0,0,0,0,0,1,0,0,0; 0,0,0,0,0,0,1,0,0; 0,0,0,0,0,0,0,1,0; 0,0,0,0,0,0,0,0,1; 1,1,1,1,1,1,1,1,1]^n*[0;0;0;0;0;0;0;0;1])[1,1] \\ _Charles R Greathouse IV_, Jun 16 2015

%o (PARI) A104144(n,m=9)=(matrix(m,m,i,j,j==i+1||i==m)^n)[1,m] \\ _M. F. Hasler_, Apr 22 2018

%Y Cf. A000045, A000073, A000078, A001591, A001592, A066178, A079262 (Fibonacci n-step numbers).

%Y Cf. A255529 (Indices of primes in this sequence).

%K nonn,easy

%O 0,11

%A Jean Lefort (jlefort.apmep(AT)wanadoo.fr), Mar 07 2005

%E Edited by _N. J. A. Sloane_, Aug 15 2006 and Nov 11 2006

%E Incorrect formula deleted by _N. J. A. Sloane_, Dec 04 2011

%E Name edited by _M. F. Hasler_, Apr 22 2018