A046738 -id:A046738 - cp's OEIS frontend

A193991 Number of zeros in the period of Fibonacci 3-step sequence A000073 mod n.

1, 2, 4, 3, 6, 8, 12, 4, 9, 12, 10, 12, 18, 9, 24, 4, 5, 18, 27, 18, 48, 10, 24, 16, 10, 12, 15, 9, 5, 48, 13, 6, 40, 5, 72, 27, 16, 18, 72, 24, 14, 36, 10, 15, 54, 48, 5, 16, 30, 20, 20, 12, 5, 30, 60, 9, 108, 4, 60, 72, 45, 26, 36, 10, 108, 40, 19, 5, 96

Offset: 1

T. D. Noe, Aug 18 2011

nonn

T. D. Noe, Table of n, a(n) for n = 1..1000

Cf. A046738.

n = 3; Table[a = Join[{1}, Table[0, {n - 1}]]; a = Mod[a, i]; a0 = a; k = 0; zeros = 0; While[k++; s = Mod[Plus @@ a, i]; a = RotateLeft[a]; If[s == 0, zeros++]; a[[n]] = s; a != a0]; zeros, {i, 100}]

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

Original entry on oeis.org

1, 24, 39, 78, 312, 2184, 1092, 240, 273, 26232, 11553, 9840, 177144, 14348904, 21523359, 10315734, 48417720, 16120104, 15706236, 5036466318, 258149112, 1162261464, 141214768239, 421900912158, 8857200, 2184, 2271, 28578504864, 21938847432216, 148698308091840

Offset: 1

Paolo P. Lava, Robert G. Wilson v, Jan 21 2013

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.
Theorem: a(n) <= 9^n.
Conjecture: All entries >1 are divisible by 3.
Additional terms are a(242)=177144, a(243)=177879.
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
The modulus-9 Pisano periods of Fibonacci numbers, k-th order sequences. - Hans Havermann, Feb 10 2013
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

			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).

Hiroaki Yamanouchi, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Pisano Period

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.

Cf. also A010888.

A210456:=proc(q,i)
local d,k,n,v;
v:=array(1..q);
for d from 1 to i do
  for n from 1 to d do v[n]:=0; od; v[d+1]:=1;
  for n from d+2 to q do v[n]:=1+((add(v[k],k=n-d-1..n-1)-1) mod 9);
    if add(v[k],k=n-d+1..n)=9*d and v[n-d]=1 then print(n-d); break;
fi; od; od; end:
A210456 (100000000,100);

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}]

a(23) from Hans Havermann, Jan 30 2013
a(24) from Hans Havermann, Feb 18 2013
a(28) from Robert G. Wilson v, Feb 21 2013
a(29)-a(30) from Hiroaki Yamanouchi, May 04 2015

A106288 Number of different orbit lengths of the 3-step recursion mod n.

Original entry on oeis.org

1, 3, 2, 4, 2, 6, 3, 5, 3, 6, 4, 8, 3, 6, 4, 6, 3, 9, 3, 8, 6, 8, 2, 10, 3, 5, 4, 8, 3, 12, 2, 7, 8, 5, 6, 12, 2, 6, 6, 10, 3, 12, 3, 11, 6, 6, 3, 12, 5, 9, 6, 7, 3, 12, 8, 9, 6, 6, 2, 16, 3, 6, 7, 8, 6, 16, 2, 6, 4, 12, 2, 15, 3, 6, 6, 8, 10, 10, 3, 12, 5, 5, 3, 16, 6, 7, 6, 14, 2, 18, 6, 8, 4, 6, 6

Offset: 1

T. D. Noe, May 02 2005

nonn

Consider the 3-step recursion x(k)=x(k-1)+x(k-2)+x(k-3) mod n. For any of the n^3 initial conditions x(1), x(2) and x(3) in Zn, the recursion has a finite period. Each of these n^3 vectors belongs to exactly one orbit. In general, there are only a few different orbit lengths for each n. For n=8, there are 5 different lengths: 1, 2, 4, 8 and 16. The maximum possible length of an orbit is A046738(n), the period of the Fibonacci 3-step sequence mod n.

Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.

Cf. A106285 (orbits of 3-step sequences), A106307 (primes that yield a simple orbit structure in 3-step recursions).

