A220555 -id:A220555 - cp's OEIS frontend

A306334 a(n) is the number of different linear hydrocarbon molecules with n carbon atoms.

1, 3, 4, 10, 18, 42, 84, 192, 409, 926, 2030, 4577, 10171, 22889, 51176, 115070, 257987, 579868, 1301664, 2925209, 6569992, 14763529, 33166848, 74527233, 167446566, 376253517, 845401158, 1899609267, 4268309531, 9590827171, 21550227328, 48422972296, 108805058758

Offset: 1

Vincent Champain, Feb 08 2019

Linear hydrocarbons are molecules made of carbon (C) and hydrogen (H) atoms organized without cycles.
a(n) <= A002986(n) because molecules can be acyclic but not linear (i.e., including carbon atoms bonded with more than two other carbons).
From Petros Hadjicostas, Nov 16 2019: (Start)
We prove Vaclav Kotesovec's conjectures from the Formula section. Let M = [[0,0,1], [0,1,1], [1,1,1]], X(n) = M^(n-2), and Y(n) = M^(floor(n/2)-2) = X(floor(n/2)) (with negative powers indicating matrix inverses). Let also, t_1 = [1,1,1]^T, t_2 = [1,2,2]^T, and t_3 = [1,2,3]^T. In addition, define b(n) = (1/2)*(t_1^T X(n) t_1) and c(n) = (1/2)*(t_3^T Y(n) t_1) if n is even and = (1/2)*(t_2^T Y(n) t_1) if n is odd.
We have a(n) = b(n) + c(n) for n >= 1. Since the characteristic polynomial of Vaclav Kotesovec's recurrence is x^9 - 2*x^8 - 3*x^7 + 5*x^6 + x^5 + 2*x^3 - 3*x^2 - x + 1 = g(x)*g(x^2), where g(x) = x^3 - 2*x^2 - x + 1, to prove his first conjecture, it suffices to show that b(n) - 2*b(n-1) - b(n-2) + b(n-3) = 0 (whose characteristic polynomial is g(x)) and c(n) - 2*c(n-2) - c(n-4) + c(n-6) = 0 (whose characteristic polynomial is g(x^2)).
Note that 2*b(n) = A006356(n-1) for n >= 1. (See the comments by L. Edson Jeffery and R. J. Mathar in the documentation of that sequence.) Also, 2*c(2*n) = A006356(n) and 2*c(2*n-1) = A006054(n+1) for n >= 1.
Properties of the polynomial g(x) = x^3 - 2*x^2 - x + 1 and its roots were studied by Witula et al. (2006) (see Corollary 2.4). This means that a(n) can essentially be expressed in terms of exp(I*2*Pi/7), but we omit the discussion. See also the comments for sequence A006054.
The characteristic polynomial of matrix M is g(x). By the Cayley-Hamilton theorem, 0 = g(M) = M^3 - 2*M^2 - M + I_3, and thus, for n >= 5, X(n) - 2*X(n-1) - X(n-2) + X(n-3) = M^(n-2) - 2*M^(n-3) - M^(n-4) + M^(n-5) = 0. Pre-multiplying by (1/2)*t_1^T and post-multiplying by t_1, we get that b(n) - 2*b(n-1) - b(n-2) + b(n-3) = 0 for n >= 5.
Similarly, for n >= 10, Y(n) - 2*Y(n-2) - Y(n-4) + Y(n-6) = X(floor(n/2)) - 2*X(floor((n-2)/2)) - X(floor((n-4)/2)) + X(floor((n-6)/2)) = X(floor(n/2)) - 2*X(floor(n/2) - 1) - X(floor(n/2) - 2) + X(floor(n/2) - 3) = 0. Pre-multiplying by (1/2)*t_3^T (when n is even) or by (1/2)*t_2^T (when n is odd), and post-multiplying by t_1, we get c(n) - 2*c(n-2) - c(n-4) + c(n-6) = 0 for n >= 10.
Since the characteristic polynomial of Vaclav Kotesovec's recurrence is g(x)*g(x^2), which is a polynomial of degree 9, the denominator of the g.f. of the sequence (a(n): n >= 1) should be x^9*g(1/x)*g(1/x^2) = (1 - 2*x - x^2 + x^3)*(1 - 2*x^2 - x^4 + x^6), as Vaclav Kotesovec conjectured below. The numerator of Vaclav Kotesovec's g.f. can be easily derived using the initial conditions (from a(1) = 1 to a(9) = 409). (End)

			For n=1, there is one possibility: CH4.
