Author |
Topic: Primes in Certain Sequences (Read 1070 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Primes in Certain Sequences
« on: Apr 4th, 2007, 12:34am » |
 Quote  Modify
|
Consider the following statement:
Given any two relatively prime integers a, d, the sequence a, a+d, a+2d, … contains infinitely many prime numbers.
This statement is known as Dirichlet theorem, resists simple proofs and was occasionally mentioned on this forum (mainly by Eigenray).
Consider now the following statement:
Given any two relatively prime integers a, d, the sequence a, a+d, 2a+d, 3a+2d, 5a+3d, 8a+5d… contains infinitely many prime numbers.
(The coefficients for a, d are Fibonacci numbers). Is this modified statement still a theorem?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Primes in Certain Sequences
« Reply #1 on: Apr 4th, 2007, 1:37am » |
Quote Modify
|
Wouldn't it be simpler to pose the sequence as
f(0)=d
f(1)=a
f(n)=f(n-1)+f(n-2)
?
For the normal fibonacci sequence its unknown whether there are infinitely many primes. So that at least is not much help. Aside from that it's very unlikely we can proof that there are in general infinitely many in the above sequence.
We might however find a counter example.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Primes in Certain Sequences
« Reply #2 on: Apr 4th, 2007, 2:21am » |
Quote Modify
|
on Apr 4th, 2007, 1:37am, towr wrote:Wouldn't it be simpler to pose the sequence as
f(0)=d
f(1)=a
f(n)=f(n-1)+f(n-2)
?
|
|
Yes.
Quote:| We might however find a counter example. |
|
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Primes in Certain Sequences
« Reply #3 on: Apr 4th, 2007, 1:44pm » |
Quote Modify
|
Interesting question...
My guess is: we should try to come up with a sequence such that all numbers are composite.
(If not, it would probably be very hard!)
|
| « Last Edit: Apr 4th, 2007, 1:44pm by Aryabhatta » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Primes in Certain Sequences
« Reply #4 on: Apr 4th, 2007, 2:42pm » |
Quote Modify
|
I did a quick computer search of the first 1000 terms of all sequences with a, d < 1000 (using a Miller-Rabin probable prime test), and the only sequence without a (strong probable) prime past the 10th term is a = 127, d = 191, so that would appear to be a good one to investigate further...
The first few terms (* = prime): 191*, 127*, 318, 445, 763, 1208, 1971, 3179, 5150, 8329*, 13479, 21808, 35287, 57095, 92382, 149477, 241859, 391336, 633195, 1024531, 1657726, 2682257, 4339983, 7022240, 11362223, 18384463, ...
Edit: that search was just with a, d prime. Searching with a, d relatively prime finds a = 479, d = 459 which has no other primes in the first 1000 terms.
--SMQ
|
| « Last Edit: Apr 4th, 2007, 3:14pm by SMQ » |
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Primes in Certain Sequences
« Reply #5 on: Apr 4th, 2007, 6:38pm » |
Quote Modify
|
The following might also work (and should be fast):
Let M = P1P2...Pk be a product of distinct primes, and let T be the period of Fibonacci mod M. [For instance if M=200560490130, T is only 5040.]
Then for each pair a,d, compute the sequence mod M. If none of the first T terms are relatively prime to M, we're golden.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Primes in Certain Sequences
« Reply #6 on: Apr 4th, 2007, 6:59pm » |
Quote Modify
|
It would suffice to show that there exists an integer T such that there are at least T primes P for which k(P) | T, where k(P) denotes the period of Fibonacci mod P. Does such exist?
[Edit: no]
|
| « Last Edit: Apr 4th, 2007, 10:47pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Primes in Certain Sequences
« Reply #7 on: Apr 4th, 2007, 7:23pm » |
Quote Modify
|
on Apr 4th, 2007, 2:42pm, SMQ wrote:| The first few terms (* = prime): 191*, 127*, 318, |
|
Terms number 1981, 5829, 9912, and 10000 also seem to be prime. The latter has 2092 digits; I can't imagine proving those are the only ones.
Quote:| a = 479, d = 459 which has no other primes in the first 1000 terms. |
|
But the 1111th term,
522545734876952223551697852773936617891835966723166670252255251119829209 191515287055933089364782214958920029521841489300385535008494056322537895 581631722815324899986846974762342861221762304588764595042171101285179032 9954066498272455051
is apparently prime, as is the 4573rd 
|
| « Last Edit: Apr 4th, 2007, 7:27pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Primes in Certain Sequences
« Reply #8 on: Apr 4th, 2007, 7:52pm » |
Quote Modify
|
I was being short-sighted: it suffices to find a covering system of the form
{a1 mod L(p1), ..., an mod L(pn)},
where the pi are distinct primes, and L(p) is the first occurence of 0 in the Fibonacci sequence mod p [or, L(p) is the order of the Fibonacci matrix in the group PGL(2,Zp)]. So L(p) | k(p), and is generally smaller: the sequence starts
{L(p)} = {3, 4, 5, 8, 10, 7, 9, 18, 24, 14, ....}
If we factor F(m), then the number of new primes (that don't divide any smaller F) is the number of times m appears in {L(p)}. Thus sorting {L(p)} gives the multiset:
{3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19, 19, 20, 21, 22, 23, ...}
Do you see any covering systems? Is there an efficient algorithm to find a (finite) covering system given a multiset of potential moduli? It would probably be wise to restrict to a small set of prime factors; taking only those terms divisible by 2 or 3 gives
{3, 4, 8, 9, 16, 18, 24, 27, 27, 32, 36, 48, 54, 64, 64, 72, 81, 81, 81, 96, 96, 108, 128, 128, 144, 162, 162, 192, 216, 216, 243, 243, 256, 256, ...}.
The sum of the reciprocals is about 1.3, which doesn't leave too much room for overlap. Throwing in powers of 5 gives us the extra terms
{5, 10, 15, 20, 25, 30, 40, 45, 50, 50, 60, 75, 80, 80, 90, 90, 100, 100, 120, 120, 125, 135, 150, 150, 160, 180, 200, 200, 225, 240, 250, 250, 250, 270, 270, 270, 270, ...}
bringing the reciprocal sum up to ~ 2.1. This might be enough. Certainly, if there exists one (and I'm guessing there does), we can certainly find it in finite time. Although it may be possible to give a non-constructive proof that a covering system exists, using, for instance, the fact that L(p) divides p, p-1, or p+1 (depending on whether p=5, p=1,4 mod 5, or p=2,3 mod 5).
|
| « Last Edit: Apr 5th, 2007, 12:19am by Eigenray » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Primes in Certain Sequences
« Reply #9 on: Apr 5th, 2007, 4:28am » |
Quote Modify
|
on Apr 4th, 2007, 7:23pm, Eigenray wrote:| Terms number 1981, 5829, 9912, and 10000 also seem to be prime. [...] But the 1111th term [...] is apparently prime, as is the 4573rd |
|
I was afraid of that, but I didn't have time to check further last night...
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Primes in Certain Sequences
« Reply #10 on: Apr 5th, 2007, 2:16pm » |
Quote Modify
|
on Apr 4th, 2007, 7:52pm, Eigenray wrote:| Do you see any covering systems? |
|
There may very well be a more compact one, but after fiddling around by hand for a bit, here's one:
{ 2 (mod 4), 4 (mod 8), 8 (mod 16), 16 (mod 32), 0 (mod 64), 32 (mod 64),
1 (mod 3), 3 (mod 9), 9 (mod 27), 18 (mod 27), 0 (mod 81), 27 (mod 81), 54 (mod 81),
1 (mod 5), 5 (mod 10),
15 (mod 18),
5 (mod 24), 17 (mod 48), 41 (mod 96), 89 (mod 96),
23 (mod 30), 47 (mod 60), 59 (mod 120), 119 (mod 120) }
Edit: removed a few superfluous terms
--SMQ
|
| « Last Edit: Apr 5th, 2007, 2:26pm by SMQ » |
IP Logged |
--SMQ
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Primes in Certain Sequences
« Reply #11 on: Apr 5th, 2007, 7:11pm » |
Quote Modify
|
Wow. That was quick. I love this site.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Primes in Certain Sequences
« Reply #12 on: Apr 5th, 2007, 7:27pm » |
Quote Modify
|
on Apr 5th, 2007, 2:16pm, SMQ wrote:| after fiddling around by hand for a bit, here's one: |
|
Nice! How did you find it?
Using this covering system, we have that if
a = 893934228206978864976613230035095733763653193610487581
d = 2139355150758502900248707105226107495572833385154458969
then every term in the corresponding sequence is divisible by one of:
{3, 7, 47, 2207, 1087, 4481, 2, 17, 53, 109, 2269, 4373, 19441, 5, 11, 19, 23, 1103, 769, 3167, 31, 2521, 241, 20641}
In detail: set
R = {2, 4, 8, 16, 0, 32, 1, 3, 9, 18, 0, 27, 54, 1, 5, 15, 5, 17, 41, 89, 23, 47, 59, 119}
M = {4, 8, 16, 32, 64, 64, 3, 9, 27, 27, 81, 81, 81, 5, 10, 18, 24, 48, 96, 96, 30, 60, 120, 120}
P = {3, 7, 47, 2207, 1087, 4481, 2, 17, 53, 109, 2269, 4373, 19441, 5, 11, 19, 23, 1103, 769, 3167, 31, 2521, 241, 20641}.
Then R mod M is a covering system, and P | F(M). Let
A = {1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
D = {1, 3, 23, 1103, 1, 2240, 1, 7, 28, 100, 1, 1426, 9810, 4, 5, 10, 3, 419, 584, 2924, 3, 758, 2, 0}.
These are chosen so that P | A*F(R+1) + B*F(R). Finally let a = A mod P, d = D mod P. [And check that a,d are in fact relatively prime.]
Now for any n, n = Ri mod Mi for some i, and so, for that i, Pi | a*F(n+1) + d*F(n).
Similar ideas were used in finding Garden of Eden primes.
|
| « Last Edit: Apr 5th, 2007, 7:59pm by Eigenray » |
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Primes in Certain Sequences
« Reply #13 on: Apr 6th, 2007, 3:49am » |
Quote Modify
|
Excellent analysis, SMQ and Eigenray!
That’s the way R. Graham found the first such sequence back in 1964. His covering system included 18 sequences, with the largest prime in P being 4481, and the largest period 64. His pair a, b contained 33 and 34 digits respectively.
Sequence with the smallest numbers a, b known so far was found in 2004. It is generated by two numbers of 12 and 11 digits. It contains 17 sequences, largest prime 2521 and largest period 90.
|
| « Last Edit: Apr 6th, 2007, 3:50am by Barukh » |
IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Primes in Certain Sequences
« Reply #14 on: Apr 6th, 2007, 4:13am » |
Quote Modify
|
on Apr 5th, 2007, 7:27pm, Eigenray wrote:| Nice! How did you find it? |
|
Pretty much the way I laid it out; I started with the "almost" coverings from available powers of 2 (covers 1 of every 2) and 3 (covers 2 of every 3 except 1 of every 9); those plus 18 can cover 5 of every 6, and together with the multiples of 24 cover 11 of every 12.
I spent a while trying without success to cover the remaining 1 in 12 with 36, 72, 108, 144, etc. but couldn't put together enough of them. I even generated the rest of L(p) through 1000 from the factors given here only to find that 288 and 576 still only have one L(p) each, and so abandoned that track and moved on to fives.
I initially had 5, 10, 20, 40, 80, 80 covering 2 of every 5, leaving 3 of every 60 uncovered. Those gaps I filled with the 30, 60, 120, 120 sequence. Then when I looked back over it I realized that the 20, 40 and 80 terms were unneeded.
If I'd just thought about in terms of covering 5 of 60 instead of 1 of 12, I probably would have chosen 5, 10, 15, 20, 30 instead of the 5, 10, 30, 60, 120, 120 I ended up with.
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
|
Re: Primes in Certain Sequences
« Reply #15 on: Apr 6th, 2007, 4:34am » |
Quote Modify
|
on Apr 5th, 2007, 7:27pm, Eigenray wrote:
I'm with you through here:
Quote:| Finally let a = A mod P, d = D mod P. |
|
I'm still not seeing how the specific a and d you give derive from A, D, and P. That is, what calculation are you performing to turn those sequences into 50+ digit numbers?
Edit: Nevermind, I see that the Chinese Remainder Theorem gives the desired results.
Edit 2: But then wouldn't
a = 9068282820450331974657080898673181357131499408941,
d = 4937322768572768736997221300181336960972337614549
where these are the numbers you gave above mod  Pi work just as well and be slightly smaller?
Edit 3: Or, if I could manage to calculate Pi correctly, I would see the given a, d were already as small as possible... 
--SMQ
|
| « Last Edit: Apr 6th, 2007, 7:28am by SMQ » |
IP Logged |
--SMQ
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Primes in Certain Sequences
« Reply #16 on: Apr 6th, 2007, 1:34pm » |
Quote Modify
|
on Apr 6th, 2007, 3:49am, Barukh wrote:| Sequence with the smallest numbers a, b known so far was found in 2004. It is generated by two numbers of 12 and 11 digits. It contains 17 sequences, largest prime 2521 and largest period 90. |
|
Googling for the words fibonacci covering system turns up this ["A New Fibonacci-like Sequence of Composite Numbers", M. Vsemirnov, Journal of Integer Sequences, Vol. 7 (2004)].
He uses the covering system:
R = {3, 5, 9, 17, 33, 1, 2, 14, 8, 80, 62, 4, 6, 12, 0, 18, 48}
M = {4, 8, 16, 24, 48, 3, 9, 18, 36, 90, 90, 5, 10, 15, 30, 20, 60}
P = {3, 7, 47, 23, 1103, 2, 17, 19, 107, 181, 541, 5, 11, 61, 31, 41, 2521}.
Now, the solutions to a*F(r-1) + b*F(r) = 0 mod p are given uniquely (mod p) by
a = c*(-1)r+1F(r) = c*F(m-r),
b = c*(-1)rF(r-1) = c*F(m-r+1),
for some non-zero c mod p. Graham's original solution used c=1 for each p. But Knuth ["A Fibonacci-like sequence of composite numbers", Math. Mag. 63 (1990) 21-25] describes how to choose theses values to minimize the final values of a,b. Basically, we have the system of equations:
b = dk a (mod pk); a != 0 mod pk, where dk is determined by
F(rk-1) + dkF(rk) = 0 mod pk,
except that if rk=mk, then we need a = 0 mod pk, b != 0 mod pk. Let
P = product {pk : rk != mk}, and
D = dk mod pk, whenever rk != mk.
Then D is uniquely determined mod P. Letting Q = product { pk : rk=mk }, we need to find a,b such that
b = Da mod P, gcd(a,P) = 1, and Q | a,
or, letting C = QD mod P, find n such that when
a = nQ; b = nC mod P,
max(a,b) is minimized. Of course we can't try every n, but by considering the continued fraction expansion of C/P (or equivalently the Euclidean algorithm applied to P and C), one can explicitly find the "record-breaking" smallest values of nC mod P; these values occur with n increasing exponentially, and nC mod P decreasing exponentially. Thus given a covering system, the smallest possible (a,b) can found quickly.
Knuth uses this argument to find a 17-digit pair; Wilf found a smaller 17-digit pair, Nicol found a 12 digit pair, and apparently Vsemirnov's is the smallest, with
a = 106276436867, b = 35256392432.
[And googling for these numbers turns up this.]
I must say, this is a very nice problem!
|
| « Last Edit: Apr 6th, 2007, 1:39pm by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print