cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-10 of 19 results. Next

A000073 Tribonacci numbers: a(n) = a(n-1) + a(n-2) + a(n-3) for n >= 3 with a(0) = a(1) = 0 and a(2) = 1.

Original entry on oeis.org

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064, 15902591, 29249425, 53798080, 98950096, 181997601, 334745777, 615693474, 1132436852
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The name "tribonacci number" is less well-defined than "Fibonacci number". The sequence A000073 (which begins 0, 0, 1) is probably the most important version, but the name has also been applied to A000213, A001590, and A081172. - N. J. A. Sloane, Jul 25 2024
Also (for n > 1) number of ordered trees with n+1 edges and having all leaves at level three. Example: a(4)=2 because we have two ordered trees with 5 edges and having all leaves at level three: (i) one edge emanating from the root, at the end of which two paths of length two are hanging and (ii) one path of length two emanating from the root, at the end of which three edges are hanging. - Emeric Deutsch, Jan 03 2004
a(n) is the number of compositions of n-2 with no part greater than 3. Example: a(5)=4 because we have 1+1+1 = 1+2 = 2+1 = 3. - Emeric Deutsch, Mar 10 2004
Let A denote the 3 X 3 matrix [0,0,1;1,1,1;0,1,0]. a(n) corresponds to both the (1,2) and (3,1) entries in A^n. - Paul Barry, Oct 15 2004
Number of permutations satisfying -k <= p(i)-i <= r, i=1..n-2, with k=1, r=2. - Vladimir Baltic, Jan 17 2005
Number of binary sequences of length n-3 that have no three consecutive 0's. Example: a(7)=13 because among the 16 binary sequences of length 4 only 0000, 0001 and 1000 have 3 consecutive 0's. - Emeric Deutsch, Apr 27 2006
Therefore, the complementary sequence to A050231 (n coin tosses with a run of three heads). a(n) = 2^(n-3) - A050231(n-3) - Toby Gottfried, Nov 21 2010
Convolved with the Padovan sequence = row sums of triangle A153462. - Gary W. Adamson, Dec 27 2008
For n > 1: row sums of the triangle in A157897. - Reinhard Zumkeller, Jun 25 2009
a(n+2) is the top left entry of the n-th power of any of the 3 X 3 matrices [1, 1, 1; 0, 0, 1; 1, 0, 0] or [1, 1, 0; 1, 0, 1; 1, 0, 0] or [1, 1, 1; 1, 0, 0; 0, 1, 0] or [1, 0, 1; 1, 0, 0; 1, 1, 0]. - R. J. Mathar, Feb 03 2014
a(n-1) is the top left entry of the n-th power of any of the 3 X 3 matrices [0, 0, 1; 1, 1, 1; 0, 1, 0], [0, 1, 0; 0, 1, 1; 1, 1, 0], [0, 0, 1; 1, 0, 1; 0, 1, 1] or [0, 1, 0; 0, 0, 1; 1, 1, 1]. - R. J. Mathar, Feb 03 2014
Also row sums of A082601 and of A082870. - Reinhard Zumkeller, Apr 13 2014
Least significant bits are given in A021913 (a(n) mod 2 = A021913(n)). - Andres Cicuttin, Apr 04 2016
The nonnegative powers of the tribonacci constant t = A058265 are t^n = a(n)*t^2 + (a(n-1) + a(n-2))*t + a(n-1)*1, for n >= 0, with a(-1) = 1 and a(-2) = -1. This follows from the recurrences derived from t^3 = t^2 + t + 1. See the example in A058265 for the first nonnegative powers. For the negative powers see A319200. - Wolfdieter Lang, Oct 23 2018
The term "tribonacci number" was coined by Mark Feinberg (1963), a 14-year-old student in the 9th grade of the Susquehanna Township Junior High School in Pennsylvania. He died in 1967 in a motorcycle accident. - Amiram Eldar, Apr 16 2021
Andrews, Just, and Simay (2021, 2022) remark that it has been suggested that this sequence is mentioned in Charles Darwin's Origin of Species as bearing the same relation to elephant populations as the Fibonacci numbers do to rabbit populations. - N. J. A. Sloane, Jul 12 2022

Examples

			G.f. = x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + 24*x^8 + 44*x^9 + 81*x^10 + ...