For n=2, there are 3 solutions: CHCH, CH3CH3, CH2CH2.
For n=3, there are 4 solutions: CHCCH3, CH2CCH2, CH3CHCH2, CH3CH2CH3.
For n=6, there are 42 solutions: CH3CH2CHCHCCH, CH3CH2CHCHCH2CH3, CH2CHCCCHCH2, CH2CHCHCHCH2CH3, CH2CHCHCHCCH, CH2CCCCHCH3, CHCCCCHCH2, CH3CHCHCHCHCH3, CHCCHCHCCH, CH2CCCCCH2, CH3CCCH2CH2CH3, CH3CCCCCH3, CH3CH2CH2CH2CH2CH3, CH2CHCHCHCHCH2, CH2CCHCH2CHCH2, CH3CHCCCHCH3, CHCCH2CH2CH2CH3, CHCCH2CH2CCH, CH3CCCH2CHCH2, CH2CCCHCH2CH3, CH2CCCHCCH, CHCCH2CCCH3, CHCCH2CHCCH2, CH3CH2CH2CH2CHCH2, CH2CHCHCCHCH3, CH3CH2CCCH2CH3, CH2CHCH2CH2CHCH2, CH2CHCHCCCH2, CH3CHCCHCH2CH3, CH3CH2CH2CHCHCH3, CH3CHCCHCCH, CHCCH2CH2CHCH2, CH3CHCHCCCH3, CH2CCHCCCH3, CH3CHCHCHCCH2, CHCCCCH2CH3, CH2CHCH2CHCHCH3, CH2CCHCHCCH2, CHCCCCCH, CH2CCHCH2CH2CH3, CH3CH2CCCHCH2, CHCCH2CHCHCH3.

Vincent Champain, Table of n, a(n) for n = 1..1000
L. Edson Jeffery, Danzer matrices (unit-primitive matrices). [It contains a discussion of a generalization of the matrix M that appears in the formula for a(n). See basis D_7.]
Wikipedia, Cayley-Hamilton theorem.
R. Witula, D. Slota, and A. Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq. 9 (2006), Article 06.4.3. [See Corollary 2.4 and the discussion about the polynomial p_7(x) and its roots. This essentially proves that a(n) can be expressed in terms of exp(I*2*Pi/7).]
Index entries for linear recurrences with constant coefficients, signature (2,3,-5,-1,0,-2,3,1,-1).

Other hydrocarbon related sequences: A002986, A018190, A129012.

Cf. A006054, A006356.

with(LinearAlgebra):
M := Matrix([[0, 0, 1], [0, 1, 1], [1, 1, 1]]):
X := proc(n) MatrixPower(M, n - 2): end proc:
Y := proc(n) MatrixPower(M, floor(1/2*n) - 2): end proc:
a := proc(n) `if`(n < 4, [1,3,4][n], 1/2*(add(add(X(n)[i, j], i = 1..3), j = 1..3) + add(add(Y(n)[i, j]*min(j, 3 - (n mod 2)), i = 1..3), j = 1..3))):
     end proc:
seq(a(n), n=1..40); # Petros Hadjicostas, Nov 17 2019

M = {{0, 0, 1}, {0, 1, 1}, {1, 1, 1}};
X[n_] := MatrixPower[M, n - 2];
Y[n_] := MatrixPower[M, Floor[1/2*n] - 2];
a[n_] := If[n < 4, {1, 3, 4}[[n]], 1/2*(Sum[Sum[X[n][[i, j]], {i, 1, 3}], {j, 1, 3}] + Sum[Sum[Y[n][[i, j]]*Min[j, 3 - Mod[n, 2]], {i, 1, 3}], {j, 1, 3}])];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Aug 16 2023, after Petros Hadjicostas *)

