login
a(1) = a(2) = a(3) = a(4) = a(5) = a(6) = a(7) = a(8) = a(9) = 1 and for n>9: a(n) = a(n-8) + a(n-9).
7

%I #31 Aug 31 2024 23:28:46

%S 1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,3,4,4,4,4,4,4,4,5,7,8,8,8,8,8,8,9,

%T 12,15,16,16,16,16,16,17,21,27,31,32,32,32,32,33,38,48,58,63,64,64,64,

%U 65,71,86,106,121,127,128,128,129,136,157,192,227,248,255,256,257,265,293

%N a(1) = a(2) = a(3) = a(4) = a(5) = a(6) = a(7) = a(8) = a(9) = 1 and for n>9: a(n) = a(n-8) + a(n-9).

%C k=8 case of the family of sequences whose k=1 case is the Fibonacci sequence A000045, k=2 case is the Padovan sequence A000931 (offset so as to begin 1,1,1), k=3 case is A079398 (offset so as to begin 1,1,1,1), k=4 case is A103372, k=5 case is A103373, k=6 case is A103374 and k=7 case is A103375.

%C The general case for integer k>1 is defined: a(1) = a(2) = ... = a(k+1) and for n>(k+1) a(n) = a(n-k) + a(n-[k+1]).

%C For this k=8 case, the ratio of successive terms a(n)/a(n-1) approaches the unique positive root of the characteristic polynomial: x^9 - x - 1 = 0. This is the real constant (to 50 digits accuracy): 1.0850702454914508283368958640973142340506536310308 = A230162. Note that x = (1 + x)^(1/9) = (1 + (1 + (1 + ...)^(1/9))^(1/9))^(1/9).

%C The sequence of prime values in this k=8 case is A103386; The sequence of semiprime values in this k=8 case is A103396.

%D Zanten, A. J. van, "The golden ratio in the arts of painting, building and mathematics", Nieuw Archief voor Wiskunde, 4 (17) (1999) 229-245.

%H J.-P. Allouche and T. Johnson, <a href="http://www.math.jussieu.fr/~allouche/johnson2.pdf">Narayana's Cows and Delayed Morphisms</a>

%H Richard Padovan, <a href="http://www.nexusjournal.com/conferences/N2002-Padovan.html">Dom Hans van der Laan and the Plastic Number</a>.

%H E. S. Selmer, <a href="http://www.mscand.dk/article/view/10478/8499">On the irreducibility of certain trinomials</a>, Math. Scand., 4 (1956) 287-302.

%H J. Shallit, <a href="http://dx.doi.org/10.1016/0304-3975(88)90103-X">A generalization of automatic sequences</a>, Theoretical Computer Science, 61 (1988), 1-16.

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

%F G.f.: x*(1+x)*(1+x^2)*(1+x^4)/(1-x^8-x^9). - _R. J. Mathar_, Dec 14 2009

%F a(1)=1, a(2)=1, a(3)=1, a(4)=1, a(5)=1, a(6)=1, a(7)=1, a(8)=1, a(9)=1, a(n)=a(n-8)+a(n-9). - _Harvey P. Dale_, May 07 2015

%e a(93) = 1200 because a(93) = a(93-8) + a(93-9) = a(85) + a(84) = 642 + 558.

%t k = 8; Do[a[n] = 1, {n, k + 1}]; a[n_] := a[n] = a[n - k] + a[n - k - 1]; Array[a, 76]

%t LinearRecurrence[{0,0,0,0,0,0,0,1,1},{1,1,1,1,1,1,1,1,1},80] (* _Harvey P. Dale_, May 07 2015 *)

%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,0,0,0,0,0,0,0]^(n-1)*[1;1;1;1;1;1;1;1;1])[1,1] \\ _Charles R Greathouse IV_, Oct 03 2016

%Y Cf. A000045, A000931, A079398, A103372-A103375, A103377-A103380, A103386, A103396.

%K nonn,easy

%O 1,10

%A _Jonathan Vos Post_, Feb 05 2005

%E Edited by _Ray Chandler_, Feb 10 2005