cp's OEIS Frontend

A370164 The number of residues mod n that occur among the Markov numbers.

%I A370164 #26 Mar 08 2024 16:01:33
%S A370164 1,2,2,2,5,4,4,3,6,10,8,4,13,8,10,5,17,12,16,10,8,16,20,6,25,26,18,8,
%T A370164 29,20,28,9,16,34,20,12,37,32,26,15,41,16,40,16,30,40,44,10,28,50,34,
%U A370164 26,53,36,40,12,32,58,56,20,61,56,24,18,65,32,64,34,40
%N A370164 The number of residues mod n that occur among the Markov numbers.
%C A370164 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).
%C A370164 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).
%C A370164 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).
%C A370164 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.
%C A370164 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.
%D A370164 Martin Aigner, Markov's theorem and 100 years of the uniqueness conjecture. A mathematical journey from irrational numbers to perfect matchings. Springer, 2013. x+257 pp. ISBN: 978-3-319-00887-5; 978-3-319-00888-2 MR3098784.
%H A370164 William P. Orrick, <a href="/A370164/b370164.txt">Table of n, a(n) for n = 1..20000</a>
%H A370164 Martin Aigner, <a href="https://archive.org/details/markovstheorem100000aign">Markov's theorem and 100 years of the uniqueness conjecture. A mathematical journey from irrational numbers to perfect matchings</a>, [archive.org copy of the book].
%F A370164 Conjectured: write 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.
%e A370164 If n = 56 = 7 * 8 then, since only the residues 1, 2, 5, 6 are allowed (mod 7) and only the residues 1, 2, 5 are allowed (mod 8), the number of potential residues (mod 56) is 4 * 3 = 12, and these residues are 1, 2, 5, 9, 13, 26, 29, 33, 34, 37, 41, 50. That these residues are realized by Markov numbers is witnessed by 1, 2, 5, 233, 13, 194, 29, 89, 34, 1325, 433, 610.
%Y A370164 Markov numbers: A002559.
%Y A370164 Markov tree: A327345, A368546.
%Y A370164 Triangle giving list of residues mod n: A370852.
%K A370164 nonn
%O A370164 1,2
%A A370164 _Wouter Meeussen_ and _William P. Orrick_, Feb 26 2024