Number — page 5
A small quotient for every denominator
Pick a denominator, any whole number. Among the fractions with that denominator, is there always one whose continued fraction has no large entries — whose path down the Stern–Brocot tree never turns the same way more than five times running? Stanisław Zaremba guessed so in 1972, for a reason to do with sampling a square evenly. Every denominator up to a hundred thousand obeys, with only 6, 54 and 150 needing a five. The guess is proved for almost every denominator and not for all, and the reason it ought to be true is a dimension: the reals whose quotients stay at most five fill a set of dimension 0.837, enough to give each denominator thousands of good fractions on average, and the open question is whether averages are kept everywhere.
How close two sums of square roots come
Two different sums of square roots of whole numbers are never equal: square roots of different squarefree numbers are independent, so no cancellation can make them agree. But they can come very close. Among sums of two square roots of numbers up to 320, √88 + √289 and √171 + √177 agree to eight decimal places. How many digits must be computed, in the worst case, to tell two such sums apart is not known — the best proof allows a number of digits doubly exponential in the length of the sums, the examples suggest only a modest polynomial, and the gap between them is why nobody knows whether the shortest route through points in the plane can be checked quickly.
A quarter of the bases at most
Carmichael numbers pass Fermat's test for every base they share no factor with, so Fermat's test can be fooled for ever. Watch the squarings on the way to aⁿ⁻¹ instead, and a prime allows only one pattern; 561 lets just 10 of its 320 bases through, and Monier and Rabin proved that no odd composite but 9 lets through more than a quarter. Four fixed bases prove every number below 3.2 billion prime or not.
Most numbers are missing from the table
An N × N multiplication table has N² cells, and every product in it is less than or equal to N². Yet only 22.5% of the numbers that small turn up in the 10,000 × 10,000 table, and the share keeps falling. Erdős proved in 1955 that it falls to nought; Kevin Ford found in 2008 how slowly — like a tiny power of the logarithm, 0.0861 — because a product of two numbers has too many prime factors to be typical.
Divisors that take a prime whole
Six is perfect because its proper divisors 1, 2 and 3 add up to 6. Keep only the divisors that take each prime of a number completely or not at all — for 60, that is 1, 3, 4, 5, 12, 15 and 20 — and ask for the same coincidence. Below ten million it happens four times: 6, 60, 90 and 87,360. The fifth has twenty-four digits. And unlike ordinary perfect numbers, where nobody knows whether an odd one exists, here a two-line argument rules every odd number out.
Nineteen fourth powers, and then sixteen
Edward Waring claimed in 1770 that every number is a sum of at most nineteen fourth powers. It is true, and it is needed: 79 takes nineteen, because its remainder on division by sixteen forces fifteen ones. But only seven numbers need nineteen, the last of them 559; the last to need eighteen is 1,248, and the last to need seventeen is 13,792. Counting every number to ten million shows the stragglers thinning out and the one obstruction that never goes away — the remainder modulo sixteen, which makes 31, 496, 7,936 and every 31·16ᵐ need sixteen for ever.
The largest amount two coins cannot pay
With coins of 5 and 7, the amounts 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 and 23 cannot be paid, and everything else can. Two lines of argument give the formula ab − a − b for the last gap, and half the rest of the board is gaps. For three coins no such formula exists, in a sense that can be proved. And the sets that coins can make have a count that climbs at the golden ratio, a conjecture settled from a table of 67, 118, 204.
Numbers that never make a prime
Multiply 78,557 by a power of two and add one. The result is never prime, for any power, though almost every other odd number gives a prime within a few doublings. The reason is that seven small primes take it in turn to divide the result, on a schedule repeating every 36 steps that leaves no step uncovered. Proving nothing smaller does this has taken sixty years of search, and five candidates are still running.
Sums with too few primes
Add 2 to 6,436,341 and the sum is 23⁵: three numbers with only four primes between them, and their product 15,042 is far smaller than the sum. The abc conjecture says this can happen only so far. Of 606 such triples up to 200,000, only seven reach quality 1.4, and if the conjecture holds, Fermat's last theorem and much else follows for large exponents in a line.
The comet Goldbach left behind
Count the ways each even number is a sum of two primes, and the points do not form a smear. They split into bands: 12,000 has 302 ways and 12,002 has 115. One small product over odd prime factors explains every band and brings them all to a single line, and it says the count grows without bound. Nobody can prove the count is never nought.