cp's OEIS Frontend

The characteristic number u of a Markov triple (r, m, s) is the solution in (0, m) of r * x == s (mod m). It satisfies u^2 == -1 (mod m), so that v = (u^2 + 1) / m is also an integer. The other solution in (0,m) of u^2 == -1 (mod m), namely m - u, is always greater than u, so u < m / 2.

The Markov tree may be formulated in terms of a set of Cohn matrices. There is a one-parameter family of such sets, parametrized by an integer c. Given a vertex of the Markov tree with Farey triple (x, y, z) and Markov triple (r, m, s), producing characteristic number u and v = (u^2 + 1) / m, the Cohn matrix C_y(c) with parameter c is

[ c * m + u m ]

[(3 * c - c^2) * m - (2 * c - 3) * u - v (3 - c) * m - u].

Then the vertex is associated with a triple of Cohn matrices, (R, R S, S), where R = C_x(c), RS = C_y(c), and S = C_z(c). See A368546 for a description of Farey and Markov triples. The left child of the vertex is associated with the triple (R, R^2 S, RS) and the right child with (RS, R S^2, S).

This sequence was introduced by Dana Scott but possibly studied earlier by others. - James Propp, Jan 27 2005

Sequence gives the upper-left entries of the respective matrices

[1 1] [1 0] [2 1] [5 2] [29 12] [433 179] [37666 15571]

[1 2] [0 1] [1 1] [2 1] [12 5] [179 74] [15571 6437], ...

satisfying the recurrence M(n) = M(n-1) M(n-3)^(-1) M(n-1) (note that the Fibonacci numbers satisfy the additive version of this recurrence). - James Propp, Jan 27 2005

Define b(1) = b(2) = b(3) = 1; b(n) = (b(n-1) + b(n-2))^2/b(n-3); then a(n) = sqrt(b(n)). - Benoit Cloitre, Jul 28 2002

Any 3 successive terms of the sequence satisfy the Markov equation x^2 + y^2 + z^2 = 3 xyz. Therefore from the 3rd term on this is a subsequence of the Markov numbers, A002559. Also, we conjecture that the limit of log(log(a(n)))/n is log((sqrt(5) + 1)/2). - Martin Giese (martin.giese(AT)oeaw.ac.at), Oct 13 2005

A subsequence of the Markoff numbers A002559. - Andrew Hone, Jan 16 2006

The recursion exhibits the Laurent phenomenon. Let F(n) = Fibonacci(n), e(n) = F(n) - 1, a(1) = a1, a(2) = a2, a(3) = a3, a(n) = (a(n-1)^2 + a(n-3)^2) / a(n-3), b(n) = a(n) * a1^e(n-1) * a2^e(n-2) * a3^e(n-3). Then b(n) for n > 1 is an irreducible polynomial in {a1^2, a2^2, a3^2}, b(n) = (b(n-1)^2 + (b(n-2) * a1^F(n-4) * a2^F(n-5) * a3^F(n-6))^2) / b(n-3), and a(n) = a(n-1) * a(n-2) * (a1^2 + a2^2 + a3^2) / (a1 * a2 * a3) - a(n-3). - Michael Somos, Jan 12 2013

Starting with n = 5, a(n) is the largest number in row n - 5 of the Markov tree, A368546. These numbers are obtained by descending the tree in alternating right and left steps; their Farey indices (see A368546 for the definition) are ratios of successive Fibonacci numbers, 1/2, 2/3, 3/5, 5/8, ... See Aigner, Proposition 10.2. - Wouter Meeussen and William P. Orrick, Feb 11 2024

One of 10 linear second-order recurrence sequences satisfying (a(n)*a(n-1)-1) * (a(n)*a(n+1)-1) = (a(n)+1)^4 and together forming A350916.

From William P. Orrick, Dec 20 2023: (Start)

Every term is a Markov number (see A002559) and, for n > 1, corresponds to a node of the Markov tree A368546 whose sibling and ancestors are all odd-indexed Fibonacci numbers. For n > 1, a(n) is the label of the node obtained from the root by going left n - 2 times and then right. Its Farey index, described in the comments to A368546, is 2 / (2*n - 1).

