A106295 -id:A106295 - cp's OEIS frontend

A073817 Tetranacci numbers with different initial conditions: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) starting with a(0)=4, a(1)=1, a(2)=3, a(3)=7.

4, 1, 3, 7, 15, 26, 51, 99, 191, 367, 708, 1365, 2631, 5071, 9775, 18842, 36319, 70007, 134943, 260111, 501380, 966441, 1862875, 3590807, 6921503, 13341626, 25716811, 49570747, 95550687, 184179871, 355018116, 684319421, 1319068095, 2542585503

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Aug 12 2002

These tetranacci numbers follow the same pattern as Lucas and generalized tribonacci(A001644) numbers: Binet's formula is a(n) = r1^n + r2^n + r3^n + r4^n, with r1, r2, r3, r4 roots of the characteristic polynomial.

For n >= 4, a(n) is the number of cyclic sequences consisting of n zeros and ones that do not contain four consecutive ones provided the positions of the zeros and ones are fixed on a circle. This is proved in Charalambides (1991) and Zhang and Hadjicostas (2015). For example, a(4)=15 because only the sequences 1110, 1101, 1011, 0111, 0011, 0101, 1001, 1010, 0110, 1100, 0001, 0010, 0100, 1000, 0000 avoid four consecutive ones on a circle. (For n=1,2,3 the statement is still true provided we allow the sequence to wrap around itself on a circle. For example, a(2)=3 because only the sequences 00, 01, 10 avoid four consecutive ones when wrapped around on a circle.) - Petros Hadjicostas, Dec 18 2016

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
C. A. Charalambides, Lucas numbers and polynomials of order k and the length of the longest circular success run, The Fibonacci Quarterly, 29 (1991), 290-297.
Spiros D. Dafnis, Andreas N. Philippou, and Ioannis E. Livieris, An Alternating Sum of Fibonacci and Lucas Numbers of Order k, Mathematics (2020) Vol. 9, 1487.
Petros Hadjicostas, Cyclic Compositions of a Positive Integer with Parts Avoiding an Arithmetic Sequence, Journal of Integer Sequences, 19 (2016), #16.8.2.
Tony D. Noe and Jonathan Vos Post, Primes in Fibonacci n-step and Lucas n-step Sequences, J. of Integer Sequences, Vol. 8 (2005), Article 05.4.4
J. L. Ramírez and V. F. Sirvent, A Generalization of the k-Bonacci Sequence from Riordan Arrays, The Electronic Journal of Combinatorics, 22(1) (2015), #P1.38.
Yüksel Soykan, Gaussian Generalized Tetranacci Numbers, arXiv:1902.03936 [math.NT], 2019.
Yüksel Soykan, Tetranacci and Tetranacci-Lucas Quaternions, arXiv:1902.05868 [math.RA], 2019.
Yüksel Soykan, Summation Formulas for Generalized Tetranacci Numbers, Asian Journal of Advanced Research and Reports (2019) Vol. 7, No. 2, Article No. AJARR.52434, 1-12.
Yüksel Soykan, Properties of Generalized (r, s, t, u)-Numbers, Earthline J. of Math. Sci. (2021) Vol. 5, No. 2, 297-327.
Kai Wang, Identities, generating functions and Binet formula for generalized k-nacci sequences, 2020.
Kai Wang, Identities for generalized enneanacci numbers, Generalized Fibonacci Sequences (2020).
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number.
A. V. Zarelua, On Matrix Analogs of Fermat's Little Theorem, Mathematical Notes, vol. 79, no. 6, 2006, pp. 783-796. Translated from Matematicheskie Zametki, vol. 79, no. 6, 2006, pp. 840-855.
L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern '11..1', Math. Scientist, 40 (2015), 89-96.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1).

Cf. A000078, A001630, A001644, A000032, A106295 (Pisano periods). Two other versions: A001648, A074081.

a:=[4,1,3,7];; for n in [5..40] do a[n]:=a[n-1]+a[n-2]+a[n-3] +a[n-4]; od; a; # G. C. Greubel, Feb 19 2019

I:=[4,1,3,7]; [n le 4 select I[n] else Self(n-1) +Self(n-2) +Self(n-3) +Self(n-4): n in [1..40]]; // G. C. Greubel, Feb 19 2019