A175290 Pisano period of A030195 modulo n.

Original entry on oeis.org

1, 3, 1, 3, 4, 3, 42, 6, 1, 12, 120, 3, 84, 42, 4, 12, 16, 3, 90, 12, 42, 120, 176, 6, 20, 84, 1, 42, 280, 12, 480, 24, 120, 48, 84, 3, 36, 90, 84, 12, 40, 42, 42, 120, 4, 528, 46, 12, 294, 60, 16, 84, 2808, 3, 120, 42, 90, 840, 58, 12, 310, 480, 42, 48, 84, 120, 33, 48, 176, 84, 5040, 6, 888, 36, 20, 90, 840, 84, 39, 12

Offset: 1

R. J. Mathar, Mar 24 2010

nonn

			Reading 0, 1, 3, 12, 45, 171, 648, 2457, 9315, 35316, 133893 .. modulo n=3 gives 0, 1, 0, 0, 0, 0, 0, .. with period length a(n=3)= 1.
Reading modulo n=6 gives 0, 1, 3, 0, 3, 3, 0, 3, 3 with period length a(n=6)=3.

Cf. A001175, A046738, A175181 - A175185, A175286.

A175291 Pisano period of A006130 modulo n.

Original entry on oeis.org

1, 3, 1, 6, 24, 3, 24, 6, 3, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, 24, 120, 22, 6, 120, 156, 9, 24, 28, 24, 240, 24, 120, 48, 24, 6, 171, 90, 156, 24, 336, 24, 42, 120, 24, 66, 736, 12, 168, 120, 16, 156, 52, 9, 120, 24, 90, 84, 3480, 24, 20, 240, 24, 48, 312, 120, 748, 48, 22, 24, 5040, 6, 888, 171, 120, 90, 120, 156, 39

Offset: 1

R. J. Mathar, Mar 24 2010

nonn

			Reading 0, 1, 1, 4, 7, 19, 40, 97, 217, 508, 1159, 2683, 6160, 14209, ... modulo n=7 gives 0, 1, 1, 4, 0, 5, 5, 6, 0, 4, 4, 2, 0, 6, 6, 3, 0, 2, 2, 1, 0, 3, 3, 5, 0, 1, 1, 4, 0, 5, 5, 6, 0, 4, 4, 2, 0, 6, 6, 3, 0, ... with period a(n=7)=24.

Cf. A001175, A046738, A175181, A175182, A175183, A175184, A175185, A175286.

a(9) corrected by R. J. Mathar, Apr 18 2010

A181190 Maximal length of chain-addition sequence mod 10 with window of size n.

Original entry on oeis.org

1, 60, 124, 1560, 4686, 1456, 18744, 585936, 4882810, 212784

Offset: 1

Alexander Dashevsky (atanvarnoalda(AT)gmail.com), Oct 10 2010

Chain addition mod 10 with window n: take an n-digit 'seed'. Take the sum of its digits mod 10 and append to the seed. Repeat with the last n digits of the string, until the seed appears again.
This sequence shows the lengths of the longest sequences for different window sizes.
a(1)-a(10) all occur for seed 1 (among others). If this is always true, the sequence continues: 406224, 12695306, 4272460934, 380859180, 122070312496, 518798826, 3433227539058. - Lars Blomberg, Feb 12 2013
Comment from Michel Lagneau, Jan 20 2017, edited by N. J. A. Sloane, Jan 24 2017: (Start)
If seed 1 is always as good as or better than any other, as seems likely, then this sequence has the following alternative description.
Consider the n initial terms of an infinite sequence S(k, n) of decimal digits given by 0, 0,..., 0, 1. The succeeding terms are given by the final digits in the sum of the n immediately preceding terms. The sequence lists the period of each sequence corresponding to n = 2, 3, ...
a(2) = period of A000045 mod 10 (Fibonacci numbers mod 10) = A001175(10).
a(3) = period of A000073 mod 10 (tribonacci numbers mod 10) = A046738(10).
a(4) = period of A000078 mod 10 (tetranacci numbers mod 10) = A106295(10).
a(5) = period of A001591 mod 10 (pentanacci numbers mod 10) = A106303(10).
a(6) = period of A001592 mod 10 (hexanacci numbers mod 10).
a(7) = period of A122189 mod 10 (heptanacci numbers mod 10).
a(8) = period of A079262 mod 10 (octanacci numbers mod 10).
a(4) = 1560 because the four initial terms 0, 0, 0, 1 => S(k, 4) = 0, 0, 0, 1, 1, 2, 4, 8, 5, 9, 6, 8, 8, 1, 3, 0, 2, 6, 1, 9, 8, ... (tetranacci numbers mod 10). This sequence is periodic with period 1560:
S(1560 + 1, 4) = S(1, 4) = 0,
S(1560 + 2, 4) = S(2, 4) = 0,
S(1560 + 3, 4) = S(3, 4) = 0,
S(1560 + 4, 4) = S(4, 4) = 1.
(End)

			For n=2, the longest sequence begins with '01' (among others):
