[math-fun] Pseudo-Fibonacci numbers?
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
Perhaps I have misunderstood how the quantifiers are scoped an this question. I recall being convinced that the Fibonacci numbers hit all residue classes, in which case every integer is "pseudo-Fibonacci". If this is not true, can you name a residue class that contains no Fibonacci numbers? On Thu, Oct 8, 2020, 11: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
No Fibonacci number is congruent to 4 or 6 mod 8. See http://oeis.org/A066853 (the sequence that gives the number of "Fibonacci residue classes" mod m for m=1,2,3,...) and http://oeis.org/A079002 (the sequence of moduli such that the Fibonacci numbers fill all m possible residue classes). Jim On Fri, Oct 9, 2020 at 8:10 AM Allan Wechsler <acwacw@gmail.com> wrote:
Perhaps I have misunderstood how the quantifiers are scoped an this question. I recall being convinced that the Fibonacci numbers hit all residue classes, in which case every integer is "pseudo-Fibonacci". If this is not true, can you name a residue class that contains no Fibonacci numbers?
On Thu, Oct 8, 2020, 11: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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Oh, gosh. I stopped enumerating just shy of mod 8, and missed these. I now see the point of this question. Mod 8 misses 4 and 6; mod 11 misses 4, 6, 7, and 9. Unexpectedly, the missed sets get repeated: 12 misses 4 and 6, like 8; and 13 misses 4, 6, 7, and 9, like 11. 16 misses 4, 6, 10, 12, 14. So far, every modulus that misses any residue at all, misses 4 and 6. Does that remain true? Does OEIS have a sequence that tells which modulus first misses n? I can't find it because I can't guess how it handles residues (like the Fibonacci numbers) that are never missed. On Fri, Oct 9, 2020 at 9:15 AM James Propp <jamespropp@gmail.com> wrote:
No Fibonacci number is congruent to 4 or 6 mod 8.
See http://oeis.org/A066853 (the sequence that gives the number of "Fibonacci residue classes" mod m for m=1,2,3,...) and http://oeis.org/A079002 (the sequence of moduli such that the Fibonacci numbers fill all m possible residue classes).
Jim
On Fri, Oct 9, 2020 at 8:10 AM Allan Wechsler <acwacw@gmail.com> wrote:
Perhaps I have misunderstood how the quantifiers are scoped an this question. I recall being convinced that the Fibonacci numbers hit all residue classes, in which case every integer is "pseudo-Fibonacci". If this is not true, can you name a residue class that contains no Fibonacci numbers?
On Thu, Oct 8, 2020, 11: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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Maybe I should've asked the following (probably easier) question first: Does there exist a positive integer n that isn’t a power of 2, such that for every odd modulus m there is a power of 2 congruent to n mod m? A negative answer would follow from the existence of infinitely many Mersenne primes, but maybe there's an easier way to prove that no such n exist. Jim Propp On Fri, Oct 9, 2020 at 10:43 AM Allan Wechsler <acwacw@gmail.com> wrote:
Oh, gosh. I stopped enumerating just shy of mod 8, and missed these.
I now see the point of this question. Mod 8 misses 4 and 6; mod 11 misses 4, 6, 7, and 9.
Unexpectedly, the missed sets get repeated: 12 misses 4 and 6, like 8; and 13 misses 4, 6, 7, and 9, like 11. 16 misses 4, 6, 10, 12, 14.
So far, every modulus that misses any residue at all, misses 4 and 6. Does that remain true?
Does OEIS have a sequence that tells which modulus first misses n? I can't find it because I can't guess how it handles residues (like the Fibonacci numbers) that are never missed.
On Fri, Oct 9, 2020 at 9:15 AM James Propp <jamespropp@gmail.com> wrote:
No Fibonacci number is congruent to 4 or 6 mod 8.
See http://oeis.org/A066853 (the sequence that gives the number of "Fibonacci residue classes" mod m for m=1,2,3,...) and http://oeis.org/A079002 (the sequence of moduli such that the Fibonacci numbers fill all m possible residue classes).
Jim
On Fri, Oct 9, 2020 at 8:10 AM Allan Wechsler <acwacw@gmail.com> wrote:
Perhaps I have misunderstood how the quantifiers are scoped an this question. I recall being convinced that the Fibonacci numbers hit all residue classes, in which case every integer is "pseudo-Fibonacci". If this is not true, can you name a residue class that contains no Fibonacci numbers?
On Thu, Oct 8, 2020, 11: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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
12 doesn't miss 4; 2584 % 12 == 4. On Fri, Oct 9, 2020 at 7:43 AM Allan Wechsler <acwacw@gmail.com> wrote:
Oh, gosh. I stopped enumerating just shy of mod 8, and missed these.
I now see the point of this question. Mod 8 misses 4 and 6; mod 11 misses 4, 6, 7, and 9.
Unexpectedly, the missed sets get repeated: 12 misses 4 and 6, like 8; and 13 misses 4, 6, 7, and 9, like 11. 16 misses 4, 6, 10, 12, 14.
So far, every modulus that misses any residue at all, misses 4 and 6. Does that remain true?
Does OEIS have a sequence that tells which modulus first misses n? I can't find it because I can't guess how it handles residues (like the Fibonacci numbers) that are never missed.
On Fri, Oct 9, 2020 at 9:15 AM James Propp <jamespropp@gmail.com> wrote:
No Fibonacci number is congruent to 4 or 6 mod 8.
See http://oeis.org/A066853 (the sequence that gives the number of "Fibonacci residue classes" mod m for m=1,2,3,...) and http://oeis.org/A079002 (the sequence of moduli such that the Fibonacci numbers fill all m possible residue classes).
Jim
On Fri, Oct 9, 2020 at 8:10 AM Allan Wechsler <acwacw@gmail.com> wrote:
Perhaps I have misunderstood how the quantifiers are scoped an this question. I recall being convinced that the Fibonacci numbers hit all residue classes, in which case every integer is "pseudo-Fibonacci". If this is not true, can you name a residue class that contains no Fibonacci numbers?
On Thu, Oct 8, 2020, 11: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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ 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/ --
Bleah. I should leave this investigation to the pros :) On Fri, Oct 9, 2020 at 12:52 PM Tomas Rokicki <rokicki@gmail.com> wrote:
12 doesn't miss 4; 2584 % 12 == 4.
On Fri, Oct 9, 2020 at 7:43 AM Allan Wechsler <acwacw@gmail.com> wrote:
Oh, gosh. I stopped enumerating just shy of mod 8, and missed these.
I now see the point of this question. Mod 8 misses 4 and 6; mod 11 misses 4, 6, 7, and 9.
Unexpectedly, the missed sets get repeated: 12 misses 4 and 6, like 8; and 13 misses 4, 6, 7, and 9, like 11. 16 misses 4, 6, 10, 12, 14.
So far, every modulus that misses any residue at all, misses 4 and 6. Does that remain true?
Does OEIS have a sequence that tells which modulus first misses n? I can't find it because I can't guess how it handles residues (like the Fibonacci numbers) that are never missed.
On Fri, Oct 9, 2020 at 9:15 AM James Propp <jamespropp@gmail.com> wrote:
No Fibonacci number is congruent to 4 or 6 mod 8.
See http://oeis.org/A066853 (the sequence that gives the number of "Fibonacci residue classes" mod m for m=1,2,3,...) and http://oeis.org/A079002 (the sequence of moduli such that the Fibonacci numbers fill all m possible residue classes).
Jim
On Fri, Oct 9, 2020 at 8:10 AM Allan Wechsler <acwacw@gmail.com> wrote:
Perhaps I have misunderstood how the quantifiers are scoped an this question. I recall being convinced that the Fibonacci numbers hit all residue classes, in which case every integer is "pseudo-Fibonacci". If this is not true, can you name a residue class that contains no Fibonacci numbers?
On Thu, Oct 8, 2020, 11: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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ 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/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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/ --
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/ --
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/ --
Tom, Instead of considering the 2N - 2 numbers: {F(0), F(1), F(2), ..., F(2N - 3)} modulo Lucas(N), can't you instead consider the (same!) 2N - 2 numbers: {F(2 - N), F(3 - N), ..., F(N - 2), F(N - 1)} modulo Lucas(N)? I think this avoids the annoying 'overflow'. Best wishes, Adam P. Goucher
Sent: Friday, October 09, 2020 at 11:17 PM From: "Tomas Rokicki" <rokicki@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Pseudo-Fibonacci numbers?
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/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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/ --
Very nice! I wonder if the result is new? (If I had the time I'd submit it to the Monthly, with Tomas' elegant solution.) By the way, my analogous question about powers of 2 is trivial. You don't need to have infinitely many Mersenne primes to argue that no such n exists; just having infinitely many Mersenne *numbers* (to serve as moduli) will suffice! Jim On Fri, Oct 9, 2020 at 7:24 PM Tomas Rokicki <rokicki@gmail.com> wrote:
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/ -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Adam P. Goucher -
Allan Wechsler -
James Propp -
Tomas Rokicki