a[0]=4; a[1]=1; a[2]=3; a[3]=7; a[4]=15; a[n_]:= 2*a[n-1] -a[n-5]; Array[a, 34, 0]
CoefficientList[Series[(4-3x-2x^2-x^3)/(1-x-x^2-x^3-x^4), {x, 0, 40}], x]
LinearRecurrence[{1,1,1,1},{4,1,3,7},40] (* Harvey P. Dale, Jun 01 2015 *)

Vec((4-3*x-2*x^2-x^3)/(1-x-x^2-x^3-x^4) + O(x^40)) \\ Michel Marcus, Jan 29 2016

((4-3*x-2*x^2-x^3)/(1-x-x^2-x^3-x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Feb 19 2019

G.f.: (4 - 3*x - 2*x^2 - x^3)/(1 - x - x^2 - x^3 - x^4).
a(n) = 2*a(n-1) - a(n-5), with a(0)=4, a(1)=1, a(2)=3, a(3)=7, a(4)=15. - Vincenzo Librandi, Dec 20 2010
a(n) = A000078(n+2) + 2*A000078(n+1) + 3*A000078(n) + 4*A000078(n-1). - Advika Srivastava, Aug 22 2019
a(n) = 8*a(n-3) - a(n-5) - 2*a(n-6) - 4*a(n-7). - Advika Srivastava, Aug 25 2019
a(n) = Trace(M^n), where M is the 4 X 4 matrix [0, 0, 0, 1; 1, 0, 0, 1; 0, 1, 0, 1; 0, 0, 1, 1], the companion matrix to the monic polynomial x^4 - x^3 - x^2 - x - 1. It follows that the sequence satisfies the Gauss congruences: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for positive integers n and r and all primes p. See Zarelua. - Peter Bala, Dec 31 2022
a(n) = Sum_{r root of x^4-x^3-x^2-x-1} r^n. - Fabian Pereyra, Feb 28 2025

Typo in definition corrected by Vincenzo Librandi, Dec 20 2010

A106296 Period of the Lucas 4-step sequence A073817 mod prime(n).

Original entry on oeis.org

5, 26, 312, 342, 120, 84, 4912, 6858, 12166, 280, 61568, 1368, 240, 162800, 103822, 303480, 205378, 226980, 100254, 357910, 2664, 998720, 1157520, 9320, 368872, 1030300, 10608, 1225042, 2614040, 13874, 2048382, 4530768, 136, 772880, 3307948

Offset: 1

T. D. Noe, May 02 2005

nonn

This sequence is the same as the period of Fibonacci 4-step sequence (A000078) mod prime(n) except for n=103, which corresponds to the prime 563 because the discriminant of the characteristic polynomial x^4-x^3-x^2-x-1 is -563. We have a(n) < prime(n) for primes 563 and A106280.

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

Cf. A106273 (discriminant of the polynomial x^n-x^(n-1)-...-x-1), A106280 (primes p such that x^4-x^3-x^2-x-1 mod p has 4 distinct zeros), A106295.

n=4; 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) = A106295(prime(n)).

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

Ilya Gutkovskiy, Feb 16 2022

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

			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.

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

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

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

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)

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

A106289 Number of different orbit lengths of the 4-step recursion mod n.

Original entry on oeis.org

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

Offset: 1

T. D. Noe, May 02 2005

nonn

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

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

Cf. A106286 (orbits of 4-step sequences).

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

A193993 Number of zeros in the period of Fibonacci 4-step sequence A000078 mod n.

Original entry on oeis.org

1, 3, 9, 5, 72, 27, 49, 8, 12, 216, 11, 24, 7, 147, 36, 10, 336, 36, 361, 188, 231, 8, 529, 39, 80, 21, 21, 126, 11, 108, 1986, 14, 51, 1008, 636, 31, 34, 1083, 36, 152, 11, 693, 3786, 8, 24, 1587, 2209, 51, 56, 56, 1440, 19, 5832, 63, 33, 203, 1653, 9, 3481

Offset: 1

T. D. Noe, Aug 18 2011

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..200

Cf. A106295 (period of Lucas 4-step sequence).

n = 4; 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}]

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.

cp's OEIS Frontend

A073817 Tetranacci numbers with different initial conditions: a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4) starting with a(0)=4, a(1)=1, a(2)=3, a(3)=7.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

Extensions

A106296 Period of the Lucas 4-step sequence A073817 mod prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A106289 Number of different orbit lengths of the 4-step recursion mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A193993 Number of zeros in the period of Fibonacci 4-step sequence A000078 mod n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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