01123583145943707741561785381909987527965167303369549325729101.
It is 60 digits long (not counting the second '01' at the end).
For n=3, one of the longest sequences begins again with '001':
00112473441944756893025746770415061742394699425184352079627546556679289964992013
48570291225960516297849144970639807524172091001 (124 digits long without the second '001').

Cf. A000045, A000073, A000078, A001591, A001592, A003893, A079262, A122189

a(8)-a(10) from Lars Blomberg, Feb 12 2013

A335534 a(n) = tribonacci(n) modulo Fibonacci(n).

Original entry on oeis.org

0, 0, 1, 2, 4, 7, 0, 3, 10, 26, 60, 130, 38, 173, 485, 175, 977, 273, 2789, 2065, 336, 15149, 22718, 39800, 5226, 54214, 2323, 251416, 418400, 93831, 977776, 1518664, 261912, 5208104, 2557037, 3549042, 21177270, 11203146, 36247269, 87596844, 44950918, 261069681

Offset: 1

Richard Peterson, Jun 12 2020

nonn

a(n) is congruent to tribonacci(n) modulo k if Fibonacci(n) is divisible by k, although the converse does not hold.

			For n=10, since tribonacci(10)=81 and Fibonacci(10)=55, a(10)=81 modulo 55 = 26.

Alois P. Heinz, Table of n, a(n) for n = 1..2000

Cf. A000073, A000045, A001177, A133021, A046738.

a:= n-> (<<0|1|0>, <0|0|1>, <1|1|1>>^n)[1, 3] mod (<<0|1>, <1|1>>^n)[1, 2]:
seq(a(n), n=1..45);  # Alois P. Heinz, Aug 19 2020

m = 42; Mod[LinearRecurrence[{1, 1, 1}, {0, 1, 1}, m], Array[Fibonacci, m]] (* Amiram Eldar, Aug 19 2020 *)

t(n) = ([0, 1, 0; 0, 0, 1; 1, 1, 1]^n)[1, 3]; \\ A000073
a(n) = t(n) % fibonacci(n); \\ Michel Marcus, Aug 19 2020

A351889 Table T(n,k) read by downward antidiagonals: period of n-step Fibonacci numbers mod k, n >= 1, k >= 1.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 6, 13, 5, 1, 1, 20, 8, 26, 6, 1, 1, 24, 31, 10, 104, 7, 1, 1, 16, 52, 312, 12, 728, 8, 1, 1, 12, 48, 130, 781, 14, 364, 9, 1, 1, 24, 16, 342, 312, 208, 16, 80, 10, 1, 1, 60, 39, 20, 2801, 728, 9372, 18, 91, 11, 1, 1, 10, 124, 78, 24, 342, 728, 195312

Offset: 1

Chai Wah Wu, Feb 24 2022

			Table T(n,k) starts:
  1   1     1   1       1      1          1   1      1        1
  1   3     8   6      20     24         16  12     24       60
  1   4    13   8      31     52         48  16     39      124
  1   5    26  10     312    130        342  20     78     1560
  1   6   104  12     781    312       2801  24    312     4686
  1   7   728  14     208    728        342  28   2184     1456
  1   8   364  16    9372    728     137257  32   1092    18744
  1   9    80  18  195312    720      13680  36    240   585936
  1  10    91  20  488281    910    5764800  40    273  4882810
  1  11  8744  22   19344  96184      19152  44  26232   212784
  1  12  3851  24  406224  46212  109531200  48  11553   406224