References

  • M. Agronomof, Sur une suite récurrente, Mathesis (Series 4), Vol. 4 (1914), pp. 125-126.
  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 47, ex. 4.
  • S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.2.
  • Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
  • J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A000045, A000078, A000213, A000931, A001590 (first differences, also a(n)+a(n+1)), A001644, A008288 (tribonacci triangle), A008937 (partial sums), A021913, A027024, A027083, A027084, A046738 (Pisano periods), A050231, A054668, A062544, A063401, A077902, A081172, A089068, A118390, A145027, A153462, A230216.
A057597 is this sequence run backwards: A057597(n) = a(1-n).
Row 3 of arrays A048887 and A092921 (k-generalized Fibonacci numbers).
Partitions: A240844 and A117546.
Cf. also A092836 (subsequence of primes), A299399 = A092835 + 1 (indices of primes).

Programs

  • GAP
    a:=[0,0,1];; for n in [4..40] do a[n]:=a[n-1]+a[n-2]+a[n-3]; od; a; # Muniru A Asiru, Oct 24 2018
  • Haskell
    a000073 n = a000073_list !! n
a000073_list = 0 : 0 : 1 : zipWith (+) a000073_list (tail
                          (zipWith (+) a000073_list $ tail a000073_list))
-- Reinhard Zumkeller, Dec 12 2011
  • Magma
    [n le 3 select Floor(n/3) else Self(n-1)+Self(n-2)+Self(n-3): n in [1..70]]; // Vincenzo Librandi, Jan 29 2016
  • Maple
    a:= n-> (<<0|1|0>, <0|0|1>, <1|1|1>>^n)[1,3]:
seq(a(n), n=0..40);  # Alois P. Heinz, Dec 19 2016
# second Maple program:
A000073:=proc(n) option remember; if n <= 1 then 0 elif n=2 then 1 else procname(n-1)+procname(n-2)+procname(n-3); fi; end; # N. J. A. Sloane, Aug 06 2018
  • Mathematica
    CoefficientList[Series[x^2/(1 - x - x^2 - x^3), {x, 0, 50}], x]
