| Displaying 1-3 of 3 results found.
page
1
1, 2, 4, 5, 6, 8, 9, 11, 12, 13, 14, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 30, 31, 32, 34, 35, 37, 38, 39, 41, 42, 44, 45, 46, 47, 49, 50, 52, 53, 54, 56, 57, 59, 60, 61, 62, 64, 65, 67, 68, 69, 70, 72, 73, 75, 76, 77, 79, 80, 82, 83, 84, 85, 87, 88, 90
COMMENTS
Conjecture: lim_{n->infinity} a(n)/n = 1.36..., and if m denotes this number, then -1 < m - a(n)/n < 1 for n >= 1.
Proof of the first part of this conjecture.
Let a(0):=0. We write this sequence as the sum of its first differences:
a(n) = Sum_{k=0..n-1} a(k+1)-a(k).
We know (see A288173) that A288173 can be generated as a decoration delta(t) of the fixed point t of the morphism alpha given by alpha(A) = AB, alpha(B) = AC, alpha(C) = ABB.
Here delta is the morphism
delta(A) = 001, delta(B) = 0001, delta(C) = 00001.
Let e = A288175 be the sequence of positions of 1 in A288173. Note that if we are at the n-th 1, then we have seen e(n)-n zeros. So the position of the (e(n)-n)-th zero is e(n)-1. Let m(n):=e(n)-n. Then
a(m(n))/m(n) = (e(n)-1)/m(n) = (e(n)-1)/n * n/(e(n)-n).
According to the comments at e = A288175, the first factor in this product converges to 3.7092753596..., and the second to 1/(3.7092753596... - 1). It follows that as n->infinity,
a(m(n))/m(n) -> 1.36900369004... .
It is easy to see from this that the whole sequence converges, and so
a(n)/n -> 1.36900369004... . (End)
MATHEMATICA
s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "001"}]
Table[w[n], {n, 0, 8}]
st = ToCharacterCode[w[11]] - 48 (* A288173 *) Flatten[Position[st, 0]] (* A288174 *) Flatten[Position[st, 1]] (* A288175 *)
3, 7, 10, 15, 18, 22, 25, 29, 33, 36, 40, 43, 48, 51, 55, 58, 63, 66, 71, 74, 78, 81, 86, 89, 93, 96, 100, 104, 107, 111, 114, 119, 122, 126, 129, 133, 137, 140, 144, 147, 151, 155, 158, 162, 165, 170, 173, 177, 180, 184, 188, 191, 195, 198, 203, 206, 210
COMMENTS
Conjecture: lim_{n->infinity} a(n)/n = 3.70..., and if m denotes this number, then -1 < m - a(n)/n < 1 for n >= 1.
Proof of the first part of this conjecture.
Let a(0):=0. We write this sequence as the sum of its first differences:
a(n) = Sum_{k=0..n-1} a(k+1)-a(k).
We know (see A288173) that A288173 can be generated as a decoration delta(t) of the fixed point t of the morphism alpha given by alpha(A) = AB, alpha(B) = AC, alpha(C) = ABB.
Here delta is the morphism
delta(A) = 001, delta(B) = 0001, delta(C) = 00001.
We see from this that the first differences of the positions of 1 can be obtained as the image of the sequence t = ABACABABB... under the letter-to-letter morphism lambda given by
lambda(A) = 3, lambda(B) = 4, lambda(C) = 5.
Then
a(n) = 3*N_A(n) + 4*N_B(n) + 5*N_C(n),
where N_X(n) is the number of times the letter X from {A,B,C} occurs in the word t(1)t(2)...t(n).
It follows that a(n)/n is asymptotically equal to the weighted asymptotic frequencies m_A, m_B, m_C of the letters in t:
a(n)/n -> 3*m_A + 4*m_B + 5*m_C.
The existence and values of these frequencies follow from the Perron-Frobenius theorem for nonnegative matrices applied to the incidence matrix of the morphism alpha. This incidence matrix is equal to
|1 1 1 |
|1 0 2 |
|0 1 0 |.
The eigenvalues are cubic irrationals equal to
L1 = 2.17008648..., L2 = 0.3111078169..., L3 = -1.481194304... .
According to the PF-theorem the vector of frequencies (m_A, m_B, m_C) is equal to the normalized eigenvector of the eigenvalue L1
(m_A, m_B, m_C) = (0.46081112715, 0.36910238601, 0.17008648683).
It thus follows that a(n)/n -> 3.7092753596... . (End)
MATHEMATICA
s = {0, 0}; w[0] = StringJoin[Map[ToString, s]];
w[n_] := StringReplace[w[n - 1], {"00" -> "0010", "1" -> "001"}]
Table[w[n], {n, 0, 8}]
st = ToCharacterCode[w[11]] - 48 (* A288173 *) Flatten[Position[st, 0]] (* A288174 *) Flatten[Position[st, 1]] (* A288175 *)
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3) + a(n-4), where a(0) = 2, a(1) = 4, a(2) = 8, a(3) = 16.
+10
2
2, 4, 8, 16, 34, 72, 156, 336, 730, 1580, 3432, 7440, 16154, 35040, 76060, 165024, 358162, 777172, 1686632, 3659984, 7942706, 17236024, 37404156, 81169520, 176145962, 382250364, 829518728, 1800123856, 3906429674, 8477282512, 18396447676, 39921865536
COMMENTS
Conjecture: a(n) is the number of letters (0's and 1's) in the n-th iteration of the mapping 00->0010, 1->001, starting with 00; see A288173. Proof of this conjecture.
We know (see A288173) that A288173 can be generated as a decoration delta(t) of the fixed point t of the morphism alpha given by alpha(A) = AB, alpha(B) = AC, alpha(C) = ABB.
Here delta is the morphism
delta(A) = 001, delta(B) = 0001, delta(C) = 00001.
Looking at the proof, we see that we have in more detail that the n-th iterate of SR starting with 00 equals the decoration of the (n-1)-th iterate of alpha starting with A, with a suffix 0 added.
For example,
SR(00) = 0010 = delta(A)0, SR^2(00) = 00100010 = delta(alpha(A))0.
This implies that the total number of letters (0's and 1's) minus 1 in the n-th iterate of SR is equal to the vector/matrix/vector product
(3,4,5) M^(n-1) (1,0,0)^T,
where (1,0,0)^T is the transpose of (1,0,0), and M is the incidence matrix of the morphism alpha, so M equals
|1 1 1 |
|1 0 2 |
|0 1 0 |.
The characteristic polynomial of M is equal to chi(u) = u^3-u^2-3*u+1. It follows therefore from the Cayley-Hamilton theorem that the sequence of lengths minus 1 satisfies the linear recursion
a(n+3) = a(n+2) + 3*a(n+1) - a(n).
This is not the conjectured recursion a(n+4) = 2*a(n+3) +2* a(n+2) - 4*a(n+1) + a(n) for A288176. However, if we substitute one of the three a(n+2)'s by a(n+2) = a(n+3) -3*a(n+1) + a(n) in the shifted equation
a(n+4) = a(n+3) + 3*a(n+2) - a(n+1),
then we obtain the conjectured recursion.
This proves the conjecture (where one uses that the constant sequence (1,1,1,...) satisfies the conjectured recursion). (End)
FORMULA
a(n) = 2*a(n-1) + 2*a(n-2) - 4*a(n-3) + a(n-4), where a(0) = 2, a(1) = 4, a(2) = 8, a(3) = 16.
G.f.: (-2 + 4*x^2)/((-1 + x) (1 - x - 3*x^2 + x^3)).
MATHEMATICA
LinearRecurrence[{2, 2, -4, 1}, {2, 4, 8, 16}, 40]
Search completed in 0.008 seconds
| 