The ever-puzzling Peter Winkler offered three problems in the August Communications of the ACM:
Does every positive integer divide some number of the form 1{0,1}*—that is, a positive integer whose decimal representation includes no digits other than 0 and 1?
Does every positive integer divide a Fibonacci number?
Is there an odd perfect number (an odd integer equal to the sum of its proper divisors)?
Answers to Problems 1 and 2 have now been published in the September CACM, so I won’t worry too much about spoiling anyone’s fun with the discussion below. Still, if you’d like to take a crack at the first two problems, do so before you read on. (As for Problem 3, you needn’t worry about my giving away the secret.)
Winkler’s solutions are based on the pigeonhole principle. If you divide successive 1{01}* numbers or successive Fibonacci numbers by any fixed integer n, the remainders necessarily lie between 0 and n–1. Furthermore, the sequence of remainders repeats cyclically. For example, the Fibonacci numbers modulo 3 are:
0 1 1 2 0 2 2 1 0 1 1 2 0 2 2 1 0 . . .
The trick is to show that the cyclic sequence of remainders always includes zero. For details see Winkler’s solution page mentioned above. (CACM is behind a paywall, but I think these links will work for nonsubscribers.) A 2007 paper by Tanya Khovanova also explains what’s going on, and gives a couple of further enticing problems.
The pigeonhole argument answers the questions as posed, but it tells us very little about the structure of the solutions. Which 1{01}* numbers and which Fibonacci numbers are divisible by various integers n? Are there any interesting patterns in the results? I was curious, so I started computing.
The graph above shows the smallest 1{01}* numbers divisible by each n from 1 through 30. The standout pattern is the series of tall flagpoles for n a multiple of 9. It appears that 1{01}* numbers that include 9 among their divisors are rarities. I didn’t foresee this pattern, although I should have. It’s connected with the long-forgotten ritual of “casting out nines,” which in turn is based on the following fact: A decimal number is divisible by 9 if and only if the sum of its digits is divisible by 9. (Question: What are the smallest 1{01}* numbers divisible by 99 and by 999? Answers at the end of this article.)
Below is the analogous graph for Fibonacci numbers divisible by values of n between 1 and 30.
There are some interesting patterns here, too, but we need a bigger sample to see them clearly.
By the way, it’s important to notice that the ordinate axis of the Fibonacci graph gives the index of each Fibonacci number, not the Fibonacci number itself. I adopt this indexing convention :
| m | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | … |
| F(m) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | … |
The diagram below offers another way of looking at the mapping from integers n (on the left) to the smallest Fibonacci number F(m) divisible by n (on the right):
A few Fibonacci numbers are highly popular—notably F(12), F(24), F(30), F(60). Indeed, F(24) is the destination of 12 of the first 100 values of n. The reason for this clustering is not a deep mystery; Fibonacci numbers of the form F(6k) tend to be very “smooth” numbers, with an abundance of small factors. F(60) is equal to 1,548,008,755,920, a number that has 960 divisors. F(240) has more than 1.3 million divisors. These smooth numbers simply have more chances to be the smallest F(m) divisible by some n.
But the clustering also highlights an asymmetry. The solution of the Winkler problem says that we can draw a line from every n on the left to a specific F(m) on the right, the least Fibonacci number divisible by that n. What about the converse? Is every F(m) the least Fibonacci number divisible by some n? Can we draw a line from every F(m) on the right to some n on the left? The diagram as shown, which covers all n up to 100, has many gaps in the set of nodes on the right; for example, none of the numbers between F(61) and F(67) are among the smallest Fibonacci numbers divisible by an n ≤ 100. If we were to extend the computation to larger values of n, would all the gaps in the righthand column eventually be filled in? Let me state that question a little more formally: For every m, is there an n that divides F(m) but does not divide F(k) for any k < m?
This is a trick question. The answer is No because of F(2), which is “shadowed” by F(1), since F(1) = F(2) = 1. But F(2) is unique in this respect. If we set aside this one exception, is the statement true for all other F(m)? Now the answer is Yes, but trivially so. Every F(m) is divisible by F(m) itself, which cannot possibly divide any F(k) with k < m. (In the case of Fibonacci numbers that are prime, F(m) and 1 are obviously the only divisors.)
To avoid the trivial solution, we need to ask a more tightly constrained question, which I’ll phrase as a conjecture:
If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.
Is the conjecture true? If so, where do all those new divisors come from? What mechanism guarantees that every nonprime F(m) will introduce at least one divisor never seen before in the sequence of Fibonacci numbers? If the conjecture is false, then there are “unselfish” Fibonacci numbers that share all their proper divisors with their smaller siblings, keeping none for their own exclusive use. What is the smallest such unselfish F(m)? (For what it’s worth, a computational search shows that any counterexample to the conjecture must lie beyond F(382).)
I’m going to leave this question as a challenge. I’ll give an answer in an update—in the unlikely event that no one posts a complete solution in the comments section in the next 10 minutes. One further note: Unselfish numbers do exist among the 1{01}* numbers; the smallest example is 1111, whose only proper divisors are 11 and 101, both of which obviously divide lesser 1{01}* numbers. Thus if you want to assert that Fibonacci numbers behave differently in this respect, you might want to think about what distinguishes the two sequences.
Finally, more about patterns of divisibility in Fibonacci numbers. The dots in the figure below show the least m such that n divides F(m) for all n up to 1,000:
It’s interesting that the dots tend to line up along certain rays, namely those whose slope is a ratio of small integers. The slopes m/n = 1 and 1/2 are the most clearly delineated, but there are also aggregations detectable by eye at m/n = 1/4, 1/3, 2/3, 3/4 and 3/2. The ray at m/n = 2 has only four data points on it in the range up to n = 1,000, but it is significant for another reason: It marks the absolute boundary of the m/n ratio. In other words, not only is it true that every n divides some F(m), but furthermore the m in question is never greater than 2n.
There is no sign of such radial streaks or other distinctive patterns in the equivalent graph for the 1{01}* numbers:
As with the Fibonacci graphs, the vertical axis here represents not the numerical magnitude of an 1{01}* number but its index within the sequence. For example, the smallest 1{01}* number divisible by 18 is 1,111,111,110, which is the 1,022nd number in the 1{01}* sequence. (It’s more than coincidence that 11111111102 = 102210.) Hence there’s a dot at n = 18 and vertical coordinate 1,022. I have colored orange all the dots associated with n that are multiples of 9. The dots along the upper margin of the graph are off-scale and actually belong at much higher elevations. For example, the dot for n = 99 should be at height 262,143 (the index of 111,111,111,111,111,111). The dot at n = 999 belongs at height 134,217,727 (the index of 111,111,111,111,111,111,111,111,111).
Update 2011-10-09: More than a month ago I promised an answer to the question posed above: Is there a composite Fibonacci number for which all the proper divisors are also divisors of smaller Fibonacci numbers? When I asked the question, I had an answer for it. But a week later when I sat down to write up the proof, it fell apart like wet tissue. Since then the problem has been constantly with me. I’ve been waking up with it in the morning; I go to bed with it at night; it comes back to visit at idle moments during the day. Several times I’ve thought I had found a solution, but then the argument fell to pieces again. If some kindly reader had posted a full proof in the comments, I could have responded, “Yes, yes, exactly so. That’s just what I had in mind.” But only one reader came to my rescue (thanks, unekdoud!); although that suggestion seemed to be heading in the right direction, I wasn’t able to fill in all the details.
Now I have yet another proof. It’s the middle of the night as I write this, but I’m going to stay up and get this posted before the idea disintegrates again.
Here, copied from above, is a more precise statement of the problem, phrased as a conjecture:
If F(m) has any divisors n with 1 < n < F(m), then at least one of those n does not divide any F(k) for k < m.
I claim the conjecture is true, based on this assertion: If every divisor of F(m) also divides some smaller F(k), then the F(k) in question cannot be greater than F(m/2), while at least one of the divisors must be no smaller than √F(m). But this is impossible, because √F(m) > F(m/2) for all m > 2. (For odd m, take the ceiling of m/2.)
The key to the proof is again the cyclic pattern of remainders observed when the members of the Fibonacci sequence are taken modulo an integer. In particular, if an integer a divides F(m), then a also divides F(2m), F(3m), F(4m), . . . For example, F(8) = 21 is divisible by 3 and 7, and these numbers are also divisors of F(16) = 987 and F(24) = 46,368.
An immediate consequence of this cyclic structure is the remarkable fact that F(k) divides F(m) if and only if k divides m. Again let me cite an example: F(15) = 610 is divisible by F(3) = 2 and by F(5) = 5 and by no other Fibonacci numbers. (The prime factors of 610 are 2, 5 and 61. Note that the factor 61 divides no smaller Fibonacci number, and so F(15) is a confirming instance of the conjecture.)
A further observation is that if m is prime, then F(m) cannot be divisible by any Fibonacci number.
Let’s look at the divisors of F(m) for composite values of m. We know that such divisors exist. They include every F(k) for which k divides m, as well as all the proper divisors of each such F(k). Suppose, contrary to the conjecture, that these known divisors comprise all the divisors of F(m). Then for each integer a that divides F(m) we can ask which F(k) it also divides. Actually, a given a might divide many F(k), but consider just the smallest member of this set. If a divides this minimal F(k), then it also divides F(2k), F(3k), and so on, but it divides no other Fibonacci numbers. Thus F(m) must be a member of this series, or in other words m must be a multiple of k. The smallest such multiple is m = 2k. This gives us half of the proof: If a divisor of F(m) also divides F(k), k can be no larger than m/2.
The second half is easier. Divisors come in pairs; they are integers a and b such that ab = F(m). Furthermore, if a ≤ √F(m), then b ≥ √F(m). Thus we conclude that b cannot be less than the square root of F(m) or more than F(m/2)—a contradiction.
The same reasoning applies with even greater force in the case of prime m. If we imagine that a divisor of F(m) is also a divisor of some smaller F(k), we are driven to the conclusion that k divides m, which can’t be so for prime m.
In the course of working all this out in my bumbling-stumbling way, while making lots of lists of Fibonacci numbers and their divisors, the patterns I was seeing suggested a slightly stronger conjecture:
Every Fibonacci number that is not a perfect power has at least one prime factor that appears in no smaller Fibonacci number.
The perfect-power exception excludes exactly five Fibonacci numbers: F(0) = 0, F(1) = 1, F(2) = 1, F(6) = 8 = 23 and F(12) = 144 = 122. No other Fibonacci numbers are perfect powers; I find it interesting that this fact was proved only in the past few years, and only with the use of industrial-grade mathematical machinery. On the other hand, “my” conjecture was proved almost a century ago by the American mathematician R. D. Carmichael. If I had known that fact a few weeks ago, I would have slept better. But maybe learned less.
I would start with the case where the Fibonacci numbers are even: F(n) is coprime to F(n-1) and is at least twice of F(n-2) for large enough n. Then F(n)/2 is a new divisor.
The argument generalizes straightforwardly for Fibonacci numbers divisible by 3, 5, and 7, using the fact that they repeat modulo these numbers.
For this argument to work for all primes it is required that they appear late enough in the sequence e.g. 11 appears as a divisor after the log(11)/log(phi) -th Fibonacci number. This seems quite plausible, given the growth rate of the sequence.
I believe I messed that one up slightly. A more accurate description of the proof would be:
If F(n) is unselfish, it shares a divisor with F(n-r) for some r, take the smallest one. The gcd of F(n) and F(n-r) is not 1, so n,n-r are not coprime. F(n) and F(n-gcd(n,r)) are not coprime, so it follows that r is the smallest prime divisor of n. Then F(n)/F(r)>F(n-r) and so doesn’t divide any number in between.
So, the reason for the new divisors would be mainly due to the divisibility properties of Fibonacci numbers, and the proof relies a bit on the growth rate. (For instance, it would certainly fail when applied to the natural numbers, which grow too slowly. However, it works as expected for the sequence consisting of the cubes of Fibonacci numbers.)
Brian, you refer to “the remarkable fact that F(k) divides F(m) if and only if k divides m.” Be careful there. Your convention has F(2)=1, which certainly divides, say F(3)=2, yet 2 does not divide 3.
I think your proof boils down to the fact that the cyclic structure of the Fibonacci numbers mod N (for any N) implies that if a number d divides both F(m) and F(k), then d divides F(gcd(m,k)), where “gcd” stands for “greatest common divisor.” If k < m (and 1 < d) , then gcd(m,k) is a proper divisor of m, hence no greater than m/2. Taking the largest possible proper divisor d gives the desired contradiction
sqrt(F(m)) ≤ d ≤ F(gcd(k,m)) ≤ F([m/2]) < sqrt(F(m))