a[0] = a[1] = 0; a[2] = 1; a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3]; Array[a, 36, 0] (* Robert G. Wilson v, Nov 07 2010 *)
LinearRecurrence[{1, 1, 1}, {0, 0, 1}, 60] (* Vladimir Joseph Stephan Orlovsky, May 24 2011 *)
a[n_] := SeriesCoefficient[If[ n < 0, x/(1 + x + x^2 - x^3), x^2/(1 - x - x^2 - x^3)], {x, 0, Abs @ n}] (* Michael Somos, Jun 01 2013 *)
Table[-RootSum[-1 - # - #^2 + #^3 &, -#^n - 9 #^(n + 1) + 4 #^(n + 2) &]/22, {n, 0, 20}] (* Eric W. Weisstein, Nov 09 2017 *)
  • Maxima
    A000073[0]:0$
A000073[1]:0$
A000073[2]:1$
A000073[n]:=A000073[n-1]+A000073[n-2]+A000073[n-3]$
  makelist(A000073[n], n, 0, 40);  /* Emanuele Munarini, Mar 01 2011 */
  • PARI
    {a(n) = polcoeff( if( n<0, x / ( 1 + x + x^2 - x^3), x^2 / ( 1 - x - x^2 - x^3) ) + x * O(x^abs(n)), abs(n))}; /* Michael Somos, Sep 03 2007 */
  • PARI
    my(x='x+O('x^99)); concat([0, 0], Vec(x^2/(1-x-x^2-x^3))) \\ Altug Alkan, Apr 04 2016
  • PARI
    a(n)=([0,1,0;0,0,1;1,1,1]^n)[1,3] \\ Charles R Greathouse IV, Apr 18 2016, simplified by M. F. Hasler, Apr 18 2018
  • Python
    def a(n, adict={0:0, 1:0, 2:1}):
    if n in adict:
        return adict[n]
    adict[n]=a(n-1)+a(n-2)+a(n-3)
    return adict[n] # David Nacin, Mar 07 2012
from functools import cache
@cache
def A000073(n: int) -> int:
    if n <= 1: return 0
    if n == 2: return 1
    return A000073(n-1) + A000073(n-2) + A000073(n-3) # Peter Luschny, Nov 21 2022

Formula

G.f.: x^2/(1 - x - x^2 - x^3).
G.f.: x^2 / (1 - x / (1 - x / (1 + x^2 / (1 + x)))). - Michael Somos, May 12 2012
G.f.: Sum_{n >= 0} x^(n+2) *[ Product_{k = 1..n} (k + k*x + x^2)/(1 + k*x + k*x^2) ] = x^2 + x^3 + 2*x^4 + 4*x^5 + 7*x^6 + 13*x^7 + ... may be proved by the method of telescoping sums. - Peter Bala, Jan 04 2015
a(n+1)/a(n) -> A058265. a(n-1)/a(n) -> A192918.
a(n) = central term in M^n * [1 0 0] where M = the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 1 1]. (M^n * [1 0 0] = [a(n-1) a(n) a(n+1)].) a(n)/a(n-1) tends to the tribonacci constant, 1.839286755... = A058265, an eigenvalue of M and a root of x^3 - x^2 - x - 1 = 0. - Gary W. Adamson, Dec 17 2004
a(n+2) = Sum_{k=0..n} T(n-k, k), where T(n, k) = trinomial coefficients (A027907). - Paul Barry, Feb 15 2005
A001590(n) = a(n+1) - a(n); A001590(n) = a(n-1) + a(n-2) for n > 1; a(n) = (A000213(n+1) - A000213(n))/2; A000213(n-1) = a(n+2) - a(n) for n > 0. - Reinhard Zumkeller, May 22 2006
Let C = the tribonacci constant, 1.83928675...; then C^n = a(n)*(1/C) + a(n+1)*(1/C + 1/C^2) + a(n+2)*(1/C + 1/C^2 + 1/C^3). Example: C^4 = 11.444...= 2*(1/C) + 4*(1/C + 1/C^2) + 7*(1/C + 1/C^2 + 1/C^3). - Gary W. Adamson, Nov 05 2006
a(n) = j*C^n + k*r1^n + L*r2^n where C is the tribonacci constant (C = 1.8392867552...), real root of x^3-x^2-x-1=0, and r1 and r2 are the two other roots (which are complex), r1 = m+p*i and r2 = m-p*i, where i = sqrt(-1), m = (1-C)/2 (m = -0.4196433776...) and p = ((3*C-5)*(C+1)/4)^(1/2) = 0.6062907292..., and where j = 1/((C-m)^2 + p^2) = 0.1828035330..., k = a+b*i, and L = a-b*i, where a = -j/2 = -0.0914017665... and b = (C-m)/(2*p*((C-m)^2 + p^2)) = 0.3405465308... . - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), Jun 23 2007
a(n+1) = 3*c*((1/3)*(a+b+1))^n/(c^2-2*c+4) where a=(19+3*sqrt(33))^(1/3), b=(19-3*sqrt(33))^(1/3), c=(586+102*sqrt(33))^(1/3). Round to the nearest integer. - Al Hakanson (hawkuu(AT)gmail.com), Feb 02 2009
a(n) = round(3*((a+b+1)/3)^n/(a^2+b^2+4)) where a=(19+3*sqrt(33))^(1/3), b=(19-3*sqrt(33))^(1/3).. - Anton Nikonov
Another form of the g.f.: f(z) = (z^2-z^3)/(1-2*z+z^4). Then we obtain a(n) as a sum: a(n) = Sum_{i=0..floor((n-2)/4)} ((-1)^i*binomial(n-2-3*i,i)*2^(n-2-4*i)) - Sum_{i=0..floor((n-3)/4)} ((-1)^i*binomial(n-3-3*i,i)*2^(n-3-4*i)) with natural convention: Sum_{i=m..n} alpha(i) = 0 for m > n. - Richard Choulet, Feb 22 2010
a(n+2) = Sum_{k=0..n} Sum_{i=k..n, mod(4*k-i,3)=0} binomial(k,(4*k-i)/3)*(-1)^((i-k)/3)*binomial(n-i+k-1,k-1). - Vladimir Kruchinin, Aug 18 2010
a(n) = 2*a(n-2) + 2*a(n-3) + a(n-4). - Gary Detlefs, Sep 13 2010
Sum_{k=0..2*n} a(k+b)*A027907(n,k) = a(3*n+b), b >= 0 (see A099464, A074581).
a(n) = 2*a(n-1) - a(n-4), with a(0)=a(1)=0, a(2)=a(3)=1. - Vincenzo Librandi, Dec 20 2010
Starting (1, 2, 4, 7, ...) is the INVERT transform of (1, 1, 1, 0, 0, 0, ...). - Gary W. Adamson, May 13 2013
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + x + x^2)/( x*(4*k+3 + x + x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Sep 09 2013
a(n+2) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2*j,k)*binomial(j,k)*2^k. - Tony Foster III, Sep 08 2017
Sum_{k=0..n} (n-k)*a(k) = (a(n+2) + a(n+1) - n - 1)/2. See A062544. - Yichen Wang, Aug 20 2020
a(n) = A008937(n-1) - A008937(n-2) for n >= 2. - Peter Luschny, Aug 20 2020
From Yichen Wang, Aug 27 2020: (Start)
Sum_{k=0..n} a(k) = (a(n+2) + a(n) - 1)/2. See A008937.
Sum_{k=0..n} k*a(k) = ((n-1)*a(n+2) - a(n+1) + n*a(n) + 1)/2. See A337282. (End)
For n > 1, a(n) = b(n) where b(1) = 1 and then b(n) = Sum_{k=1..n-1} b(n-k)*A000931(k+2). - J. Conrad, Nov 24 2022
Conjecture: the congruence a(n*p^(k+1)) + a(n*p^k) + a(n*p^(k-1)) == 0 (mod p^k) holds for positive integers k and n and for all the primes p listed in A106282. - Peter Bala, Dec 28 2022
Sum_{k=0..n} k^2*a(k) = ((n^2-4*n+6)*a(n+1) - (2*n^2-2*n+5)*a(n) + (n^2-2*n+3)*a(n-1) - 3)/2. - Prabha Sivaramannair, Feb 10 2024
a(n) = Sum_{r root of x^3-x^2-x-1} r^n/(3*r^2-2*r-1). - Fabian Pereyra, Nov 23 2024

Extensions

Minor edits by M. F. Hasler, Apr 18 2018
Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A106302 Period of the Fibonacci 3-step sequence A000073 mod prime(n).

Original entry on oeis.org

4, 13, 31, 48, 110, 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

Views

Author

T. D. Noe, May 02 2005, Sep 18 2008

Keywords

Comments

This sequence differs from the corresponding Lucas sequence (A106294) 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 in A106279.

Links

Crossrefs

Cf. A106273, A106279, A106294, A046738.

Programs

  • Mathematica
    n=3; Table[p=Prime[i]; a=Join[{1},Table[0,{n-1}]]; 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}]
  • Python
    from itertools import count
