Fran�ois Perruchaud wrote:
>An old book of mine gives without proof an example of Fibonacci Sequence
>that countains no primes, but where U(1) and U(2) are co-prime.
>The sequence was found by R. L. Graham.
>Reference :
>"A Fibonacci-like sequence of composite numbers",
>R.L. Graham, Math. Mag. 37, 1964.
>
>U(1) = 1786772701928802632268715130455793
>U(2) = 1059683225053915111058165141686995
>U(N+2) = U(N+1) + U(N)
>
>I only verified with Mapple that U(1) and U(2) are co-prime
>and that U(N) is composite for N<10.
Unfortunately, Graham made a computational error in calculating U(1) and
U(2), and the above values don't work as desired. The following will
correct the error:
U(1) = 331635635998274737472200656430763
U(2) = 1510028911088401971189590305498785
U(N+2) = U(N+1) + U(N)
The trick is to create a "covering" of the indices, i.e. a set of
congruences such that every index satisfies at least one of the
congruences. The best way to understand this is by this example. Note
that F(4) is divisible by 3, and that every 4th term in the Fibonacci
sequence is also divisible by 3, i.e. the period of 3 is equal to 4.
Using the U() series instead of the F() series, it can be verified that
U(4n+2) is divisible by 3 for all n. Similarly,
U(8n+4) is divisible by 7
U(16n+8) is divisible by 47
U(32n+16) is divisible by 2207
U(64n+32) is divisible by 1087
U(64n) is divisible by 4481
This assures that U(2n) is composite for all n, since every even number
is either 2 mod 4, 4 mod 8, 8 mod 16, 16 mod 32, 32 mod 64, or 0 mod 64.
Note that F(8)/F(4) = 7, F(16)/F(8) = 47, F(32)/F(16) = 2207,
F(64)/F(32) = 1087*4481.
For the odd indices, consider separately the cases 6n+1, 6n+3 and 6n+5.
First, the period of 2 is 3, and U(6n+3) is divisible by 2 for all n (in
fact, U(3n) is divisible by 2, but at this point we only need the odd
values). For 6n+5, we have
U(18n+5) is divisible by 17 (actual period = 9)
U(18n+11) is divisible by 19
U(54n+17) is divisible by 53 (actual period = 27)
U(54n+35) is divisible by 109 (actual period = 27)
U(54n+53) is divisible by 5779
which covers all the cases U(6n+5). For 6n+1, we have
U(30n+7) is divisible by 5 (actual period = 5)
U(30n+13) is divisible by 11 (actual period = 10)
U(30n+19) is divisible by 61 (actual period = 15)
U(30n+25) is divisible by 31
U(60n+1) is divisible by 2521
U(60n+31) is divisible by 41 (actual period = 20)
which covers all the cases U(6n+1). This completes the coverage of all
cases, thus U(n) is composite for all n.
Graham's error was that his original U(1) and U(2) gave U(64n+33)
divisible by 1087, rather than U(64n+32). This doesn't mean necessarily
that any U(n) was prime in his original sequence, only that U(n) could
not easily be proved composite.
Regards,
Bill
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
