Счастливые числа

The iteration came first and the name came later. The earliest known treatment is a three-page paper by Arthur Porges, "A Set of Eight Numbers", in the American Mathematical Monthly volume 52 (1945), pages 379–382. Porges — an American writer who held a bachelor's and a master's degree in mathematics and taught the subject at college level before turning to short fiction full time — proved the fact that makes the whole puzzle well posed: take any positive integer, replace it by the sum of the squares of its digits, repeat, and you must end either at 1 or in the cycle 4, 16, 37, 58, 89, 145, 42, 20. Nothing else can happen in base ten. The reason is a size argument: any number of four or more digits maps to something strictly smaller, so every trajectory falls below 1000 within a few steps and is then trapped in a range small enough to check exhaustively by hand.

Where the cheerful name came from is genuinely unclear, and the usual story is a chain of custody rather than a discovery. The most widely repeated account has the problem reaching Reginald Allenby, a British author and senior lecturer in pure mathematics at the University of Leeds, by way of his daughter, who had met it at school; the same account adds only that the idea may have originated in Russia. Nobody has pinned it down further.

What drew research mathematicians was density. Esam El-Sedy and Samir Siksek proved that the happy numbers contain arbitrarily long runs of consecutive integers. Justin Gilmer later showed that their lower density is below 0.1138 while their upper density is above 0.18577 — the bounds do not meet, so the happy numbers have no natural density at all, even though counting them over any fixed range gives a suspiciously stable answer near 14%.

Ключевые свойства

• In base 10, iterating the sum of the squares of the digits always reaches either 1 or the eight-term cycle 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4.
• 7 is the smallest happy number above 1, by way of 7 → 49 → 97 → 130 → 10 → 1.
• 142 of the integers from 1 to 999 are happy; of the integers from 1 to 2,000,000, exactly 282,005 are, which is about 14.1%.
• The first pair of consecutive happy numbers is 31 and 32; the first run of three is 1880, 1881, 1882; the first run of four begins at 7839.
• El-Sedy and Siksek proved that runs of consecutive happy numbers can be made arbitrarily long.
• Gilmer proved that the lower density of the happy numbers is less than 0.1138 and the upper density greater than 0.18577, so the sequence has no natural density.
• A number of four or more digits always maps to a strictly smaller value, which is why every trajectory is eventually confined below 1000.
• Base 2 and base 4 are the only bases below 5×10⁸ known to be "happy", meaning every number in them reaches 1; whether any others exist is an open question.

Где встречаются

• Project Euler problem 92, "Square Digit Chains", asks how many starting numbers below ten million arrive at 89 rather than 1 — a question that only makes sense because of Porges's theorem.
• Happy numbers are a standard programming-interview warm-up (LeetCode problem 202), because the iteration is a functional graph and Floyd's cycle-detection trick applies directly.
• The 2007 Doctor Who episode "42" uses happy primes as the answer to a series of door-lock puzzles.
• The primes that are also happy form their own catalogued sequence, OEIS A035497, beginning 7, 13, 19, 23, 31, 79, 97, 103.
• The digit-square map itself is catalogued as OEIS A003132 and is a common classroom example of an iteration with exactly two possible destinations.