from sympy import prime
def A106302(n):
    a = b = (0,)*2+(1 % (p:= prime(n)),)
    for m in count(1):
        b = b[1:] + (sum(b) % p,)
        if a == b:
            return m # Chai Wah Wu, Feb 27 2022

Formula

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

A046737 Reduced period of A000073 mod n.

Original entry on oeis.org

1, 4, 13, 8, 31, 52, 16, 16, 13, 124, 110, 104, 56, 16, 403, 32, 96, 52, 120, 248, 208, 220, 553, 208, 155, 56, 39, 16, 140, 1612, 331, 64, 1430, 96, 496, 104, 469, 120, 728, 496, 560, 208, 308, 440, 403, 2212, 46, 416, 112, 620, 1248, 56, 52, 156
Offset: 1

Views

Author

David W. Wilson

Keywords

Comments

See A046738 for the period of the tribonacci numbers mod n. The ratio of the period to the reduced period is either 1 or 3. Robinson discusses the relationship between the period and the reduced period of a sequence. For the Fibonacci numbers, the analogous sequence is A001177. - T. D. Noe, Jan 14 2009

Examples

			From _T. D. Noe_, Jan 14 2009: (Start)
The tribonacci sequence (starting with 1) mod 7 has a period that repeats
  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 pair of zeros occurs at the 16th term. Hence a(7)=16.
(End)

Links

Crossrefs

Cf. A000073, A001177, A046738, A154753 (restriction to prime indices), A386236.

Extensions

Improved name from T. D. Noe, Jan 14 2009

A104217 Period of Perrin (0,2,3,2,5,5,..., A001608) sequence mod n.

Original entry on oeis.org

