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!
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
©2011 ACM 0001-0782/11/0800 $10.00
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 [email protected] or fax (212) 869-0481.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2011 ACM, Inc.
No entries found