A000073 -id:A000073 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

A337286 a(n) = Sum_{i=0..n} i^2*T(i)^2, where T(i) = A000073(i) is the i-th tribonacci number.

Original entry on oeis.org

0, 0, 4, 13, 77, 477, 2241, 10522, 47386, 204202, 860302, 3546623, 14357567, 57286271, 225714755, 879795380, 3397426356, 13012405492, 49478890936, 186932228945, 702169068945, 2623863676449, 9758799153349, 36140284390030, 133317609306766, 490032600916766, 1795262239190210, 6557012850772931

Offset: 0

N. J. A. Sloane, Sep 12 2020

nonn

R. Schumacher, Explicit formulas for sums involving the squares of the first n Tribonacci numbers, Fib. Q., 58:3 (2020), 194-202. (Note that this paper uses an offset for the tribonacci numbers that is different from that used in A000073.)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7,-9,-7,-56,96,108,252,-162,-114,-318,126,-16,136,-36,12,-21,3,-1,1).

Cf. A000073, A085697, A337282, A337283, A337284, A337285.

R:=PowerSeriesRing(Integers(), 40); [0,0] cat Coefficients(R!( x^2*(4-15*x+22*x^2+83*x^3-90*x^4+11*x^5-128*x^6-207*x^7-224*x^8-233*x^9-162*x^10- 147*x^11-58*x^12-3*x^13-4*x^14-x^15)/((1-x)*(1+x+x^2-x^3)^3*(1-3*x-x^2-x^3)^3) )); // G. C. Greubel, Nov 22 2021

T[n_]:= T[n]= If[n<2, 0, If[n==2, 1, T[n-1] +T[n-2] +T[n-3]]]; (* A000073 *)
A337286[n_]:= Sum[j^2*T[j]^2, {j,0,n}];
Table[A337286[n], {n, 0, 50}] (* G. C. Greubel, Nov 22 2021 *)

@CachedFunction
def T(n): # A000073
    if (n<2): return 0
    elif (n==2): return 1
    else: return T(n-1) +T(n-2) +T(n-3)
def A337286(n): return sum( j^2*T(j)^2 for j in (0..n) )
[A337286(n) for n in (0..40)] # G. C. Greubel, Nov 22 2021

G.f.: x^2*(4 - 15*x + 22*x^2 + 83*x^3 - 90*x^4 + 11*x^5 - 128*x^6 - 207*x^7 - 224*x^8 - 233*x^9 - 162*x^10 - 147*x^11 - 58*x^12 - 3*x^13 - 4*x^14 - x^15)/((1-x)*(1 + x + x^2 - x^3)^3*(1 - 3*x - x^2 - x^3)^3). - G. C. Greubel, Nov 22 2021

A349904 Inverse Euler transform of the tribonacci numbers A000073.

Original entry on oeis.org

0, 0, 1, 1, 2, 3, 6, 10, 18, 31, 56, 96, 172, 299, 530, 929, 1646, 2893, 5126, 9044, 16028, 28362, 50328, 89249, 158598, 281830, 501538, 892857, 1591282, 2837467, 5064334, 9044023, 16163946, 28906213, 51729844, 92628401, 165967884, 297541263, 533731692, 957921314

Offset: 1

Peter Luschny, Dec 05 2021

nonn

Column k=2 of A349802.
Cf. A000073, A057597 (tribonacci numbers for n <= 0), A006206 and A060280.
Cf. A349903, A349977.