Chai Wah Wu, Table of n, a(n) for n = 1..226
M. E. Waddill, Some properties of a generalized Fibonacci sequence modulo m, The Fibonacci Quarterly, vol. 16, no. 4, pp. 344-353 (1978).
Marcellus E. Waddill, Some Properties of the Tetranacci Sequence Modulo m, The Fibonacci Quarterly, vol. 30, no. 3, 232-238 (1992).
D. D. Wall, Fibonacci Series Modulo m, The American Mathematical Monthly, vol. 67, no. 6, pp. 525-532, (1960).
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Pisano Period

Cf. A000045, A001175, A046738, A106295, A106303, A337212, A351657 (diagonal).

from functools import lru_cache
from math import lcm
from itertools import count
from sympy import factorint
@lru_cache(maxsize=None)
def A351889_T(n,k): # computes the period of the n-step Fibonacci sequence mod k
    if len(fs := factorint(k)) <= 1:
        a = b = (0,)*(n-1)+(1 % k,)
        s = 1 % k
        for m in count(1):
            b, s = b[1:] + (s,), (s + s - b[0]) % k
            if a == b:
                return m
    else:
        return lcm(*(A351889_T(n,p**e) for p, e in fs.items()))

T(1,k) = T(n,1) = 1.
T(2,k) = A001175(k).
T(3,k) = A046738(k).
T(4,k) = A106295(k) for k not a multiple of 563.
T(5,k) = A106303(k).
T(n,2) = n + 1 for n > 1.
T(n,3) = A337212(n).
T(n,n) = A351657(n).
T(n,p_1^e_1*...*p_m^e_m) = lcm(T(n,p_1^e_1),...,T(n,p_m^e_m)) for p_i distinct primes.
Conjecture 1: T(n,2^m) = (n+1)*2^(m-1) for n > 1.
Conjecture 2: For p prime, if T(n,p) != T(n,p^2) then T(n,p^k) = p^(k-1)T(n,p).
Conjecture 2 is true for n = 2, n = 3 and n = 4 (see [Wall, 1960], [Waddill, 1978] and [Waddill, 1992] resp.). It is easy to show that T(n,4) != n+1 for all n, and thus Conjecture 2 implies Conjecture 1.
Conjecture 3: T(p^m,p^k) = (p^(pm)-1)*p^(k-1)/(p^m-1) for p prime and k, m > 0.

A166038 Period of A022405 mod n.

Original entry on oeis.org

1, 3, 12, 18, 30, 12, 42, 18, 24, 30, 48, 36, 42, 42, 60, 36, 102, 24, 78, 90, 84, 48, 24, 36, 30, 42, 72, 126, 84, 60, 312, 72, 48, 102, 210, 72, 84, 78, 84, 90, 48, 84, 66, 144, 120, 24, 18, 36, 42, 30, 204, 126, 276, 72, 240, 126, 156, 84, 144, 180, 444, 312, 168, 144

Offset: 1

Carl R. White, Oct 05 2009

Pisano-style numbers for the recurrence b(n) = n for 0 <= n <= 2, otherwise b(n) = b(n-1)*b(n-2) - b(n-3); that is, the sequence b(n) = A022405(n+1).

Eric Weisstein's World of Mathematics, Pisano period.
Wikipedia, Pisano period.

Cf. A001175, A022405, A046738.

/* GNU bc */ define p(m){auto os,a,b,c,d,k;if(m<3)return 2*m-1;os=scale;scale=0;a=0;b=1;c=2;k=0;while(1){d=(c*b+m-a)%m;a=b;b=c;c=d;k+=1;if(a==0&&b==1&&c==2)break};scale=os;return k};for(i=1;i<=200;i++)print p(i),",";print"\n"

cp's OEIS Frontend

A193991 Number of zeros in the period of Fibonacci 3-step sequence A000073 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A106288 Number of different orbit lengths of the 3-step recursion mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

A175290 Pisano period of A030195 modulo n.

Views

Author

Keywords

Examples

Crossrefs

A175291 Pisano period of A006130 modulo n.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A181190 Maximal length of chain-addition sequence mod 10 with window of size n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A335534 a(n) = tribonacci(n) modulo Fibonacci(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A351889 Table T(n,k) read by downward antidiagonals: period of n-step Fibonacci numbers mod k, n >= 1, k >= 1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A166038 Period of A022405 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

bc