A106302 -id:A106302 - cp's OEIS frontend

A046738 Period of Fibonacci 3-step sequence A000073 mod n.

1, 4, 13, 8, 31, 52, 48, 16, 39, 124, 110, 104, 168, 48, 403, 32, 96, 156, 360, 248, 624, 220, 553, 208, 155, 168, 117, 48, 140, 1612, 331, 64, 1430, 96, 1488, 312, 469, 360, 2184, 496, 560, 624, 308, 440, 1209, 2212, 46, 416, 336, 620, 1248, 168

Offset: 1

David W. Wilson

Could also be called the tribonacci Pisano periods. [Carl R. White, Oct 05 2009]
Klaska notes that n=208919=59*3541 satisfies a(n) = a(n^2). - Michel Marcus, Mar 03 2016
39, 78, 273, 546 also satisfy a(n) = a(n^2). - Michel Marcus, Mar 07 2016

T. D. Noe [1..1000] + Jean-François Alcover [1001..2000] + Zhong Ziqian [2001..20000], Table of n, a(n) for n = 1..20000
Jirí Klaška, A search for Tribonacci-Wieferich primes, Acta Mathematica Universitatis Ostraviensis, vol. 16 (2008), issue 1, pp. 15-20.
Jirí Klaška, On Tribonacci-Wieferich primes, Fibonacci Quart. 46/47 (2008/2009), no. 4, 290-297.
Jirí Klaška, Tribonacci partition formulas modulo m, Acta Mathematica Sinica, English Series, March 2010, Volume 26, Issue 3, pp 465-476.
M. E. Waddill, Some properties of a generalized Fibonacci sequence modulo m, The Fibonacci Quarterly, vol. 16, no. 4, pp. 344-353 (1978).

Cf. A106302.

Cf. A001175.

a:= proc(n) local f, k, l; l:= ifactors(n)[2];
      if nops(l)<>1 then ilcm(seq(a(i[1]^i[2]), i=l))
    else f:= [0, 0, 1];
         for k do f:=[f[2], f[3], f[1]+f[2]+f[3] mod n];
                  if f=[0, 0, 1] then break fi
         od; k
      fi
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Aug 27 2023

Table[a = {0, 1, 1}; a = a0 = Mod[a, n]; k = 0; While[k++; s = a[[3]] + a[[2]] + a[[1]]; a = RotateLeft[a]; a[[-1]] = Mod[s, n]; a != a0]; k, {n, 100}] (* T. D. Noe, Aug 28 2012 *)

from itertools import count
def A046738(n):
    a = b = (0,0,1%n)
    for m in count(1):
        b = b[1:] + (sum(b) % n,)
        if a == b:
            return m # Chai Wah Wu, Feb 27 2022

a(3^k) = 13*3^(k-1) for k > 0. If a(p) != a(p^2) for p prime, then a(p^k) = p^(k-1)*a(p) for k > 0 [Waddill, 1978]. - Chai Wah Wu, Feb 25 2022

Let the prime factorization of n be p1^e1*...*pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek)) [Waddill, 1978]. - Avery Diep, Aug 26 2025

A106282 Primes p such that the polynomial x^3-x^2-x-1 mod p has no zeros; i.e., the polynomial is irreducible over the integers mod p.

Original entry on oeis.org

3, 5, 23, 31, 37, 59, 67, 71, 89, 97, 113, 137, 157, 179, 181, 191, 223, 229, 251, 313, 317, 331, 353, 367, 379, 383, 389, 433, 443, 449, 463, 467, 487, 509, 521, 577, 619, 631, 641, 643, 647, 653, 661, 691, 709, 719, 727, 751, 797, 823, 829, 839, 859, 881

Offset: 1

T. D. Noe, May 02 2005

nonn

This polynomial is the characteristic polynomial of the Fibonacci and Lucas 3-step sequences, A000073 and A001644.

Primes of the form 3x^2+2xy+4y^2 with x and y in Z. - T. D. Noe, May 08 2005

