last byte

DOI: 10.1145/1978542.1978567
Peter Winkler

Puzzled
uncommon Divisors

Welcome to three new puzzles. Solutions to the first two will be published next month; the third is (as yet) unsolved. In fact, this time it’s a famously unsolved problem.

The theme is divisibility. A number n is said to divide a number m, written “n|m”, if m is an integer multiple of n; for example, “m is even” is the same as saying 2 divides m.

1.Does every positive integer divide some number whose representation (base 10) contains only zeroes and ones? For example, if we start computing multiples of 7, we find that 1,001 = 7 × 143 is among them. Then again, maybe 7 is just a lucky number.

2.Does every positive integer divide some Fibonacci number? Recall that the Fibonacci numbers begin 1, 1, after which each is the sum of the previous two; 1, 1, 2, 3, 5, 8, 13, 21, 34…; for example, 7 works (again), since 7 × 3 = 21, or the eighth Fibonacci number.

3.A perfect number m is a positive integer that is the sum of its proper divisors; that is, the sum of all n less than m, such that n|m. The first perfect number is 6; 1, 2, and 3 are its proper positive divisors, and 1 + 2 + 3 = 6. The next perfect number is 28 = 1 + 2 + 4 + 7 + 14, and the next six are

496; 8128; 33,550,336; 8,589,869,056; 137,348,691,328; and 2,305,843,008,139,952,128.

The first four perfect numbers were known in ancient Greece; the eighth goes back to Swiss mathematician Leonhard Euler in 1772.

Note that all these numbers—in fact all 47 known perfect numbers—are even. The even perfect numbers are in a sense well understood, each of the form 2p− 1(2p− 1), where both p and 2p− 1 are prime numbers (no divisor other than 1 and themselves).

Unfortunately, it is difficult to tell for which primes p the number 2p− 1 is also prime; we don’t even know whether there are infinitely many such primes p. Thus, we don’t know if there are infinitely many perfect numbers, either.

Are there any odd perfect numbers? Major brainpower has been expended on this problem, over centuries, yet it remains tantalizingly open. Warning: If you are trying to find an odd perfect number by computer, please know that all odd numbers with 300 or fewer digits have already been checked.

Lots of information on perfect numbers is available from Wikipedia and other sources. My Dartmouth colleague Carl Pomerance, an expert in the area, can make a persuasive argument that odd perfect numbers probably don’t exist. If you prove they don’t exist, you will be famous!

All readers are encouraged to submit prospective puzzles for future columns to [e-mail]. Peter Winkler ( [e-mail]) is Professor of mathematics and of computer science and albert bradley third century Professor in the sciences at dartmouth college, hanover, Nh.