from numpy import array as npa
from numpy.linalg import matrix_power as npow
def F(n):
     if n<4: return([0,1,3,4][n])
     m=npa([[0,0,1],[0,1,1],[1,1,1]],dtype=object)
     m2=npow(m,n//2-2)
     return((sum(sum(npow(m,n-2)))+sum(sum(m2[j]*min(j+1,3-(n&1)) for j in range(3))))//2)

a(n) = (1/2) * (Sum_{i,j = 1..3} X_{ij} + Sum_{i,j = 1..3} Y_{ij} * min(j, 3 - (n&1))), where M = [[0,0,1], [0,1,1], [1,1,1]], X = [X_{ij}: i,j = 1..3] = M^(n-2), and Y = [Y_{ij}: i,j = 1..3] = M^(floor(n/2)-2)) for n >= 1 (with negative powers indicating matrix inverses). [Edited by Petros Hadjicostas, Nov 16 2019]
Conjectures from Vaclav Kotesovec, Feb 12 2019: (Start)
a(n) = 2*a(n-1) + 3*a(n-2) - 5*a(n-3) - a(n-4) - 2*a(n-6) + 3*a(n-7) + a(n-8) - a(n-9), for n >= 10.
G.f.: (1 - x - 2*x^2 - x^4 + 2*x^5 + x^6 - x^7) / ((1 - 2*x - x^2 + x^3)*(1 - 2*x^2 - x^4 + x^6)) - 1. (End) [These conjectures are true. See my comments above. - Petros Hadjicostas, Nov 17 2019]
From Petros Hadjicostas, Nov 17 2019: (Start)
a(2*n) = (1/2)*(A006356(2*n-1) + A006356(n)).
a(2*n-1) = (1/2)*(A006356(2*n-2) + A006054(n+1)). (End)

A062882 a(n) = (1 - 2cos(Pi/9))^n + (1 + 2cos(Pi2/9))^n + (1 + 2cos(Pi*4/9))^n.

Original entry on oeis.org

3, 9, 18, 45, 108, 270, 675, 1701, 4293, 10854, 27459, 69498, 175932, 445419, 1127763, 2855493, 7230222, 18307377, 46355652, 117376290, 297206739, 752553261, 1905530913, 4824972522, 12217257783, 30935180610, 78330624264

Offset: 1

Vladeta Jovovic, Jun 27 2001

From L. Edson Jeffery, Apr 05 2011: (Start)
Let U be the matrix (see [Jeffery])
U = U_(9,2) =
  (0 0 1 0)
  (0 1 0 1)
  (1 0 1 1)
  (0 1 1 1).
Then a(n) = Trace(U^n).
(End)
We note that all numbers of the form a(n)*3^(-floor((n+4)/3)) are integers. - Roman Witula, Sep 29 2012

			We have a(2)=3*a(1), a(4)/a(3) = a(6)/a(5) = a(7)/a(6) = 5/2, a(6)=6*a(4), a(7)=15*a(4), and (1 + c(1))^8 + (1 + c(2))^8 + (1 + c(4))^8 = 7*3^5. - _Roman Witula_, Sep 29 2012

Harry J. Smith, Table of n, a(n) for n = 1..200
L. Edson Jeffery, Danzer matrices
Index entries for linear recurrences with constant coefficients, signature (3,0,-3).

Cf. A033304, A062883.

Digits := 1000:q := seq(floor(evalf((1-2*cos(1/9*Pi))^n+(1+2*cos(2/9*Pi))^n+(1+2*cos(4/9*Pi))^n)),n=1..50);

LinearRecurrence[{3,0,-3},{3,9,18},25] (* Georg Fischer Feb 02 2019 *)

{ default(realprecision, 200); for (n=1, 200, a=(1 - 2*cos(1/9*Pi))^n + (1 + 2*cos(2/9*Pi))^n + (1 + 2*cos(4/9*Pi))^n; write("b062882.txt", n, " ", round(a)) ) } \\ Harry J. Smith, Aug 12 2009

Vec((3-9*x^2)/(1-3*x+3*x^3)+O(x^66)) /* Joerg Arndt, Apr 08 2011 */

G.f.: x*(3 - 9*x^2)/(1 - 3*x + 3*x^3). The terms in parentheses in the definition are the roots of x^3-3*x^2+3. - Ralf Stephan, Apr 10 2004

a(n) = 3*(a(n-1) - a(n-3)) for n >= 4 - Roman Witula, Sep 29 2012

More terms from Sascha Kurz, Mar 24 2002
Adapted formula, denominator of g.f. and modified g.f. (and offset) to accommodate added initial term a(0)=4. - L. Edson Jeffery, Apr 05 2011
a(0) = 4 removed, g.f. and programs adapted by Georg Fischer, Feb 02 2019

A210456 Period of the sequence of the digital roots of Fibonacci n-step numbers.

Original entry on oeis.org

1, 24, 39, 78, 312, 2184, 1092, 240, 273, 26232, 11553, 9840, 177144, 14348904, 21523359, 10315734, 48417720, 16120104, 15706236, 5036466318, 258149112, 1162261464, 141214768239, 421900912158, 8857200, 2184, 2271, 28578504864, 21938847432216, 148698308091840

Offset: 1

Paolo P. Lava, Robert G. Wilson v, Jan 21 2013

More precisely, start with 0,0,...,0,1 (with n-1 0's and a single 1); thereafter the next term is the digital root (A010888) of the sum of the previous n terms. This is a periodic sequence and a(n) is the length of the period.
Theorem: a(n) <= 9^n.
Conjecture: All entries >1 are divisible by 3.
Additional terms are a(242)=177144, a(243)=177879.
More: a(728)=1594320, a(729)=1596513, a(2186)=14348904, a(2187)=14355471, a(6560)=129140160, a(6561)=129159849, a(19682)=1162261464, a(19683)=1162320519. - Hans Havermann, Jan 30 2013, Feb 08 2013
The modulus-9 Pisano periods of Fibonacci numbers, k-th order sequences. - Hans Havermann, Feb 10 2013
Conjecture: a(3^n-1)=3^(2*n+1)-3, a(3^n)=3^(2*n+1)+3^(n+1)+3 - Fred W. Helenius (fredh(AT)ix.netcom.com), posting to MathFun, Feb 21 2013

			Digital roots of Fibonacci numbers (A030132) are 0, 1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 9, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 9, 1, 1, 2, 3,... Thus the period is 24 (1, 1, 2, 3, 5, 8, 4, 3, 7, 1, 8, 9, 8, 8, 7, 6, 4, 1, 5, 6, 2, 8, 1, 9).

Hiroaki Yamanouchi, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Pisano Period

Cf. Fibonacci numbers, k-th order sequences, A000045 (Fibonacci numbers, k=2), A030132 (digital root, k=2), A001175 (Pisano periods, k=2), A000073 (tribonacci numbers, k=3), A222407 (digital roots, k=3), A046738 (Pisano periods, k=3), A029898 (Pitoun's sequence), A187772, A220555.

Cf. also A010888.

A210456:=proc(q,i)
local d,k,n,v;
v:=array(1..q);
for d from 1 to i do
  for n from 1 to d do v[n]:=0; od; v[d+1]:=1;
  for n from d+2 to q do v[n]:=1+((add(v[k],k=n-d-1..n-1)-1) mod 9);
    if add(v[k],k=n-d+1..n)=9*d and v[n-d]=1 then print(n-d); break;
fi; od; od; end:
A210456 (100000000,100);

f[n_] := f[n] = Block[{s = PadLeft[{1}, n], c = 1}, s = t = Nest[g, s, n]; While[t = g[t]; s != t, c++]; c]; g[lst_List] := Rest@Append[lst, 1 + Mod[-1 + Plus @@ lst, 9]]; Do[ Print[{n, f[n] // Timing}], {n, 100}]

a(23) from Hans Havermann, Jan 30 2013
a(24) from Hans Havermann, Feb 18 2013
a(28) from Robert G. Wilson v, Feb 21 2013
a(29)-a(30) from Hiroaki Yamanouchi, May 04 2015

cp's OEIS Frontend

A187772 T(n,k) = (n-1)*A220555(n,k), n,k = 2,3,....

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A306334 a(n) is the number of different linear hydrocarbon molecules with n carbon atoms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A062882 a(n) = (1 - 2*cos(Pi/9))^n + (1 + 2*cos(Pi*2/9))^n + (1 + 2*cos(Pi*4/9))^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A210456 Period of the sequence of the digital roots of Fibonacci n-step numbers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A062882 a(n) = (1 - 2cos(Pi/9))^n + (1 + 2cos(Pi2/9))^n + (1 + 2cos(Pi*4/9))^n.