For instance, a(3) = 194 comes from going left once from the root node of the Markov tree and then right, which corresponds to the sequence of Markov numbers 5, 13, 194. The corresponding sequence of Farey indices is 1/2, 1/3, 2/5. The sibling of the final node corresponds to Markov number 34 and Farey index 1/4. (End)

See lemma 5.2 of Reznick's preprint.

Conjecture: count of even Markov numbers in generation n (with generations 0, 1 and 2 labeled as {5}, {13, 29} and {34, 194, 433, 169}. (Checked up to generation 20.) - Wouter Meeussen, Jan 16 2024

Wouter Meeussen's conjecture is true. Proof: label the Markov tree with Markov triples according to the scheme described at A368546. Mod 2, the triples are: row 0: (1,1,0); row 1: (1,1,1), (1,1,0); row 2: (1,0,1), (1,0,1), (1,1,1), (1,1,0); row 3: (1,1,0), (0,1,1), (1,1,0), (0,1,1), (1,0,1), (1,0,1), (1,1,1), (1,1,0); etc. Note that the Markov number labels of the tree (the center numbers of the triples) in rows 0 and 1 include no even numbers, while those in row 2 include two even numbers. Observing that the second triple in row 1 and the first four triples in row 3 are the same or the reverse of the root triple, and noting that every vertex in row 3 and beyond is in a subtree with one of these triples as root, the recurrence follows. - William P. Orrick, Mar 05 2024

No Markov number is divisible by any prime congruent to 3 (mod 4). Proof: Let m be a Markov number and let p be an odd prime dividing m. Then there exist positive integers b and c such that m^2 + b^2 + c^2 = 3 * m * b * c (Markov's equation). Furthermore it is known that b and c must be coprime to m. Evaluating Markov's equation (mod p) gives b^2 = -c^2 (mod p), which implies -1 is a square (mod p). This is only possible if p = 1 (mod 4).

Given a prime p congruent to 3 (mod 4) and greater than 3, no Markov number is congruent to 1/3 * (p - 2 * sigma(p)) or 2/3 * (p + sigma(p)) (mod p), where sigma(p) = -1 if p is congruent to 7 (mod 12) and sigma(p) = 1 if p is congruent to 11 (mod 12). Proof: Let m be a Markov number congruent to one of the forbidden residues (mod p). Then evaluating Markov's equation (mod p) using the forms of the forbidden residues above and doing a few simplifications implies that -4 is a square (mod p). This contradicts that p = 3 (mod 4).

The first comment above implies that an odd Markov number is congruent to 1 (mod 4). It has also been shown that any positive even integer satisfying all of the constraints of the first two comments above is congruent to 2 (mod 32).

It is conjectured that, modulo n, all residues not forbidden by the constraints in the three comments above are actually realized by some Markov number. Specifically, mod n the forbidden residues include the following: (1) if p is a prime congruent to 3 (mod 4) that divides n, then any residue congruent to 0 (mod p) or congruent to either of the forbidden residues listed in the second comment (mod p), (2) if 4 divides n, then any odd residue congruent to 3 (mod 4), (3) if 2^r is the highest power of 2 dividing n and 2 <= r <= 5, then any even residue not congruent to 2 (mod 2^r), (4) if 2^r is the highest power of 2 dividing n and r > 5, then any even residue not congruent to 2 (mod 32). It is conjectured that all other residues occur. This has been verified for all n <= 38000.

If the conjecture in the previous comment is correct, then it follows from the Chinese remainder theorem that a(n) may be found by writing n = 2^s * 3^t * u * p_1^r_1 * p_2^r_2 * ... * p_k^r_k, where p_1, ..., p_k are distinct primes greater than 3 and congruent to 3 (mod 4) and r_1, ..., r_k are positive and where the prime divisors of u are all congruent to 1 (mod 4). Then a(n) = u * C_s * D_t * Product_{j=1..k} (p_j - 3) * p_j^(r_j - 1), where C_s = 2^s if s < 2, 1 + 2^(s-2) if 2 <= s <= 5, and 2^(s - 5) + 2^(s - 2) if s > 5, and where D_t = 1 if t = 0 and 2 * 3^(t-1) if t > 0. If the conjecture holds then a(n) is a multiplicative function.

Length of row n is A370164(n).