In Fibonacci base, everything is clear. A proof can be derived from this transcript easily. I show it for the 18th Lucas number 9349. Only the nth Lucas numbers for even n show this exact pattern. The resulting lower bound is always F(n+2) + F(n-1). rokicki@MacBook-Pro ~ % python fibmod2.py 18 Lucas number 18: 1010000000000000000 9349 Resulting lower bound: 0000000000000000001 1 0000000000000000010 2 0000000000000000100 3 0000000000000001000 5 0000000000000010000 8 0000000000000100000 13 0000000000001000000 21 0000000000010000000 34 0000000000100000000 55 0000000001000000000 89 0000000010000000000 144 0000000100000000000 233 0000001000000000000 377 0000010000000000000 610 0000100000000000000 987 0001000000000000000 1597 0010000000000000000 2584 0100000000000000000 4181 1000000000000000000 6765 0001000000000000000 1597 1001000000000000000 8362 0000010000000000000 610 1001010000000000000 8972 0000000100000000000 233 1001010100000000000 9205 0000000001000000000 89 1001010101000000000 9294 0000000000010000000 34 1001010101010000000 9328 0000000000000100000 13 1001010101010100000 9341 0000000000000001000 5 1001010101010101000 9346 0000000000000000010 2 1001010101010101010 9348 0000000000000000001 1 0000000000000000000 0 0000000000000000001 1 8362 On Fri, Oct 9, 2020 at 3:17 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Okay, I don't have a proof but I have *very* strong evidence.
Consider as moduli the Lucas numbers starting with (2,1). These start 2,1,3,4,7,11,18,29,...
Iterate the Fibonacci sequence modulo these; it will repeat when the sequence 1,1 shows up again. This happens very quickly for these moduli. Consider 11:
1,1,2,3,5,8,2,10,1,0,1,1,...
The minimum still possible value of n is the lowest value that appears in this sequence that is not a Fibonacci number. For the above sequence, that value is 10.
For the Lucas number 29, that value is 26.
Here is a table for the first few values:
4 4 7 4 11 10 18 10 29 26 47 26 76 68 123 68 199 178 322 178 521 466 843 466 1364 1220 2207 1220 3571 3194 5778 3194
This pattern continues; the minimum value still possible always appears to be of the same order of magnitude of these exceptional moduli.
Indeed, if you see that that second column satisfies the recurrence F(n) = 3 F(n-2) - F(n-4) and this grows exactly as fast as the Lucas and Fibonacci sequences.
So, to generate a lower limit with N digits, just generate a Lucas number with N+1 digits, and iterate the operation above.
How to prove this? Let's start with this. Lucas(N) = Fib(N) + Fib(N-2). This can be shown by induction.
Fib(2N) = (Fib(N+1)+Fib(N-1))*(Fib[N+1]-Fib[N-2])
so Fib(2N) is divisible by Lucas(N+1). This gives us our zero.
A bit more algebra with the Fibonacci sequences will show us that the sequence does indeed repeat at 2(N-1).
Then we need to figure out what the smallest value is that is not a Fibonacci number. And a bit more.
So I don't have a proof but the clear and straightforward nature of the sequence shows that there likely is a simple proof. And if you don't like the proof, just generate an arbitrarily large Lucas number and calculate the sequence above and you'll prove as large a lower bound as you have cycles for, in polylog time.
For instance, to prove a lower bound with 20,000 digits took under 3 seconds on my laptop.
-tom
On Fri, Oct 9, 2020 at 2:06 PM Tomas Rokicki <rokicki@gmail.com> wrote:
Just a few more minutes raises the limit to this:
24524920689683934612523815466510509898977114040073848370088830506614177804428792983800066702703080692136684365181903088684884343920553287594894772073041785466123008435725367696575050925379097143890123169555297567493687565236627642109260606865191349252713802534939006333041841571236727111758337703161241471270261635988459529545920123394624337400037677377619985418743172798689446836259406446091967885994585159218873682917457765198388770816496360584258785017529237898784829543352882111310293679268695489382196534568966648325
-tom
On Fri, Oct 9, 2020 at 2:01 PM Tomas Rokicki <rokicki@gmail.com> wrote:
If there is, it must be greater than
276792026060022456497058911697376830627911091457539277300827264605865506146172478305720990198054221114105111525234958335011060935983844946443475003682525687205923438462532622519320479701851802392
This is the smallest number that is not a Fibonacci number that is not excluded by this modulus:
5752028405020859396395768625940010545359026815479616133477751814335827064308752092084424225510402022972844755481554083297677086937356202818322021388807601850180058538115156217193711471626944740035227
I suspect there's a simple proof that there is no such number.
Raising the limit above is straightforward; that's from a few minutes of CPU time.
-tom
On Thu, Oct 8, 2020 at 8:07 PM James Propp <jamespropp@gmail.com> wrote:
Does there exist a positive integer n that isn’t a Fibonacci number, such that for every modulus m there is a Fibonacci number congruent to n mod m?
Jim Propp _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --
-- -- http://cube20.org/ -- http://golly.sf.net/ --