Vincenzo Librandi, Table of n, a(n) for n = 1..300
N. J. A. Sloane et al., Binary Quadratic Forms and OEIS (Index to related sequences, programs, references)
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number

Primes in A028952.
Cf. A106276 (number of distinct zeros of x^3-x^2-x-1 mod prime(n)), A106294, A106302 (period of Lucas and Fibonacci 3-step sequence mod prime(n)), A003631 (primes p such that x^2-x-1 is irreducible mod p).
For a list of sequences giving numbers and/or primes represented by binary quadratic forms, see the "Binary Quadratic Forms and OEIS" link.

t=Table[p=Prime[n]; cnt=0; Do[If[Mod[x^3-x^2-x-1, p]==0, cnt++ ], {x, 0, p-1}]; cnt, {n, 200}];Prime[Flatten[Position[t, 0]]]

forprime(p=2,1000,if(#polrootsmod(x^3-x^2-x-1,p)==0,print1(p,", ")));
/* Joerg Arndt, Jul 19 2012 */

A106279 Primes p such that the polynomial x^3-x^2-x-1 mod p has 3 distinct zeros.

Original entry on oeis.org

47, 53, 103, 163, 199, 257, 269, 311, 397, 401, 419, 421, 499, 587, 599, 617, 683, 757, 773, 863, 883, 907, 911, 929, 991, 1021, 1087, 1109, 1123, 1181, 1237, 1291, 1307, 1367, 1433, 1439, 1543, 1567, 1571, 1609, 1621, 1697, 1699, 1753, 1873, 1907, 2003

Offset: 1

T. D. Noe, May 02 2005

nonn

This polynomial is the characteristic polynomial of the Fibonacci and Lucas 3-step sequences, A000073 and A001644. The periods of the sequences A000073(k) mod p and A001644(k) mod p have length less than p. For a given p, let the zeros be a, b and c. Then A001644(k) mod p = (a^k+b^k+c^k) mod p. This sequence is the same as A033209 except for the initial term.

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

Cf. A106276 (number of distinct zeros of x^3-x^2-x-1 mod prime(n)), A106294, A106302 (periods of the Fibonacci and Lucas 3-step sequences mod prime(n)).

t=Table[p=Prime[n]; cnt=0; Do[If[Mod[x^3-x^2-x-1, p]==0, cnt++ ], {x, 0, p-1}]; cnt, {n, 500}];Prime[Flatten[Position[t, 3]]]

A154754 Ratio of the period and the reduced period of the Fibonacci 3-step sequence A000073 mod prime(n).

Original entry on oeis.org

1, 1, 1, 3, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 1, 1, 3, 1, 3, 1, 3, 1, 1, 3, 1, 3, 1, 3, 1, 1, 1, 1, 1, 3, 1, 3, 3, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 3, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 3

Offset: 1

T. D. Noe, Jan 15 2009

nonn

See A046737 for more information about the reduced period.

For the Fibonacci 3-step (tribonacci) sequence, only 1 and 3 appear. A116515 is the analogous sequence for Fibonacci numbers. Let the terms in the reduced period be denoted by R. When the ratio is 3, the full period can be written as R,aR,bR, where a and b are multipliers that are the two solutions of the equation x^2+x+1 = 0 (mod p). What order do the solutions appear as a and b? See A154755 and A154756 for the primes that produce ratios of 1 and 3, respectively. Observe that there are approximately three times as many 1's as 3's.

			The tribonacci sequence (starting with 1) mod 7 is 1,1,2,4,0,6,3,2,4, 2,1,0,3,4,0,0,4,4,1,2,0,3,5,1,2,1,4,0,5,2,0,0,2,2,4,1,0,5,6,4,1,4,2,0, 6,1,0,0, which has 3 pairs of 0-0 terms. Hence a(4)=3.

See the comments for the relationships with A116515, A154755, A154756.
See the formula section for the relationships with A106302, A154753, A386236.
Cf. A000073.
For the periods modulo all positive integers see A046737, A046738.

Table[p=Prime[i]; a={1,0,0}; a0=a; k=0; zeros=0; While[k++; s=Mod[Plus@@a,p]; a=RotateLeft[a]; a[[ -1]]=s; If[Rest[a]=={0,0}, zeros++ ]; a!=a0]; zeros, {i,200}]

a(n) = A106302(n) / A154753(n).

a(n) = A386236(prime(n)), where prime(n) is the n-th prime.

A106294 Period of the Lucas 3-step sequence A001644 mod prime(n).

Original entry on oeis.org

1, 13, 31, 48, 10, 168, 96, 360, 553, 140, 331, 469, 560, 308, 46, 52, 3541, 1860, 1519, 5113, 5328, 3120, 287, 8011, 3169, 680, 51, 1272, 990, 12883, 5376, 5720, 18907, 3864, 7400, 2850, 8269, 162, 9296, 2494, 32221, 10981, 36673, 4656, 3234, 198, 5565

Offset: 1

T. D. Noe, May 02 2005

nonn

This sequence differs from the corresponding Fibonacci sequence (A106302) at n=1 and 5 because these correspond to the primes 2 and 11, which are the prime factors of -44, the discriminant of the characteristic polynomial x^3-x^2-x-1. We have a(n) < prime(n) for the primes 2, 11 and A106279.

For a prime p, the period depends on the zeros of x^3-x^2-x-1 mod p. If there are 3 zeros, then the period is < p. If there are no zeros, then the period is p^2+p+1 or a simple fraction of p^2+p+1. Also note that the period can be prime, as for p=3, 5, 31, 59, 71, 89, 97, 157, 223. When the period is prime, the orbits have a simple structure. [From T. D. Noe, Sep 18 2008]

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

Cf. A106273, A106279, A106302.

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

a(n) = A106293(prime(n)).

A154753 Reduced period of the Fibonacci 3-step sequence A000073 mod prime(n).

Original entry on oeis.org

4, 13, 31, 16, 110, 56, 96, 120, 553, 140, 331, 469, 560, 308, 46, 52, 3541, 620, 1519, 5113, 1776, 1040, 287, 8011, 3169, 680, 17, 1272, 330, 12883, 1792, 5720, 18907, 1288, 7400, 950, 8269, 54, 9296, 2494, 32221, 10981, 36673, 1552, 3234, 66, 1855

Offset: 1

T. D. Noe, Jan 15 2009

nonn

The Fibonacci 3-step (tribonacci) sequence t(k) begins (with offset -2) 1,0,0. For a prime p, the reduced period r is the least number such that p divides both t(r-1) and t(r); i.e., "0,0" appears in the sequence mod p. The ratio of the period A106302 and the reduced period is either 1 or 3; see A154754.

			The tribonacci sequence (starting with 1) mod 7 begins with the 48 terms 1,1,2,4,0,6,3,2,4,2,1,0,3,4,0,0,4,4,1,2,0,3,5,1,2,1,4,0,5,2,0,0,2,2,4,1, 0,5,6,4,1,4,2,0,6,1,0,0. The first "0,0" terms occur at index 16. Hence a(4)=16.

D. W. Robinson, A note on linear recurrent sequences modulo m, Amer. Math. Monthly 73 (1966), 619-621.

Cf. A046737, A046738.

a(n) = A046738(prime(n)).

cp's OEIS Frontend

A046738 Period of Fibonacci 3-step sequence A000073 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A106282 Primes p such that the polynomial x^3-x^2-x-1 mod p has no zeros; i.e., the polynomial is irreducible over the integers mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A106279 Primes p such that the polynomial x^3-x^2-x-1 mod p has 3 distinct zeros.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A154754 Ratio of the period and the reduced period of the Fibonacci 3-step sequence A000073 mod prime(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A106294 Period of the Lucas 3-step sequence A001644 mod prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A154753 Reduced period of the Fibonacci 3-step sequence A000073 mod prime(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula