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