[math-fun] Simple(?) Fib problem
For which m for do the Fibs have every residue mod m? For most things Fibonacci mod m, see Marc Renault's master's thesis. http://www.ship.edu/~msrena/math/FibThesis.html
He notes that Kuipers and Shiue proved that the only m for which they're uniformly distributed are m=5^k, k>=1, so your sequence will include all those. Jacobson published something on the distribution of Fib numbers (mod 2^i 5^j). Renault says nothing else appears to have been published on the distribution of residues for other moduli. -- Mike Stay staym@clear.net.nz http://www.cs.auckland.ac.nz/~msta039
Finally catching up on stuff from a week ago, when David Wilson said:
For which m for do the Fibs have every residue mod m?
As David Terr implicitly pointed out, if we miss a residue mod m, we do for all multiples of m as well -- so it's reasonable to ask about the prime moduli first. It's easy to check that you hit all moduli for 2,3,5,7. I just wrote the two-minute c program which tells me those are the only primes under 250,000 for which it works. I was surprised -- but perhaps only half as surprised as you, since I followed up Mike Stay's reference to Marc Renault's master's thesis, and thence to D. D. Wall's "Fibonacci Series Modulo $m$", in the Monthly (67 #6, Jun-Jul 1960, pp 525-532; on Jstor, if you have institutional access). He proves: (1) If p is +-1 mod 10, then the period of the Fib's mod p divides p-1 (2) If p is +-3 mod 10, then the period of the Fib's mod p divides 2p+2 Incidentally, the separation into these two cases is because of the sqrt(5) in the golden ratio, which either does (case 1) or doesn't (case 2) exist in the integers mod p -- that's another math-fun discussion I was just catching up on :-). Anyway, since there are p residues mod p, this immediately tells us that primes ending in 1 or 9 can't possibly have all the moduli. (That's why I was only half as surprised.) If it really is true that 2/3/5/7 are the only primes that have all the moduli, we're playing a game of four-dimensional chomp, and there is a finite set of "minimal" (with respect to the divisor ordering) numers which fail, and all others succeed. We know easily that 8 and 49 fail, limiting our growth in that direction. Again from Mike Stay's reference, we know that all powers of 5 succeed. I just checked up to 3^14 and 15^7 and those both succeed. Oh, and 18, 21 and 28 are in the minimal fail set -- probably that all has to do with non-relatively-prime periods, but I haven't had the time to think about that. Go ahead, someone, prove it fails for all primes over one digit, and succeeds for 15^n for all n... --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.
David Wilson asked:
For which m for do the Fibs have every residue mod m?
A quick search reveals: 1 2 3 4 5 6 7 9 10 14 15 20 25 27 30 35 45 50 70 75 81 100 125 135 150 175 225 243 250 350 375 405 500 625 675 729 750 875 1125 1215 1250 1750 1875 2025 2187 2500 3125 3375 3645 3750 4375 5625 6075 6250 6561 8750 9375 (extended after 500 by David Wilson) The number of different residues of Fibonacci's mod M for M from 1 to 100 is: 1,2,3,4,5,6,7,6,9,10,7,11,9,14,15,11,13,11,12,20,9,14,19,13,25,18,27,21, 10,30,19,21,19,13,35,15,29,13,25,30,19,18,33,20,45,21,15,15,37,50,35,30, 37,29,12,25,33,20,37,55,25,21,23,42,45,38,51,20,29,70,44,15,57,58,75,13, 35,50,49,55,81,38,63,27,65,66,27,32,17,55,53,29,53,30,60,26,69,74,41,100 So the i for which a[i]=i in the latter series make up the former series. Both of these are have now been submitted to the OEIS as A102380 and A102381 Ron Knott www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci
participants (4)
-
David Wilson -
M. Stay -
Michael Kleber -
Ron