cp's OEIS Frontend

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

%I A104144 #75 Feb 16 2025 08:32:56
%S A104144 0,0,0,0,0,0,0,0,1,1,2,4,8,16,32,64,128,256,511,1021,2040,4076,8144,
%T A104144 16272,32512,64960,129792,259328,518145,1035269,2068498,4132920,
%U A104144 8257696,16499120,32965728,65866496,131603200,262947072,525375999,1049716729,2097364960
%N A104144 a(n) = Sum_{k=1..9} a(n-k); a(8) = 1, a(n) = 0 for n < 8.
%C A104144 Sometimes called the Fibonacci 9-step numbers.
%C A104144 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 A104144 The offset for this sequence is fairly arbitrary. - _N. J. A. Sloane_, Feb 27 2009
%H A104144 T. D. Noe, <a href="/A104144/b104144.txt">Table of n, a(n) for n = 0..208</a>
%H A104144 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 A104144 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 A104144 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 A104144 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Fibonaccin-StepNumber.html">Fibonacci n-Step Number</a>
%H A104144 <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 A104144 a(n) = Sum_{k=1..9} a(n-k) for n > 8, a(8) = 1, a(n) = 0 for n=0..7.
%F A104144 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 A104144 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 A104144 From _N. J. A. Sloane_, Dec 04 2011: (Start)
%F A104144 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 A104144 Let c = -b^8/g'(b) = 0.00099310812055463178382193226558248643030626601288701...
%F A104144 Then a(n) is the nearest integer to c/b^n. (End)
%p A104144 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 A104144 a={1, 0, 0, 0, 0, 0, 0, 0, 0}; Table[s=Plus@@a; a=RotateLeft[a]; a[[ -1]]=s, {n, 50}]
%t A104144 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 A104144 With[{nn=9},LinearRecurrence[Table[1,{nn}],Join[Table[0,{nn-1}],{1}],50]] (* _Harvey P. Dale_, Aug 17 2013 *)
%o A104144 (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 A104144 (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 A104144 Cf. A000045, A000073, A000078, A001591, A001592, A066178, A079262 (Fibonacci n-step numbers).
%Y A104144 Cf. A255529 (Indices of primes in this sequence).
%K A104144 nonn,easy
%O A104144 0,11
%A A104144 Jean Lefort (jlefort.apmep(AT)wanadoo.fr), Mar 07 2005
%E A104144 Edited by _N. J. A. Sloane_, Aug 15 2006 and Nov 11 2006
%E A104144 Incorrect formula deleted by _N. J. A. Sloane_, Dec 04 2011
%E A104144 Name edited by _M. F. Hasler_, Apr 22 2018