read transforms;  # https://oeis.org/transforms.txt
arow := len -> EULERi([seq(A000073(n), n = 0..len)]): arow(39);
# second Maple program:
t:= n-> (<<0|1|0>, <0|0|1>, <1|1|1>>^n)[1, 3]:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(binomial(a(i)+j-1, j)*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= proc(n) option remember; t(n-1)-b(n, n-1) end:
seq(a(n), n=1..40);  # Alois P. Heinz, Dec 05 2021

(* EulerInvTransform is defined in A022562. *)
EulerInvTransform[LinearRecurrence[{1, 1, 1}, {0, 0, 1}, 40]]

InvEulerT(v)={my(p=log(1+x*Ser(v))); dirdiv(vector(#v,n,polcoef(p,n)), vector(#v,n,1/n))}
seq(n) = InvEulerT(Vec(x^2/(1 - x - x^2 - x^3) + O(x^n), -n)) \\ Andrew Howroyd, Dec 05 2021

# After the Maple program of Alois P. Heinz.
from functools import cache
from math import comb
def binomial(n, k):
    if n == -1: return 1
    return comb(n, k)
@cache
def A000073(n):
    if n <= 1: return 0
    if n == 2: return 1
    return A000073(n-1) + A000073(n-2) + A000073(n-3)
@cache
def b(n, i):
    if n == 0: return 1
    if i <  1: return 0
    return sum(binomial(a(i) + j - 1, j) *
               b(n - i * j, i - 1) for j in range(1 + n // i))
@cache
def a(n): return (A000073(n - 1) - b(n, n - 1))
print([a(n) for n in range(1, 41)])

def euler_invtrans(A) :
    L = []; M = []
    for i in range(len(A)) :
        s = (i+1)*A[i] - sum(L[j-1]*A[i-j] for j in (1..i))
        L.append(s)
        s = sum(moebius((i+1)/d)*L[d-1] for d in divisors(i+1))
        M.append(s/(i + 1))
    return M
@cached_function
def a(n): return a(n-1) + a(n-2) + a(n-3) if n > 2 else [0,0,1][n]
print(euler_invtrans([a(n) for n in range(40)]))

A357451 Number of compositions (ordered partitions) of n into tribonacci numbers 1,2,4,7,13,24, ... (A000073).

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 18, 32, 57, 101, 179, 318, 564, 1002, 1778, 3157, 5603, 9947, 17656, 31342, 55635, 98759, 175308, 311191, 552400, 980571, 1740625, 3089803, 5484750, 9736045, 17282576, 30678512, 54457808, 96668726, 171597851, 304605465, 540708924

Offset: 0

Ilya Gutkovskiy, Sep 29 2022

nonn

Cf. A000073, A076739, A117546, A240844, A357453, A357455.

A000073[0] = A000073[1] = 0; A000073[2] = 1; A000073[n_] := A000073[n] = A000073[n - 1] + A000073[n - 2] + A000073[n - 3]; nmax = 36; CoefficientList[Series[1/(1 - Sum[x^A000073[k], {k, 3, 20}]), {x, 0, nmax}], x]

G.f.: 1 / (1 - Sum_{k>=3} x^A000073(k)).

A360260 a(0) = 0, and for any n > 0, let k > 0 be as small as possible and such that T(3) + ... + T(2+k) >= n (where T(m) denotes A000073(m), the m-th tribonacci number); a(n) = k + a(T(3) + ... + T(2+k) - n).

Original entry on oeis.org

0, 1, 3, 2, 5, 6, 4, 3, 8, 10, 9, 6, 7, 5, 4, 12, 11, 14, 15, 13, 8, 9, 11, 10, 7, 8, 6, 5, 16, 17, 15, 14, 19, 21, 20, 17, 18, 10, 11, 13, 12, 15, 16, 14, 9, 10, 12, 11, 8, 9, 7, 6, 21, 23, 22, 19, 20, 18, 17, 25, 24, 27, 28, 26, 21, 22, 24, 23, 12, 13, 15

Offset: 0

Rémy Sigrist, Jan 31 2023

See A356895 for the corresponding k's.

See A360259 for the Fibonacci variant.

			The first terms, alongside the corresponding k's, are:
  n   a(n)  k
  --  ----  ---
   0     0  N/A
   1     1    1
   2     3    2
   3     2    2
   4     5    3
   5     6    3
   6     4    3
   7     3    3
   8     8    4
   9    10    4
  10     9    4
  11     6    4
  12     7    4
  13     5    4
  14     4    4
  15    12    5

Rémy Sigrist, Table of n, a(n) for n = 0..10609

Cf. A000073, A027084, A356895, A360259.

tribonacci(n) = ([0,1,0; 0,0,1; 1,1,1]^n)[2,1]
{ t = k = 0; print1 (0); for (n = 1, #a = vector(70), if (n > t, t += tribonacci(2+k++);); print1 (", "a[n] = k+if (t==n, 0, a[t-n]));); }

a(A027084(n)) = n - 1.

A366783 Sum of the divisors of A000073(n) (tribonacci numbers).

Original entry on oeis.org

1, 1, 3, 7, 8, 14, 60, 84, 121, 150, 414, 1560, 1352, 2304, 7239, 12480, 10713, 22400, 67032, 154056, 166560, 334880, 770160, 1322090, 2020564, 3712800, 8461404, 21427200, 17008752, 37733696, 154277568, 219104032, 249664896, 341958960, 1575703584, 1997069256

Offset: 2

Sean A. Irvine, Oct 22 2023

nonn

			a(8)=60 because the 8th tribonacci number 24 has divisors {1, 2, 3, 4, 6, 8, 12, 24}.

Amiram Eldar, Table of n, a(n) for n = 2..365

Cf. A000203, A000073, A366780, A366781, A366782, A063477.

DivisorSigma[1, LinearRecurrence[{1, 1, 1}, {1, 1, 2}, 36]] (* Amiram Eldar, Oct 23 2023 *)

a(n) = A000203(A000073(n)).

A075111 a(n) = Sum_{i=0..floor(n/2)} (-1)^(i+floor(n/2))*T(2i+e), where T(n) are tribonacci numbers (A000073) and e = (1/2)(1-(-1)^n).

Original entry on oeis.org

0, 1, 1, 1, 3, 6, 10, 18, 34, 63, 115, 211, 389, 716, 1316, 2420, 4452, 8189, 15061, 27701, 50951, 93714, 172366, 317030, 583110, 1072507, 1972647, 3628263, 6673417, 12274328, 22576008, 41523752, 76374088, 140473849, 258371689

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Sep 01 2002

a(n) is the convolution of T(n) with the sequence (1,0,-1,0,1,0,-1,0,....) A056594.

The number of ways to place non-overlapping Young diagrams of shape (3,1) on an 3 by n rectangle. - Per Alexandersson, Jul 01 2025

Index entries for linear recurrences with constant coefficients, signature (1,0,2,1,1).

Cf. A000073, A056594, A074662, A074677, A074678.

CoefficientList[Series[x/(1 - x - 2*x^3 - x^4 - x^5), {x, 0, 40}], x]

a(n) = a(n-1)+2a(n-3)+a(n-4)+a(n-5), a(0)=0, a(1)=1, a(2)=1, a(3)=1, a(4)=3.

G.f.: x/(1 - x - 2*x^3 - x^4 - x^5).

A075676 Sequences A001644 and A000073 interleaved.

Original entry on oeis.org

3, 1, 3, 2, 11, 7, 39, 24, 131, 81, 443, 274, 1499, 927, 5071, 3136, 17155, 10609, 58035, 35890, 196331, 121415, 664183, 410744, 2246915, 1389537, 7601259, 4700770, 25714875, 15902591, 86992799, 53798080, 294294531, 181997601

Offset: 0

Mario Catalani (mario.catalani(AT)unito.it), Sep 24 2002

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0, 3, 0, 1, 0, 1).

Cf. A000073, A001644, A005013, A005247, A075536.

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (3+x- 6*x^2-x^3-x^4)/(1-3*x^2-x^4-x^6) )); // G. C. Greubel, Apr 21 2019

CoefficientList[Series[(3+x-6x^2-x^3-x^4)/(1-3x^2-x^4-x^6), {x, 0, 40}], x]
LinearRecurrence[{0,3,0,1,0,1},{3,1,3,2,11,7},40] (* Harvey P. Dale, May 01 2014 *)

my(x='x+O('x^40)); Vec((3+x-6*x^2-x^3-x^4)/(1-3*x^2-x^4-x^6)) \\ G. C. Greubel, Apr 21 2019

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

a(n) = A000073(n) if n odd, a(n) = A001644(n) if n even.
a(n) = ((1-(-1)^n)*T(n) + (1+(-1)^n)*S(n))/2, where T(n) = A000073(n), S(n) =  A001644(n).
a(n) = 3*a(n-2) + a(n-4) + a(n-6), a(0)=3, a(1)=1, a(2)=3, a(3)=2, a(4)=11, a(5)=7.
O.g.f.: (3 + x - 6*x^2 - x^3 - x^4)/(1 - 3*x^2 - x^4 - x^6).
a(n) = T(n) + (1+(-1)^n)*(T(n-1) + (3/2)*T(n-2)).

A130611 Tribonacci numbers A000073 which can be the hypotenuse of a Pythagorean triple.

Original entry on oeis.org

13, 149, 274, 1705, 19513, 35890, 66012, 121415, 755476, 1389537, 4700770

Offset: 1

Jonathan Vos Post, Jun 17 2007

nonn

The first 2 values are hypotenuses of primitive Pythagorean triples, A000073 INTERSECTION A020882: (5^2 + 12^2 = 13^2), (51^2 + 140^2 = 149^2). The other values listed have one or more nonprimitive solution: a(6) = 35890 has 13 solutions; a(8), a(9), a(10), a(11) have 4 solutions each.

			a(4) = 1705 because 1023^2 + 1364^2 = 1705^2, which is a nonprimitive Pythagorean triple 341*(3,4,5).

Cf. A000073, A020882, A009000.

A000073 INTERSECTION A009000. {c in A000073 such that there exist integers a, b with a^2 + b^2 = c^2}.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

A337286 a(n) = Sum_{i=0..n} i^2*T(i)^2, where T(i) = A000073(i) is the i-th tribonacci number.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A349904 Inverse Euler transform of the tribonacci numbers A000073.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Python

SageMath

A357451 Number of compositions (ordered partitions) of n into tribonacci numbers 1,2,4,7,13,24, ... (A000073).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A360260 a(0) = 0, and for any n > 0, let k > 0 be as small as possible and such that T(3) + ... + T(2+k) >= n (where T(m) denotes A000073(m), the m-th tribonacci number); a(n) = k + a(T(3) + ... + T(2+k) - n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A366783 Sum of the divisors of A000073(n) (tribonacci numbers).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A075111 a(n) = Sum_{i=0..floor(n/2)} (-1)^(i+floor(n/2))*T(2i+e), where T(n) are tribonacci numbers (A000073) and e = (1/2)(1-(-1)^n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula