Communications of the ACM

Last byte

Puzzled: Uncommon Divisors

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 x 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 x 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!

Author

Peter Winkler (puzzled@cacm.acm.org) is Professor of Mathematics and of Computer Science and Albert Bradley Third Century Professor in the Sciences at Dartmouth College, Hanover, NH.

Footnotes

All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and full citation on the first page. Copyright for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or fee. Request permission to publish from permissions@acm.org or fax (212) 869-0481.