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

Author

David W. Wilson

Keywords

• nonn
• changed

Comments

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

Links

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

Crossrefs

Cf. A106302.

Cf. A001175.

Programs

Maple

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

Mathematica

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

Python

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

Formula

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