A210456 - OEIS

%I #69 Feb 16 2025 08:33:17

%S 1,24,39,78,312,2184,1092,240,273,26232,11553,9840,177144,14348904,

%T 21523359,10315734,48417720,16120104,15706236,5036466318,258149112,

%U 1162261464,141214768239,421900912158,8857200,2184,2271,28578504864,21938847432216,148698308091840

%N Period of the sequence of the digital roots of Fibonacci n-step numbers.

%C More precisely, start with 0,0,...,0,1 (with n-1 0's and a single 1); thereafter the next term is the digital root (A010888) of the sum of the previous n terms. This is a periodic sequence and a(n) is the length of the period.

%C Theorem: a(n) <= 9^n.

%C Conjecture: All entries >1 are divisible by 3.

%C Additional terms are a(242)=177144, a(243)=177879.

%C More: a(728)=1594320, a(729)=1596513, a(2186)=14348904, a(2187)=14355471, a(6560)=129140160, a(6561)=129159849, a(19682)=1162261464, a(19683)=1162320519. - _Hans Havermann_, Jan 30 2013, Feb 08 2013

%C The modulus-9 Pisano periods of Fibonacci numbers, k-th order sequences. - _Hans Havermann_, Feb 10 2013

%C Conjecture: a(3^n-1)=3^(2*n+1)-3, a(3^n)=3^(2*n+1)+3^(n+1)+3 - Fred W. Helenius (fredh(AT)ix.netcom.com), posting to MathFun, Feb 21 2013

%H Hiroaki Yamanouchi, <a href="/A210456/b210456.txt">Table of n, a(n) for n = 1..100</a>

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

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PisanoPeriod.html">Pisano Period</a>

%e Digital roots of Fibonacci numbers (A030132) are 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 9, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 9, 1, 1, 2, 3,... Thus the period is 24 (1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 9, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 9).

%p A210456:=proc(q,i)

%p local d,k,n,v;

%p v:=array(1..q);

%p for d from 1 to i do

%p   for n from 1 to d do v[n]:=0; od; v[d+1]:=1;

%p   for n from d+2 to q do v[n]:=1+((add(v[k],k=n-d-1..n-1)-1) mod 9);

%p     if add(v[k],k=n-d+1..n)=9*d and v[n-d]=1 then print(n-d); break;

%p fi; od; od; end:

%p A210456 (100000000,100);

%t f[n_] := f[n] = Block[{s = PadLeft[{1}, n], c = 1}, s = t = Nest[g, s, n]; While[t = g[t]; s != t, c++]; c]; g[lst_List] := Rest@Append[lst, 1 + Mod[-1 + Plus @@ lst, 9]]; Do[ Print[{n, f[n] // Timing}], {n, 100}]

%Y Cf. Fibonacci numbers, k-th order sequences, A000045 (Fibonacci numbers, k=2), A030132 (digital root, k=2), A001175 (Pisano periods, k=2), A000073 (tribonacci numbers, k=3), A222407 (digital roots, k=3), A046738 (Pisano periods, k=3), A029898 (Pitoun's sequence), A187772, A220555.

%Y Cf. also A010888.

%K nonn,base

%O 1,2

%A _Paolo P. Lava_, _Robert G. Wilson v_, Jan 21 2013

%E a(23) from _Hans Havermann_, Jan 30 2013

%E a(24) from _Hans Havermann_, Feb 18 2013

%E a(28) from _Robert G. Wilson v_, Feb 21 2013

%E a(29)-a(30) from _Hiroaki Yamanouchi_, May 04 2015