wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Primes in Certain Sequences
        
(Message started by: Barukh on Apr 4th, 2007, 12:34am)
Title: Primes in Certain Sequences
Post by Barukh on Apr 4th, 2007, 12:34am
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 (http://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arithmetic_progressions), 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?

Title: Re: Primes in Certain Sequences
Post by towr on Apr 4th, 2007, 1:37am
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.
Title: Re: Primes in Certain Sequences
Post by Barukh on Apr 4th, 2007, 2:21am

on 04/04/07 at 01:37:06, 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.

;)
Title: Re: Primes in Certain Sequences
Post by Aryabhatta on Apr 4th, 2007, 1:44pm
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!)
Title: Re: Primes in Certain Sequences
Post by SMQ on Apr 4th, 2007, 2:42pm
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
Title: Re: Primes in Certain Sequences
Post by Eigenray on Apr 4th, 2007, 6:38pm
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.
Title: Re: Primes in Certain Sequences
Post by Eigenray on Apr 4th, 2007, 6:59pm
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]
Title: Re: Primes in Certain Sequences
Post by Eigenray on Apr 4th, 2007, 7:23pm

on 04/04/07 at 14:42:37, 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,
5225457348769522235516978527739366178918359667231666702522552511198292091915152870559330893647822149589200295218414893003855350084940563225378955816317228153248999868469747623428612217623045887645950421711012851790329954066498272455051
is apparently prime, as is the 4573rd  :-/
Title: Re: Primes in Certain Sequences
Post by Eigenray on Apr 4th, 2007, 7:52pm
I was being short-sighted: it suffices to find a [link=http://en.wikipedia.org/wiki/Covering_system]covering system[/link] 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

[link=http://www.research.att.com/~njas/sequences/A001602]{L(p)}[/link] = {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).
Title: Re: Primes in Certain Sequences
Post by SMQ on Apr 5th, 2007, 4:28am

on 04/04/07 at 19:23:30, 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
Title: Re: Primes in Certain Sequences
Post by SMQ on Apr 5th, 2007, 2:16pm

on 04/04/07 at 19:52:49, 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) }

:D

Edit: removed a few superfluous terms

--SMQ
Title: Re: Primes in Certain Sequences
Post by Aryabhatta on Apr 5th, 2007, 7:11pm
Wow. That was quick. I love this site.
Title: Re: Primes in Certain Sequences
Post by Eigenray on Apr 5th, 2007, 7:27pm

on 04/05/07 at 14:16:43, 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}

;D

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 [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1147119746]Garden of Eden[/link] primes.
Title: Re: Primes in Certain Sequences
Post by Barukh on Apr 6th, 2007, 3:49am
Excellent analysis, SMQ and Eigenray!  :D

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.
Title: Re: Primes in Certain Sequences
Post by SMQ on Apr 6th, 2007, 4:13am

on 04/05/07 at 19:27:09, 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 (http://home.att.net/~blair.kelly/mathematics/fibonacci/) 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
Title: Re: Primes in Certain Sequences
Post by SMQ on Apr 6th, 2007, 4:34am

on 04/05/07 at 19:27:09, Eigenray wrote:
In detail:

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 (http://en.wikipedia.org/wiki/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 http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif Pi work just as well and be slightly smaller?

Edit 3: Or, if I could manage to calculate http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif Pi correctly, I would see the given a, d were already as small as possible... :-[

--SMQ
Title: Re: Primes in Certain Sequences
Post by Eigenray on Apr 6th, 2007, 1:34pm

on 04/06/07 at 03:49:40, 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 [link=http://www.emis.de/journals/JIS/VOL7/Vsemirnov/vsem5.pdf]this[/link] ["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 [link=http://en.wikipedia.org/wiki/Primefree_sequence]this[/link].]

I must say, this is a very nice problem!


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board