Displaying 1-4 of 4 results found.
page
1
T(n,k) = (n-1)* A220555(n,k), n,k = 2,3,....
+20
2
3, 14, 8, 21, 52, 6, 124, 54, 28, 20, 315, 484, 42, 124, 24, 90, 130, 248, 186, 364, 16, 105, 144, 630, 3124, 378, 84, 12, 4088, 11480, 180, 120, 15004, 342, 56, 24, 567, 78728, 210, 120, 8190, 11204, 84, 156, 60
COMMENTS
For n,k >= 2, T(n,k) is equal to the maximal period p of the corresponding sequence (w.r.t. n and k) defined in Conjecture 1 in A220555.
EXAMPLE
Array begins as
....3.....8.....6......20.......24......16....12.....24.........60
...14....52....28.....124......364......84....56....156........868
...21....54....42.....186......378.....342....84....162.......1302
..124...484...248....3124....15004...11204...496...1452......96844
..315...130...630.....120.....8190...65360..1260....390.......2520
...90...144...180.....120......720....2400...360....432........360
..105.11480...210..227864....34440.1681400...420..34440....3417960
.4088.78728..8176.3906248.40230008....2736.16352.236184.1996092728
..567...702..1134....1116....14742.....378..2268...2106......70308
a(n) is the number of different linear hydrocarbon molecules with n carbon atoms.
+10
4
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
COMMENTS
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).
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)).
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)
LINKS
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).]
FORMULA
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]
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]
EXAMPLE
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.
MAPLE
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:
MATHEMATICA
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}])];
PROG
(Python)
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*cos(Pi/9))^n + (1 + 2*cos(Pi*2/9))^n + (1 + 2*cos(Pi*4/9))^n.
+10
2
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
COMMENTS
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
FORMULA
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
EXAMPLE
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
MAPLE
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);
MATHEMATICA
LinearRecurrence[{3, 0, -3}, {3, 9, 18}, 25] (* Georg Fischer Feb 02 2019 *)
PROG
(PARI) { 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
(PARI) Vec((3-9*x^2)/(1-3*x+3*x^3)+O(x^66)) /* Joerg Arndt, Apr 08 2011 */
EXTENSIONS
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
Period of the sequence of the digital roots of Fibonacci n-step numbers.
+10
2
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
COMMENTS
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
EXAMPLE
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).
MAPLE
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:
MATHEMATICA
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}]
CROSSREFS
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.
Search completed in 0.007 seconds
|