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

Length of row n is A370164(n).

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.

The Markov tree is a complete, infinite binary tree. Vertices are labeled by triples. The root vertex is (1, 5, 2). The left child of (a, b, c) is (a, 3*a*b - c, b); its right child is (b, 3*b*c - a, c). The sequence is a triangle read by rows consisting of the middle element of each triple, which is always the largest element of the triple. Row r contains 2^r elements.

The tree contains contains exactly one representative of each class of permutation equivalent nonsingular solutions to Markov's equation, a^2 + b^2 + c^2 = 3 * a * b * c. Nonsingular solutions are those in which a, b, and c are three distinct numbers. The two singular triples (1, 1, 1) and (1, 2, 1) are omitted in this sequence.

A consequence of Markov's equation is that the recurrence for the tree may be reformulated as follows: the left child of (a, b, c) is (a, (a^2 + b^2) / c, b); its right child is (b, (b^2 + c^2) / a, c).

An open problem is to prove the uniqueness conjecture, which asserts that the largest element of a triple determines the other two.

Frobenius proposed assigning a rational number index in (0,1) to each vertex of the tree, and hence to each term in this sequence. This is the Farey index, obtained by assigning the triple (0/1, 1/2, 1/1) to the root vertex and using the following rules to assign triples to the rest of the tree: the vertex labeled (u/v, w/x, y/z) with w = u + u and x = v + z has left child (u/v, (u+w)/(v+x), w/x) and right child (w/x, (w+y)/(x+z), y/z). The Farey index is the center element of the triple. Each rational number in (0, 1) appears as the Farey index of exactly one vertex of the tree. The index of a(n) is A007305(n+2) / A007306(n+2).

A sequence of leftward steps in the tree produces odd-indexed Fibonacci numbers, A001519, which have Farey indices of the form 1 / n. A sequence of rightward steps in the tree produces odd-indexed Pell numbers, A001653, which have Farey indices of the form (n - 1) / n. A sequence of leftward steps followed by a single rightward step produces A350922, corresponding to Farey indices of the form 2 / (2 * n + 1). Alternating steps right, left, right, left, right, ... produces A064098, which corresponds to Farey indices of the form F(n) / F(n + 1), where F(n) is the n-th Fibonacci number.

If n = p_1^r_1 p_2^r_2 ... p_k^r_k where p_1, ..., p_k are distinct primes, the partial fraction decomposition of m/n has the form z + Sum_{i=1..k} a_i / p_i^r_i = z + Sum_{i=1..k} Sum_{j=1..r_i} a_ij / p_i^j where 0 < a_i < p_i^r_i, gcd(a_i,p_i) = 1, and where 0 <= a_ij < p_i (a_ij > 0 when j = r_i). z is the integer part.

If 0 < m / n < 1 and gcd(m,n) = 1 then the integer part satisfies 1 - k <= z <= 0.

If n is a nonhyperbolic number, which means that Sum_{i=1..k} 1 / p_i^r_i >= 1, then the integer part is not zero for any m/n with 0 < m / n < 1, gcd(m,n) = 1.

Assuming gcd(m,n) = 1, if m/n has integer part z then (n - m)/n has integer part 1 - k - z. This means there are equally many reduced fractions with denominator n > 1 between 0 and 1 having integer part z and integer part 1 - k - z.

If row elements are divided by row sums, one obtains a probability distribution that approaches a Poisson distribution with expected value 1 as n approaches infinity.

The number of configurations depends on the number of sides on the dice only through its prime signature. A063008 provides a canonical representative of each prime signature.

Also the number of Krasner factorizations of (x^(A063008(n))^k)-1) / (x-1) into k polynomials each having A063008(n) nonzero terms all with coefficient +1. (Krasner and Ranulac, 1937)

Also the number of Krasner factorizations of (x^((p^n*q)^k)-1) / (x-1) into k polynomials each having p^n*q nonzero terms all with coefficient +1. (Krasner and Ranulac, 1937)

The terms up to a(21) were computed by Michael Borinsky and Jos Vermaseren using a program written in FORM. The graphs enumerated by a(n) are called admissible (Borinsky and Vogtmann, 2023).

T(n,k) depends on n only through its prime signature. (See A118914.) For example, for fixed k, T(p*q^2,k) will be the same for any pair of distinct primes p and q. Hence we may define T(n,k) = R(s(n),k), where s(n) is the prime signature of n.

Also the number of Krasner factorizations of (x^(n^k)-1) / (x-1) into k polynomials each having n nonzero terms all with coefficient +1. (Krasner and Ranulac, 1937)