1, 7, 13, 14, 24, 91, 48, 28, 39, 168, 120, 182, 183, 336, 312, 56, 288, 273, 180, 168, 624, 840, 22, 364, 120, 1281, 117, 336, 871, 2184, 993, 112, 1560, 2016, 48, 546, 1368, 1260, 2379, 168, 1723, 4368, 231, 840, 312, 154, 2257, 728, 336, 840, 3744, 2562
Offset: 1

Views

Author

Anthony C Robin, Mar 14 2005

Keywords

Comments

Analogy to A001175, Pisano periods (or Pisano numbers): period of Fibonacci numbers mod n AND to A046738 for Perrin sequence, where a(n)=a(n-2)+a(n-3)
It appears that the n such that n-1 divides a(n) is the set of primes of the form x^2+23*y^2 (A033217). The discriminant of the characteristic polynomial of the Perrin sequence is -23. - T. D. Noe, Feb 23 2007

Links

Crossrefs

Cf. A001175, A046738 and Perrin sequence A001608.

Programs

  • Mathematica
    Table[a={0,2,3}; a=a0=Mod[a, n]; k=0; While[k++; s=a[[2]]+a[[1]]; a=RotateLeft[a]; a[[ -1]]=Mod[s,n]; a!=a0]; k, {n,100}] (* T. D. Noe, Oct 10 2006 *)
  • Python
    from math import lcm
from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
def A104217(n):
    if n < 4:
        return (1,7,13)[n-1]
    f = factorint(n).items()
    if len(f) > 1:
        return lcm(*(A104217(a**b) for a,b in f))
    else:
        k,x = 1, (0,2,3)
        while x != (3,0,2):
            k += 1
            x = (x[1], x[2], (x[0]+x[1]) % n)
        return k # Chai Wah Wu, Apr 25 2025

Extensions

More terms from T. D. Noe, Oct 10 2006

A106293 Period of the Lucas 3-step sequence A001644 mod n.

Original entry on oeis.org

1, 1, 13, 4, 31, 13, 48, 8, 39, 31, 10, 52, 168, 48, 403, 16, 96, 39, 360, 124, 624, 10, 553, 104, 155, 168, 117, 48, 140, 403, 331, 32, 130, 96, 1488, 156, 469, 360, 2184, 248, 560, 624, 308, 20, 1209, 553, 46, 208, 336, 155, 1248, 168, 52, 117, 310, 48, 4680, 140
Offset: 1

Views

Author

T. D. Noe, May 02 2005

Keywords

Comments

This sequence can differ from the corresponding Fibonacci sequence (A046738) only when n is a multiple of 2 or 11 because the discriminant of the characteristic polynomial x^3-x^2-x-1 is -44. [Clarified by Avery Diep, Aug 22 2025]
a(n) divides A046738(n). - Avery Diep, Aug 22 2025

Links

Crossrefs

Cf. A046738 (period of Fibonacci 3-step sequence mod n), A106273 (discriminant of the polynomial x^n-x^(n-1)-...-x-1).

Programs

  • Mathematica
    n=3; Table[p=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}]

Formula

Let the prime factorization of n be p1^e1...pk^ek. Then a(n) = lcm(a(p1^e1), ..., a(pk^ek)).

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

Views

Author

T. D. Noe, Jan 15 2009

Keywords

Comments

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.

Examples

			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.

Crossrefs

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.

Programs

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

Formula

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

A351657 Period of the Fibonacci n-step sequence mod n.

Original entry on oeis.org

1, 3, 13, 10, 781, 728, 137257, 36, 273, 212784, 28531167061, 42640
Offset: 1

Views

Author

Ilya Gutkovskiy, Feb 16 2022

Keywords

Comments

From Chai Wah Wu, Feb 23 2022: (Start)
a(14) = 92269645680
a(15) = 4976066589192413
a(16) = 136
a(18) = 306281976
(End)

Examples

			For n = 4, take the tetranacci sequence (A000078), 0, 0, 0, 1, 1, 2, 4, 8, 15, 29, 56, 108, 208, ... (mod 4), which gives 0, 0, 0, 1, 1, 2, 0, 0, 3, 1, 0, 0, 0, 1, 1, 2, ... This repeats a pattern of length 10, so a(4) = 10.

Links

Crossrefs

Cf. A000040, A001039, A001175, A007582, A046738, A106295, A106303.

