Last byte

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.
  1. Article
  2. Author
  3. Footnotes
Peter Winkler scrambled

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





137,348,691,328; and


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!

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More