Programs

  • Python
    from math import lcm
from itertools import count
from sympy import factorint
def f(n,pe): # period of the Fibonacci n-step sequence mod pe
    a = b = (0,)*(n-1)+(1%pe,)
    s = 1 % pe
    for m in count(1):
        b, s = b[1:] + (s,), (s+s-b[0]) % pe
        if a == b:
            return m
def A351657(n): return 1 if n == 1 else lcm(*(f(n,p**e) for p, e in factorint(n).items())) # Chai Wah Wu, Feb 23-27 2022

Formula

From Chai Wah Wu, Feb 22 2022: (Start)
Conjecture 1: a(p) = (p^p-1)/(p-1) for p prime, i.e., a(A000040(n)) = A001039(n).
Conjecture 2: a(2^k) = 2^(k-1)*(1+2^k) = A007582(k).
Conjecture 3 (which implies Conjectures 1 and 2): a(p^k) = (p^(p*k)-1)*p^(k-1)/(p^k-1) for k > 0 and prime p.
(End)

Extensions

a(11)-a(12) from Chai Wah Wu, Feb 22 2022

A386236 Ratio of the period and the reduced period of the Fibonacci 3-step sequence A000073 mod n.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 3, 1, 1, 1, 3, 3, 1, 1, 1, 3, 3, 1, 3, 1, 1, 1, 1, 3, 3, 3, 1, 1, 1, 1, 1, 1, 3, 3, 1, 3, 3, 1, 1, 3, 1, 1, 3, 1, 1, 1, 3, 1, 1, 3, 1, 3, 1, 3, 3, 1, 1, 1, 3, 1, 3, 1, 3, 1, 1, 1, 1, 3, 1, 3, 3, 1, 1, 3, 3, 3, 3, 1, 3, 1, 1, 3, 1, 1, 1, 1, 1, 3, 3, 1, 1, 1, 3, 1, 1, 3, 3, 1, 1, 1, 3, 3, 3
Offset: 1

Views

Author

Peter Munn, Jul 16 2025

Keywords

Comments

The period is A046738(n) and the reduced period is A046737(n).
See also the information in A154754 and A046737.

Links

Crossrefs

Cf. A000073, A046737, A046738.
The equivalent sequence for Fibonacci numbers is A001176.
Cf. A060839 (differs first at n=31), A154754 (restriction to prime indices).

Formula

a(n) = A046738(n)/A046737(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

Views

Author

T. D. Noe, Jan 15 2009

Keywords

Comments

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.

Examples

			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.

Links

Crossrefs

Cf. A046737, A046738.

Formula

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

A175289 Pisano period of A002605 modulo n.

Original entry on oeis.org

1, 1, 3, 1, 24, 3, 48, 1, 9, 24, 10, 3, 12, 48, 24, 1, 144, 9, 180, 24, 48, 10, 22, 3, 120, 12, 27, 48, 840, 24, 320, 1, 30, 144, 48, 9, 36, 180, 12, 24, 280, 48, 308, 10, 72, 22, 46, 3, 336, 120, 144, 12, 936, 27, 120, 48, 180, 840, 29, 24, 60, 320, 144, 1, 24, 30, 1122, 144
Offset: 1

Views

Author

R. J. Mathar, Mar 24 2010

Keywords

Comments

a(79)=6240. [John W. Layman, Aug 10 2010]

Examples

			Reading 0, 1, 2, 6, 16, 44, 120, 328, 896, 2448,.. modulo 12 gives 0, 1, 2, 6, 4, 8, 0, 4, 8, 0, 4, 8 ,.. with period length a(n=12)= 3.

Links

Crossrefs

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

Programs

  • Mathematica
    a={1};For[n=2,n<=80,n++,{x={{0,1}}; t={1,1}; While[ !MemberQ[x,t], {xl = x[[ -1]]; AppendTo[x,t]; t={Mod[2*(t[[1]]+xl[[1]]),n], Mod[2*(t[[2]] + xl[[2]]),n]};}]; p = Flatten[Position[x,t]][[1]]; AppendTo[a, Length[x] - p+1];}]; Print[a]; (* John W. Layman, Aug 10 2010 *)

Extensions

Terms beyond a(28)=48 from John W. Layman, Aug 10 2010
Showing 1-10 of 19 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.