Prime numbers and primality testing is a Restricted Group with 1137 members. Yahoo Groups Re: Prime chains x-->Ax+B djbroadhurst Message 1 of 143 , Nov 12 3:30 AM ----------------------- --- In primenumbers@yahoogroups.com, "WarrenS" wrote: > One might CONJECTURE that the necessary conditions of > the theorem also suffice. It would be better to make > such a conjecture after getting rather more > numerical evidence than this, though. I did a little more testing, which made your conjecture seem fairly plausible. Here I print output only when the best chain with starting prime < 10^6 has length less than 6 or more than 10: {isok(a,b)=local(f,t);if(b&&(a+b)%2&&gcd(a,b)==1,t=1; f=factor(a-1)[,1];for(k=1,#f,if(b%f[k],t=0;break())));t;} {chain(a,b)=local(c,m,q,r,s);forprime(p=2,pmax,q=p;c=0; while(isprime(q),c++;if(c>m,m=c;r=p);s=a*q+b; if(s-q,q=s,break())));[r,m];} {pmax=10^6;for(a=2,20,for(b=-20,20,if(isok(a,b),t=chain(a,b); if(t[2]<6||t[2]>10,print([a*x+b,t])))));} [3*x - 2, [61, 5]] [3*x + 16, [587, 11]] [4*x - 9, [13729, 13]] [17*x - 18, [31223, 5]] [17*x - 8, [109073, 5]] [17*x - 4, [53629, 5]] [17*x + 2, [314953, 5]] [17*x + 6, [6689, 5]] [17*x + 18, [7907, 5]] Then I took a deeper look at 3*x-2: pmax=10^7;print([3*x-2,chain(3,-2)]); [3*x - 2, [1197631, 7]] I imagine that Jens, or Jarek, could quickly find a chain significantly longer than [4*x - 9, [13729, 13]] David djbroadhurst Nov 12 3:30 AM ----------------------- --- In primenumbers@yahoogroups.com, "WarrenS" wrote: > One might CONJECTURE that the necessary conditions of > the theorem also suffice. It would be better to make > such a conjecture after getting rather more > numerical evidence than this, though. I did a little more testing, which made your conjecture seem fairly plausible. Here I print output only when the best chain with starting prime < 10^6 has length less than 6 or more than 10: {isok(a,b)=local(f,t);if(b&&(a+b)%2&&gcd(a,b)==1,t=1; f=factor(a-1)[,1];for(k=1,#f,if(b%f[k],t=0;break())));t;} {chain(a,b)=local(c,m,q,r,s);forprime(p=2,pmax,q=p;c=0; while(isprime(q),c++;if(c>m,m=c;r=p);s=a*q+b; if(s-q,q=s,break())));[r,m];} {pmax=10^6;for(a=2,20,for(b=-20,20,if(isok(a,b),t=chain(a,b); if(t[2]<6||t[2]>10,print([a*x+b,t])))));} [3*x - 2, [61, 5]] [3*x + 16, [587, 11]] [4*x - 9, [13729, 13]] [17*x - 18, [31223, 5]] [17*x - 8, [109073, 5]] [17*x - 4, [53629, 5]] [17*x + 2, [314953, 5]] [17*x + 6, [6689, 5]] [17*x + 18, [7907, 5]] Then I took a deeper look at 3*x-2: pmax=10^7;print([3*x-2,chain(3,-2)]); [3*x - 2, [1197631, 7]] I imagine that Jens, or Jarek, could quickly find a chain significantly longer than [4*x - 9, [13729, 13]] David djbroadhurst Nov 12 4:19 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > I imagine that Jens, or Jarek, could quickly find > a chain significantly longer than > [4*x - 9, [13729, 13]] I should have added: for x ==> a*x+b with a > 2. We know of Cunningham chains with lengths up to 17: http://users.cybercity.dk/~dsl522332/math/Cunningham_Chain_records.htm David Jens Kruse Andersen Nov 12 6:39 AM ----------------------- Henri Lifchitz has a page about Generalized Cunningham chains: http://www.primenumbers.net/Henri/us/CunnGenus.htm There are old results for a + b = 1. In http://tech.groups.yahoo.com/group/primenumbers/message/21480 I wrote: > If we are allowed to choose between ax + b and ax - b at each step > then Chuck Seggelin calls it a prime tree at > http://unbecominglevity.blogharbor.com/blog/_archives/2004/3/17/27759.html > > With my program he found one of depth 26: > http://unbecominglevity.blogharbor.com/blog/_archives/2006/5/12/1952529.html > > It is 2n +/- 308843535 starting at 177857809. As a prime curio: > http://primes.utm.edu/curios/page.php/177857809.html -- Jens Kruse Andersen mikeoakes2 Nov 13 1:06 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > I imagine that Jens, or Jarek, could quickly find > a chain significantly longer than > [4*x - 9, [13729, 13]] Here are a couple of 14's, using your script over a different range:- [3*x - 992222, [653801, 14]] [3*x - 983780, [775189, 14]] As of course you know, that search algorithm is very inefficient, and what's needed is a multiple Eratosthenes-type sieve, which I imagine from their record achievements that Jens and Jarek each have a whole armoury of. Mike djbroadhurst Nov 13 5:33 AM ----------------------- --- In primenumbers@yahoogroups.com, "WarrenS" wrote: > if gcd(B,A-1)=1 then the linear congruential sequence generator > x-->Ax+B (mod M) will be full period M for any prime M dividing A-1 > hence the chain length cannot be longer than M primes in a row The conclusion is not correct. Consider the map x ==> 4*x - 5. In this case B = -5 is coprime to the prime M = 3, which divides A - 1 = 3. Thus Warren claims that the chain length cannot be longer than 3 primes in a row. Counterexample: The chain of primes 2, 3, 7, 23 satisfies the recursion x ==> 4*x - 5. David Jens Kruse Andersen Nov 13 9:07 AM ----------------------- David wrote: > I imagine that Jens, or Jarek, could quickly find > a chain significantly longer than > [4*x - 9, [13729, 13]] My efficient programs would require modifications to handle a > 2. Here are some 16's from an inefficient C program: [4*x + 2252715, [1750061, 16]] [4*x + 1339065, [1813219, 16]] [4*x + 2057595, [2019191, 16]] [4*x + 9449115, [2610821, 16]] -- Jens Kruse Andersen Jens Kruse Andersen Nov 13 11:33 AM ----------------------- [4*x + 14882835, [4447297, 17]] -- Jens Kruse Andersen djbroadhurst Nov 13 6:29 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > hence the chain length cannot be longer than M primes > Counterexample: The chain of primes 2, 3, 7, 23 > satisfies the recursion x ==> 4*x - 5. Off list, Warren wrote to me saying: > In computer programming this is called a "boundary case bug." > I actually knew this when I wrote the theorem+proof > but I was too lazy/lame to state+do it fully right. In mathematics, this is called an "error in reasoning". The error is easily repaired: for "cannot be longer than M primes", read "cannot be longer than 2*M-1 primes". Proof: An integer sequence generated by the map x ==> A*x + B, with A = 1 mod M, and B coprime to the prime M, will contain at least two multiples of M if the length of the sequence exceeds 2*M-1. No more than one of these multiples may be prime. PS: Congratulations to Jens for the 17 primes > [4*x + 14882835, [4447297, 17]] namely p(n) = 9408242*4^n - 4960945, for n = 0 ... 16. David mikeoakes2 Nov 14 1:38 AM ----------------------- Half-way results with David's code for a=3, abs(b)<=10^6 and pmax=10^6: no 15's yet but Poisson feeling generous: [3*x - 201950, [483407, 16]] Mike WarrenS Nov 14 5:03 PM ----------------------- THEOREM (Warren D. Smith): the only possible unboundedly long x-->Ax+B prime chains (A>=2) must have B a multiple of every prime divisor of A-1, and B nonzero, and gcd(A,|B|)=1, and the parities of A,B must differ. REMARK: "B a multiple of every prime divisor of A-1" can be replaced by "B a multiple of the squarefree part of A-1." CONJECTURE: the necessary conditions of the theorem also suffice. I wrote a hack to check my theorem. It sought but failed to find any counterexamples (or even plausible candidates) i.e. failed to find any long chains when the theorem said they were impossible. That's nice. (Since being insane is bad.) In the other direction, it sometimes found long chains when the conjecture said they should exist. However, it failed to find impressively long chains in many cases: for each A=7,...,20, it failed to find a long-enough chain when B=A-1 and B=1-A. For example 7x-6: 11681(6) meaning 6 primes starting with 11681 was the longest chain it found 7x+6: 4259(6) 8x-7: 11551(7) 8x+7: 25589(6) 9x-8: 13249(6) 9x+8: 4099(7) 10x-9: 29(6) 10x+9: 13(6) 11x-10: 6553(6) 11x+10: 14891(6) Also failed to find impressively long chains in these cases: 6x-5: 1601(6) 7x-18: 1693(6) 7x-12: 9227(7) 7x+12: 9043(6) 7x+18: 9257(6) 9x-16: 2377(6) 9x+16: 55837(6) 11x-20: 10859(6) 11x+20: 17749(6) Broadhurst complained about 3x-8: 217739(6) which he finds not impressively long enough either. So: Can anybody find longer 3x-8 or 6x-5 chains? Or prove they must have bounded length? I don't think there is enough evidence for the conjecture yet. People have found some very long chains by using rather ridiculously large cherrypicked B. Fun, but maybe not very testing of the conjecture. Here are some chains with 8 to 11 primes: 2x-19: 759559(8) 2x-15: 301789(8) 2x-5: 11(8) 2x-3: 1823(8) 2x+3: 477727(8) 2x+9: 413411(8) 2x+11: 810379(8) 3x-14: 373657(8) 3x-10: 23539(8) 4x-15: 287579(8) 4x-9: 37(8) 4x-3: 408539(8) 4x+3: 17231(8) 4x+9: 93811(8) 4x+15: 271211(8) 2x-13: 285283(9) 2x-11: 41(9) 2x+13: 3467(9) 2x+15: 4759(9) 3x-4: 1087(9) 4x+3: 32611(9) 5x+12: 4099(9) 2x+15: 75731(10) 3x+8: 342821(10) 4x-9: 13729(10) 3x+16: 587(11) djbroadhurst Nov 14 6:05 PM ----------------------- --- In primenumbers@yahoogroups.com, "WarrenS" wrote: > Can anybody find longer 3x-8 or 6x-5 chains? [3*x - 8, [2023529, 8]] [6*x - 5, [95807339, 9]] Puzzle: In a bounded case (see Warren's theorem) find a chain longer than these: [12*x + 17, [7468693, 9]] [14*x - 17, [2276201, 9]] [20*x - 17, [2219681, 9]] David djbroadhurst Nov 15 10:47 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Puzzle: In a bounded case (see Warren's theorem) > find a chain longer than these: > > [12*x + 17, [7468693, 9]] > [14*x - 17, [2276201, 9]] > [20*x - 17, [2219681, 9]] Hint: There are at least 4 solutions to this puzzle with 99 > A > |B|, so no criticism of "big-B cherry-picking" is merited, in these case. David djbroadhurst Nov 16 5:21 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Puzzle: In a bounded case (see Warren's theorem) > find a chain longer than these: > [12*x + 17, [7468693, 9]] > [14*x - 17, [2276201, 9]] > [20*x - 17, [2219681, 9]] Kevin Acres sent me this correct solution: [14*x - 9, [12953407, 10]] Starting with a prime > 13 the length of chain cannot exceed 12, so Kevin's score was 10/12. Here are 4 more solutions with a chain of length 10, in a bounded case: [44*x - 17, [79833209, 10]] [48*x - 35, [39431881, 10]] [60*x + 19, [61519747, 10]] [72*x - 35, [57180493, 10]] Note that in the last case, if we start with a prime > 71 the length of the chain cannot exceed 70. Here we see that Warren's distinction between bounded and unbounded has become somewhat vacuous, since he is telling us not to look at this case if we are seeking a chain of length 71. But that extreme length is far longer than the record for a chain of any kind, namely a length of 17, found in a Cunningham case, by Jarek, and in a non-Cunningham case, by Jens. Conclusions: Warren's theorem was good; its practical import is limited. David djbroadhurst Nov 17 6:55 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Kevin's score was 10/12. Let A, B and L be integers with A > 1 and L > 1. Definition: A "Smith chain" of length L is a chain p[n+1] = A*p[n] + B, such that p[n] is prime, for n = 1 to L, with p[2] > p[1] > A. Example [Jens Kruse Andersen]: With A = 4, B = 14882835, and p[1] = 4447297, we obtain a Smith chain of length L = 17. Definition: A "maximal Smith chain" is a Smith chain with integers (A,B) for which there is a proof that no chain of greater length exists. Example: [Warren Smith]: With A = 8, B = -9, and p[1] = 9497, we obtain a Smith chain of length L = 6. This is a maximal Smith chain, since the iteration p[n+1] = 8*p[n] - 9, with p[2] > p[1] > 8, ensures that one of the integers p[n], for n = 1 to 7, is a composite number divisible by 7. Puzzle 2: Find a maximal Smith chain of length L > 6. Hint: Make A-1 divisible by a prime that is coprime to B. David Broadhurst, 17 November 2010 djbroadhurst Nov 17 5:22 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Definition: A "Smith chain" of length L is a chain > p[n+1] = A*p[n] + B, such that p[n] is prime, > for n = 1 to L, with p[2] > p[1] > A. > Definition: A "maximal Smith chain" is a Smith chain with > integers (A,B) for which there is a proof that no chain > of greater length exists. > Puzzle 2: Find a maximal Smith chain of length L > 6. Kevin has sent me correct solutions with a score of 10/10 . I had a couple of others. But can anyone make it to 12/12 ? David Kevin Acres Nov 17 6:10 PM ----------------------- At 12:22 PM 18/11/2010, djbroadhurst wrote: > > Definition: A "Smith chain" of length L is a chain > > p[n+1] = A*p[n] + B, such that p[n] is prime, > > for n = 1 to L, with p[2] > p[1] > A. > > > Definition: A "maximal Smith chain" is a Smith chain with > > integers (A,B) for which there is a proof that no chain > > of greater length exists. > > > Puzzle 2: Find a maximal Smith chain of length L > 6. > >Kevin has sent me correct solutions with a score of 10/10 . >I had a couple of others. But can anyone make it to 12/12 ? > I'm submitting my only 12/12 as yet: [14*x - 2907, [15145447, 12]] Kevin. Kevin Acres Nov 18 1:31 AM ----------------------- At 01:10 PM 18/11/2010, Kevin Acres wrote: >At 12:22 PM 18/11/2010, djbroadhurst wrote: > > > Definition: A "Smith chain" of length L is a chain > > > p[n+1] = A*p[n] + B, such that p[n] is prime, > > > for n = 1 to L, with p[2] > p[1] > A. > > > > > Definition: A "maximal Smith chain" is a Smith chain with > > > integers (A,B) for which there is a proof that no chain > > > of greater length exists. > > > > > Puzzle 2: Find a maximal Smith chain of length L > 6. > > > >Kevin has sent me correct solutions with a score of 10/10 . > >I had a couple of others. But can anyone make it to 12/12 ? > > > >I'm submitting my only 12/12 as yet: > >[14*x - 2907, [15145447, 12]] I now have a second 12/12: [14*x + 15035, [70247743, 12]] I used a "speed up" in my script which was implemented by testing for the condition: x - b = 0 mod a-1 I'm not sure, however, if this is a necessary condition to obtain the 12/12. Maybe someone can enlighten me on this. Regards, Kevin. Phil Carmody Nov 18 3:09 AM ----------------------- Late to the party again... Show message history djbroadhurst Nov 18 9:39 AM ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > Late to the party again... "Pauca sed matura" [Gauss] > [14*x-139, [28405148634529, 12]] > [14*x-139, [121720727206459, 12]] > [14*x-139, [213651970745893, 12]] > [14*x+139, [240738291413, 12]] (alas no bonus points for term 14) > [14*x+139, [38492830711487, 12]] > [14*x+139, [41837744593823, 12]] Your ability to sieve starting primes much larger than those tested by Kevin and me is almost certainly the key. My code was awful; Kevin's only incrementally better; yours probably nodding at respectability. > Going to L=16 would require heavy processing (at least a week) Well it's only for fun. But I sure would "Wow^137" if/when someone scores the perfect hex of 16/16 in a bounded case, when Warren D Smith is telling us not even to look at such cases, yet the combined power of Jarek and Jens cannot yet score more than 17/infinity, in easy unbounded cases. Take your time, Phil: it ain't urgent. Glad to see you back, with such neat primes already in your pocket. Yrs for aye, David Kevin Acres Nov 18 11:55 AM ----------------------- Just pulling the plug on the 12's. >--- In primenumbers@yahoogroups.com, >Phil Carmody wrote: > > > Late to the party again... > >"Pauca sed matura" [Gauss] > > > [14*x-139, [28405148634529, 12]] > > [14*x-139, [121720727206459, 12]] > > [14*x-139, [213651970745893, 12]] > > [14*x+139, [240738291413, 12]] (alas no bonus points for term 14) > > [14*x+139, [38492830711487, 12]] > > [14*x+139, [41837744593823, 12]] > >Your ability to sieve starting primes much >larger than those tested by Kevin and me >is almost certainly the key. > >My code was awful; Kevin's only incrementally better; >yours probably nodding at respectability. > > > Going to L=16 would require heavy processing (at least a week) My last two are: [14*x + 23069, [82443667, 12]] [14*x - 23103, [10460903, 12]] Just for statistics sake, my 4 12/12 results where found in amongst a total of: 1671 9/12 183 10/12 19 11/12 4 12/12 Bearing in mind that I had two processes running and that the second 12/12 in each in the endpoint of the search. Now maybe I'll start looking at the 16/16. Kevin. Phil Carmody Nov 18 3:41 PM ----------------------- --- On Thu, 11/18/10, djbroadhurst wrote: > --- In primenumbers@yahoogroups.com, > Phil Carmody wrote: > > > Late to the party again... > > "Pauca sed matura" [Gauss] > > > [14*x-139, [28405148634529, 12]] > > [14*x-139, [121720727206459, 12]] > > [14*x-139, [213651970745893, 12]] > > [14*x+139, [240738291413, 12]] (alas no bonus points > for term 14) > > [14*x+139, [38492830711487, 12]] > > [14*x+139, [41837744593823, 12]] > > Your ability to sieve starting primes much > larger than those tested by Kevin and me > is almost certainly the key. > > My code was awful; Kevin's only incrementally better; > yours probably nodding at respectability. > > > Going to L=16 would require heavy processing (at least a week) Gross underestimate - I've just seen the size of the numbers. I think it's a quantity better measured in years on my hardware. > Well it's only for fun. But I sure would "Wow^137" if/when > someone scores the perfect hex of 16/16 in a bounded case, > when Warren D Smith is telling us not even to look at such > cases, yet the combined power of Jarek and Jens cannot > yet score more than 17/infinity, in easy unbounded cases. 16/16 is exactly as hard as 16/infinity. 17/anything has always been the exclusive domain of the guys with access to 100s of GHz. (Waldvogel used ~200 machines IIRC.) > Take your time, Phil: it ain't urgent. Glad to see you > back, with such neat primes already in your pocket. I've been meaning to rewrite gensv from scratch for about 5 years. Maybe in 5 years I'll have done that, and maybe then I'll try some big tasks with it. Until then, I'm just dabbling. Phil djbroadhurst Nov 18 9:55 PM ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > 17/anything has always been the exclusive domain of > the guys with access to 100s of GHz. That is not clear to me. Please see the progression by Jens from http://tech.groups.yahoo.com/group/primenumbers/message/22048 [4*x + 2252715, [1750061, 16]] [4*x + 1339065, [1813219, 16]] [4*x + 2057595, [2019191, 16]] [4*x + 9449115, [2610821, 16]] to http://tech.groups.yahoo.com/group/primenumbers/message/22049 [4*x + 14882835, [4447297, 17]] in one day, using (I imagine) considerably less than 100 GHz of processing power. Perhaps Jens might like to comment on Phil's overestimate of the burden of 17/infinity? David mikeoakes2 Nov 19 8:18 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > {isok(a,b)=local(f,t);if(b&&(a+b)%2&&gcd(a,b)==1,t=1; > f=factor(a-1)[,1];for(k=1,#f,if(b%f[k],t=0;break())));t;} > > {chain(a,b)=local(c,m,q,r,s);forprime(p=2,pmax,q=p;c=0; > while(isprime(q),c++;if(c>m,m=c;r=p);s=a*q+b; > if(s-q,q=s,break())));[r,m];} > > {pmax=10^6;for(a=2,20,for(b=-20,20,if(isok(a,b),t=chain(a,b); > if(t[2]<6||t[2]>10,print([a*x+b,t])))));} > > Then I took a deeper look at 3*x-2: > > pmax=10^7;print([3*x-2,chain(3,-2)]); > [3*x - 2, [1197631, 7]] I have taken a deeper look at a=2, pmax=10^6, and various ranges [-b_max,b_max] for b. c[L] is the count of chains of length L for that range of b's. For every b there is a chain of length at least 4. The first table corresponds to the 2 kinds of Cunningham chain. b_max=1 c[4]=0 c[5]=0 c[6]=1 c[7]=1 c[8]=0 c[9]=0 c[10]=0 c[11]=0 c[12]=0 c[13]=0 c[14]=0 c[15]=0 b_max=10 c[4]=0 c[5]=0 c[6]=1 c[7]=5 c[8]=4 c[9]=0 c[10]=0 c[11]=0 c[12]=0 c[13]=0 c[14]=0 c[15]=0 b_max=10^2 c[4]=0 c[5]=0 c[6]=6 c[7]=39 c[8]=37 c[9]=15 c[10]=3 c[11]=0 c[12]=0 c[13]=0 c[14]=0 c[15]=0 b_max=10^3 c[4]=0 c[5]=0 c[6]=78 c[7]=432 c[8]=341 c[9]=130 c[10]=15 c[11]=4 c[12]=0 c[13]=0 c[14]=0 c[15]=0 b_max=10^4 c[4]=0 c[5]=4 c[6]=782 c[7]=4348 c[8]=3452 c[9]=1188 c[10]=166 c[11]=54 c[12]=6 c[13]=0 c[14]=0 c[15]=0 b_max=10^5 c[4]=0 c[5]=25 c[6]=9867 c[7]=44723 c[8]=32734 c[9]=10603 c[10]=1595 c[11]=372 c[12]=63 c[13]=15 c[14]=3 c[15]=0 b_max=10^6 c[4]=384 c[5]=22842 c[6]=202726 c[7]=444335 c[8]=248092 c[9]=69116 c[10]=9942 c[11]=2114 c[12]=340 c[13]=84 c[14]=18 c[15]=7 Each increas of 10 in b_max gives about 10 tims the counts, which is pretty much to be expected. These (especially the last) look like Poisson distributions; can anyone elaborate on that? Mike mikeoakes2 Nov 19 10:53 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > Phil Carmody wrote: > > > 17/anything has always been the exclusive domain of > > the guys with access to 100s of GHz. > > That is not clear to me. > > Please see the progression by Jens from > > http://tech.groups.yahoo.com/group/primenumbers/message/22048 > [4*x + 2252715, [1750061, 16]] > [4*x + 1339065, [1813219, 16]] > [4*x + 2057595, [2019191, 16]] > [4*x + 9449115, [2610821, 16]] > > to > > http://tech.groups.yahoo.com/group/primenumbers/message/22049 > [4*x + 14882835, [4447297, 17]] > > in one day, using (I imagine) considerably less > than 100 GHz of processing power. You are asking for a "bounded" solution with L=17. So the sequences with smallest a that qualify are:- a=18, p=17; or (probably easiest) a=20, any p; or a=24, any p; else a>=30. I am with Phil on this: it's very much harder than the unbounded case. Mike djbroadhurst Nov 19 11:47 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > > 17/anything has always been the exclusive domain of > > > the guys with access to 100s of GHz. > > That is not clear to me. > > You are asking for a "bounded" solution with L=17. No, Mike. I was challenging (with justice, perhaps) Phil's (seemingly) dubious claim that 17/anything requires 100s of GHz. If anything includes infinity then Jens may well have exposed the dubiety of Phil's hasty assertion. Please recall that this began by my saying: http://tech.groups.yahoo.com/group/primenumbers/message/22105 > Well it's only for fun. But I sure would "Wow^137" if/when > someone scores the perfect hex of 16/16 in a bounded case, > when Warren D Smith is telling us not even to look at such > cases, yet the combined power of Jarek and Jens cannot > yet score more than 17/infinity, in easy unbounded cases. Then Phil said: http://tech.groups.yahoo.com/group/primenumbers/message/22108 > 16/16 is exactly as hard as 16/infinity. > 17/anything has always been the exclusive domain of the > guys with access to 100s of GHz. So then I said (with justice, I hope): http://tech.groups.yahoo.com/group/primenumbers/message/22109 > Please see the progression by Jens from > [4*x + 9449115, [2610821, 16]] > to > [4*x + 14882835, [4447297, 17]] > in one day, using (I imagine) considerably less > than 100 GHz of processing power. But until we hear from Jens I may not insist that Phil was wrong. Perhaps Phil was right and Jens did use 100s of GHz ? Or perhaps Phil intended something different from what I read ? Best regards, to all contributors, David Jens Kruse Andersen Nov 19 11:47 AM ----------------------- David wrote: > Phil Carmody wrote: > >> 17/anything has always been the exclusive domain of >> the guys with access to 100s of GHz. > > That is not clear to me. > > Please see the progression by Jens from > > http://tech.groups.yahoo.com/group/primenumbers/message/22048 > [4*x + 2252715, [1750061, 16]] > [4*x + 1339065, [1813219, 16]] > [4*x + 2057595, [2019191, 16]] > [4*x + 9449115, [2610821, 16]] > > to > > http://tech.groups.yahoo.com/group/primenumbers/message/22049 > [4*x + 14882835, [4447297, 17]] > > in one day, using (I imagine) considerably less > than 100 GHz of processing power. > > Perhaps Jens might like to comment on Phil's > overestimate of the burden of 17/infinity? It depends on the form and size - and the expected size of the smallest solution depends on the form. It only took a few hours at 2.4 GHz and limited efficiency to find [4*x + 14882835, [4447297, 17]] and another case I didn't report: [4*x + 7792485, [5336489, 17]] Phil was probably thinking of problems similar to my simultaneous primes page. If both a and b are fixed in advance in a prime chain search for an arbitrary starting prime p then it becomes similar. My prime chains with arbitrary b wouldn't be allowed at my page. The required minimum value of a for bounded cases of 17 mean that the primes in the smallest solutions will be much larger than in the unbounded cases where small a is possible. Finding solutions looks too hard for me. The main reasons I could so easily find 17's are: 1) The primes in a chain grow relatively slowly with a = 4. 2) The form allows one to try billions of small (b, p) combinations. A few of these combinations are likely to give 17-hits with small primes. A bounded form with a >= 18 doesn't have advantage 1). Jarek's impressive CC17's didn't have advantage 2) because a CC fixes b = +/-1 -- Jens Kruse Andersen djbroadhurst Nov 19 12:03 PM ----------------------- --- In primenumbers@yahoogroups.com, "Jens Kruse Andersen" wrote: > It only took a few hours at 2.4 GHz and limited efficiency to find > [4*x + 14882835, [4447297, 17]] > and another case I didn't report: > [4*x + 7792485, [5336489, 17]] Thanks for confirming my assumption, Jens. > The main reasons I could so easily find 17's are: > 1) The primes in a chain grow relatively slowly with a = 4. > 2) The form allows one to try billions of small (b, p) combinations. As so often, you have put your finger on the nub of the "unbounded" case. When Phil's "anything" includes "infinity", as he seemed so clearly to imply, then 17 is easy, for smart folk with few cycles, like Jens. But how about 16/16, which was what I was encouraging? Here we lose Jens's point (1), since a = 17 is the smallest bounded possibility. But we still have Jens's point (2), which Kevin is currently exploiting, but without Phil's smart "gensv" sieve, I imagine. Might some of you talented folks please get together and attempt the "full hex" of 16/16; I ain't smart enough. David (a mere editor, in this case) mikeoakes2 Nov 19 12:12 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > You are asking for a "bounded" solution with L=17. > > No, Mike. I was challenging (with justice, perhaps) Phil's > (seemingly) dubious claim that 17/anything requires > 100s of GHz. If anything includes infinity then Jens may well > have exposed the dubiety of Phil's hasty assertion. > > Please recall that this began by my saying: > http://tech.groups.yahoo.com/group/primenumbers/message/22105 > > Well it's only for fun. But I sure would "Wow^137" if/when > > someone scores the perfect hex of 16/16 in a bounded case, > > when Warren D Smith is telling us not even to look at such > > cases, yet the combined power of Jarek and Jens cannot > > yet score more than 17/infinity, in easy unbounded cases. > > Then Phil said: > http://tech.groups.yahoo.com/group/primenumbers/message/22108 > > 16/16 is exactly as hard as 16/infinity. > > 17/anything has always been the exclusive domain of the > > guys with access to 100s of GHz. > > So then I said (with justice, I hope): > http://tech.groups.yahoo.com/group/primenumbers/message/22109 > > Please see the progression by Jens from > > [4*x + 9449115, [2610821, 16]] > > to > > [4*x + 14882835, [4447297, 17]] > > in one day, using (I imagine) considerably less > > than 100 GHz of processing power. Thanks for that recap, David. (It's been a fruitful thread, and shows no sign of withering:-) Your puzzle 2, which is the header of this subthread, was about _bounded_ soluitons only. I'm still not entirely clear whether you and/or Phil were restricting your remarks to this bounded case or not. Further, I think it would help us all to keep up if you were to gloss your notation "L1/L2", used above and passim. In particular, I offer you [12*x + 143588905, [11, 11]] Is this a more-than-perfect (pluperfect?) 11/10, or what? Mike djbroadhurst Nov 19 12:14 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > But how about 16/16, which was what I was encouraging? > Here we lose Jens's point (1), since a = 17 is the smallest > bounded possibility. But we still have Jens's point (2), > which Kevin is currently exploiting, but without Phil's > smart "gensv" sieve, I imagine. Sorry: for "a = 17", read "a = 18", precisely as Jens had indicated. David (not even a decent editor) djbroadhurst Nov 19 12:31 PM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > [12*x + 143588905, [11, 11]] > Is this a more-than-perfect (pluperfect?) 11/10, or what? Please read the rules for the bounded case: http://tech.groups.yahoo.com/group/primenumbers/message/22087 > Let A, B and L be integers with A > 1 and L > 1. > > Definition: A "Smith chain" of length L is a chain > p[n+1] = A*p[n] + B, such that p[n] is prime, > for n = 1 to L, with p[2] > p[1] > A. > Definition: A "maximal Smith chain" is a Smith chain with > integers (A,B) for which there is a proof that no chain > of greater length exists. Can you see where you broke my careful rubric? p=11;for(k=1,12,print(factor(p));p=12*p + 143588905) Mat([11, 1]) Mat([143589037, 1]) Mat([1866657349, 1]) Mat([22543477093, 1]) Mat([270665314021, 1]) Mat([3248127357157, 1]) Mat([38977671874789, 1]) Mat([467732206086373, 1]) Mat([5612786616625381, 1]) Mat([67353439543093477, 1]) Mat([808241274660710629, 1]) [11, 1; 111301, 1; 7921921224323, 1] But the first prime, 11, is less than A = 12. You have a "maximal Smith chain", as precisely defined above, with 10/10, not so? David Kevin Acres Nov 19 12:44 PM ----------------------- Hi David, At 07:03 AM 20/11/2010, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >"Jens Kruse Andersen" wrote: > > > It only took a few hours at 2.4 GHz and limited efficiency to find > > [4*x + 14882835, [4447297, 17]] > > and another case I didn't report: > > [4*x + 7792485, [5336489, 17]] > >Thanks for confirming my assumption, Jens. > > > The main reasons I could so easily find 17's are: > > 1) The primes in a chain grow relatively slowly with a = 4. > > 2) The form allows one to try billions of small (b, p) combinations. > >As so often, you have put your finger on the nub of the >"unbounded" case. When Phil's "anything" includes "infinity", >as he seemed so clearly to imply, then 17 is easy, >for smart folk with few cycles, like Jens. > >But how about 16/16, which was what I was encouraging? > >Here we lose Jens's point (1), since a = 17 is the smallest >bounded possibility. But we still have Jens's point (2), >which Kevin is currently exploiting, but without Phil's >smart "gensv" sieve, I imagine. > >Might some of you talented folks please get together >and attempt the "full hex" of 16/16; I ain't smart enough. > >David (a mere editor, in this case) I had a preliminary run for 17s. In my 699 instances, where the chain length was >=9, there were 640 chains of 9, 52 chains of 10 and 7 chains of 11. I have still to find a chain longer than 11. Regards, Kevin. mikeoakes2 Nov 19 12:53 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > [12*x + 143588905, [11, 11]] > > Is this a more-than-perfect (pluperfect?) 11/10, or what? > > Please read the rules for the bounded case: > http://tech.groups.yahoo.com/group/primenumbers/message/22087 > > > Let A, B and L be integers with A > 1 and L > 1. > > > > Definition: A "Smith chain" of length L is a chain > > p[n+1] = A*p[n] + B, such that p[n] is prime, > > for n = 1 to L, with p[2] > p[1] > A. > > > Definition: A "maximal Smith chain" is a Smith chain with > > integers (A,B) for which there is a proof that no chain > > of greater length exists. > > Can you see where you broke my careful rubric? Obviously, you can make whatever rules you like. But I think your Definition is not the natural one for this problem. At the very least, it should say p[1] >= A. Why disallow for example [7*x + 4, [7,2]] ? After spending a lot of today analysing _carefully_(!) all cases A <= 20, and their associated max poss. L for the bounded case, I put it to you that the correct restriction is:- p[1] >= A-1. Do you not agree? Mike djbroadhurst Nov 19 1:22 PM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > I put it to you that the correct restriction is:- > p[1] >= A-1. > > Do you not agree? Humpty Dumpty emphatically disagrees, since then the challenge would be far harder. Your pluperfect 17/16 would have have to begin with 17. Humpty's perfect 16/16 may begin with any prime greater than 17, thus affording Jens and Kevin the full (b,p) space. http://www.sabian.org/Alice/lgchap06.htm `When I use a word,' Humpty Dumpty said, in rather a scornful tone, `it means just what I choose it to mean -- neither more nor less.' I don't mean to be scornful. But I do think that I was wise to disallow p[1] = A - 1, so as to set a much fairer puzzle than you might have done by allowing it. Yours arbitrarily, David mikeoakes2 Nov 19 2:12 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > I don't mean to be scornful. But I do think > that I was wise to disallow p[1] = A - 1, > so as to set a much fairer puzzle than you might > have done by allowing it. 1) I agree it is a special case. There's a closely analogous AP-k case - see my 2001 NMBRTHRY post http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0106&L=NMBRTHRY&P=R357 Perhaps we should have Puzzle 3, with p[1]=A-1? I have solved it for A<=12. For A=14 I've so far only found [14*x + 2693409, [13,10]] Can anyone improve on that? 2) You haven't addressed my grizzle about your ruling out p[1] = A. Mike djbroadhurst Nov 19 3:34 PM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > that I was wise to disallow p[1] = A - 1 > I agree it is a special case. Thanks. > You haven't addressed my grizzle about your ruling > out p[1] = A. For Puzzle 2, it was irrelevant whether I wrote p[2] > p[1] > A or p[2] > p[1] >= A so I saved myself the ugly-looking redundant keystroke. David djbroadhurst Nov 19 4:20 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > For Puzzle 2, it was irrelevant whether I wrote > p[2] > p[1] > A > or > p[2] > p[1] >= A > so I saved myself the ugly-looking redundant keystroke. I was, of course, assuming that a solver would choose A = 12, for 10/10, as did Kevin, and then maybe later A = 14, for 12/12, as did Kevin and Phil. Mike, after both happy events, may like to solve the much harder Puzzle 4, with A = p[1] = 23 for 10/10, and then maybe later Puzzle 5, with A = p[1] = 53 for 12/12 but I was trying to set less fearful puzzles than these post-hoc inventions. David mikeoakes2 Nov 20 4:35 AM ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > > I had a preliminary run for 17s. > > In my 699 instances, where the chain length was >=9, there were 640 > chains of 9, 52 chains of 10 and 7 chains of 11. I have still to > find a chain longer than 11. Presumably by "17s" you mean A=20 with max L=18? (David doesn't let us look at a maximal L=17:-) A=18 gives max L=16. Here is (I think) the longest bounded chain posted so far:- [18*x + 214555, [86677, 13]] Mike mikeoakes2 Nov 20 10:09 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > For Puzzle 2, it was irrelevant whether I wrote > > p[2] > p[1] > A > > or > > p[2] > p[1] >= A > > so I saved myself the ugly-looking redundant keystroke. > > I was, of course, assuming that a solver would choose > A = 12, for 10/10, as did Kevin, and then maybe later > A = 14, for 12/12, as did Kevin and Phil. .. and Mike. Here is my A = 14 contribution:- [14*x + 2692854861, [13, 12]] but of course Sir won't let me claim it as a 12/12 :-( (I still think the Puzzle 2 restrictions on p[1] vs. A are not properly thought through, but agree to a cease-fire on that one.) Mike djbroadhurst Nov 20 11:47 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > [14*x + 2692854861, [13, 12]] > but of course Sir won't let me claim it as a 12/12 :-( Indeed not, hard-hearted person that I am: p=13;for(k=1,12,p=14*p+2692854861;print(factor(p))); Mat([2692855043, 1]) Mat([40392825463, 1]) Mat([568192411343, 1]) Mat([7957386613663, 1]) Mat([111406105446143, 1]) Mat([1559688169100863, 1]) Mat([21835637060266943, 1]) Mat([305698921536592063, 1]) Mat([4279784904205143743, 1]) Mat([59916988661564867263, 1]) Mat([838837841264600996543, 1]) [107, 1; 999236351, 1; 109838361859, 1] 11/12: could do better :-) David mikeoakes2 Nov 20 12:07 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > [14*x + 2692854861, [13, 12]] > > but of course Sir won't let me claim it as a 12/12 :-( > > Indeed not, hard-hearted person that I am: > > p=13;for(k=1,12,p=14*p+2692854861;print(factor(p))); > Mat([2692855043, 1]) > Mat([40392825463, 1]) > Mat([568192411343, 1]) > Mat([7957386613663, 1]) > Mat([111406105446143, 1]) > Mat([1559688169100863, 1]) > Mat([21835637060266943, 1]) > Mat([305698921536592063, 1]) > Mat([4279784904205143743, 1]) > Mat([59916988661564867263, 1]) > Mat([838837841264600996543, 1]) > [107, 1; 999236351, 1; 109838361859, 1] > > 11/12: could do better :-) Ah yes: pari's ispseudoprime(p,0), which I have to use since isprime() is unconscionably slow at these heights, is good, but not that good. Thanks for the double-check, which I rashly omitted. Mike djbroadhurst Nov 20 12:27 PM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > pari's ispseudoprime(p,0), which I have to use since isprime() > is unconscionably slow at these heights, is good, but not that > good You would become rather famous (and $640 better off) if you ever found a composite number that passes ispseudoprime(k,0). It is ispseudoprime(k,1) that is leaky. David mikeoakes2 Nov 21 2:02 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > [14*x + 2692854861, [13, 12]] > > but of course Sir won't let me claim it as a 12/12 :-( > > Indeed not, hard-hearted person that I am: > > p=13;for(k=1,12,p=14*p+2692854861;print(factor(p))); > Mat([2692855043, 1]) > Mat([40392825463, 1]) > Mat([568192411343, 1]) > Mat([7957386613663, 1]) > Mat([111406105446143, 1]) > Mat([1559688169100863, 1]) > Mat([21835637060266943, 1]) > Mat([305698921536592063, 1]) > Mat([4279784904205143743, 1]) > Mat([59916988661564867263, 1]) > Mat([838837841264600996543, 1]) > [107, 1; 999236351, 1; 109838361859, 1] > > 11/12: could do better :-) I claim 12/13. (Look at your code: you can't count 12 primes properly:-) Mike djbroadhurst Nov 21 3:27 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > can't count 12 primes properly :-) Dear Mr Oakes As a solicitor with some experience in these matters, I cannot hold out much hope for the outcome of any appeal to the Court of Prime Rights that you might consider making, since the president is almost certain to cite the case of Broadhurst v. Smith, which was presided over by Chief Justice Humpty Dumpty. Recall that Smith made a demonstrably false claim: http://tech.groups.yahoo.com/group/primenumbers/message/22042 > x-->Ax+B (mod M) will be full period M for any prime M dividing A-1 > hence the chain length cannot be longer than M primes in a row Broadhurst disproved Smith's claim here: http://tech.groups.yahoo.com/group/primenumbers/message/22047 > 2, 3, 7, 23 satisfies the recursion x ==> 4*x - 5 This is now referred to as a "plupluperfect case", since there are only M-1 distinct non-zero residues modulo the prime M|A-1, yet Broadhurst found a chain of M+1 primes. To avoid litigation over plupluperfect cases like Broadhurst's (M+1)/(M-1), and merely pluperfect cases with M/(M-1), like those envisaged by Smith and lately reconsidered by your good self, it was thought sufficient (though not necessary) to demand that p[2] > p[1] > A, as in the ruling of Chief Justice Humpty Dumpty: http://tech.groups.yahoo.com/group/primenumbers/message/22094 Some jurists consider this to be wise, in the prevention of arguments over Broadhurst's ultra-rare plupluperfect and Smith's rare pluperfect cases, though some consider that the Chief Justice was arbitrary in his prohibition of the rare perfect case with p[1] = A, for which there is as yet no example with M > 7, where A = 23 appears to be the first possibility. Recent supplications by your good self have (I am told) been viewed unfavourably by Chief Justice Humpty Dumpty, who has been heard to murmur, after a decent bottle of claret in his private chambers, that "this fellow Oakes is a Johnny-come-lately who doesn't even study previous cases thoroughly". It is unfortunate that Chief Justice Humpty Dumpty is of such an irascible, arbitrary and implacable disposition. However, in view of his well-known and long-standing personal faults, I am bound to advise you that there is little hope of your succeeding in any attempt to persuade him to overturn the law on p[2] > p[1] > A, which you clearly find to be ill-considered. Yours regretfully, David Broadhurst Solicitor, pro bono publico mikeoakes2 Nov 21 3:49 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > > > [14*x + 2692854861, [13, 12]] > > > but of course Sir won't let me claim it as a 12/12 :-( > > > > Indeed not, hard-hearted person that I am: > > > > p=13;for(k=1,12,p=14*p+2692854861;print(factor(p))); > > Mat([2692855043, 1]) > > Mat([40392825463, 1]) > > Mat([568192411343, 1]) > > Mat([7957386613663, 1]) > > Mat([111406105446143, 1]) > > Mat([1559688169100863, 1]) > > Mat([21835637060266943, 1]) > > Mat([305698921536592063, 1]) > > Mat([4279784904205143743, 1]) > > Mat([59916988661564867263, 1]) > > Mat([838837841264600996543, 1]) > > [107, 1; 999236351, 1; 109838361859, 1] > > > > 11/12: could do better :-) > > Ah yes: pari's ispseudoprime(p,0), which I have to use since isprime() is unconscionably slow at these heights, is good, but not that good. > Thanks for the double-check, which I rashly omitted. I wrote this because I thought you were saying my 12th term was not prime. Why then, when I indicated as much, did you not kindly put me right, instead of going along with my mistake by posting > You would become rather famous (and $640 better off) > if you ever found a composite number that passes > ispseudoprime(k,0). It is ispseudoprime(k,1) that is leaky. Perhaps trying to make me look daft for as long as possible? :=( Mike mikeoakes2 Nov 21 4:42 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > For Puzzle 2, it was irrelevant whether I wrote > > p[2] > p[1] > A > > or > > p[2] > p[1] >= A > > so I saved myself the ugly-looking redundant keystroke. > > I was, of course, assuming that a solver would choose > A = 12, for 10/10, as did Kevin, and then maybe later > A = 14, for 12/12, as did Kevin and Phil. > > Mike, after both happy events, may like to solve the much harder > Puzzle 4, with A = p[1] = 23 for 10/10, and then maybe later > Puzzle 5, with A = p[1] = 53 for 12/12 > but I was trying to set less fearful puzzles than these > post-hoc inventions. Fearful, eh? [23*x + 90168090, [23, 10]] and [23*x + 96795634, [23, 10]] found in 815 secs. Mike djbroadhurst Nov 21 5:18 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > [23*x + 90168090, [23, 10]] > [23*x + 96795634, [23, 10]] Great stuff, Mike! Now how about p[1] = A = 53, to catch up with Kevin and Phil, who have already scored 12/12, obeying the hateful rule p[2] > p[1] > A. David djbroadhurst Nov 21 5:37 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > It is unfortunate that Chief Justice Humpty Dumpty is of such an > irascible, arbitrary and implacable disposition. However, in view > of his well-known and long-standing personal faults, I am bound > to advise you that there is little hope of your succeeding in any > attempt to persuade him to overturn the law on p[2] > p[1] > A, > which you clearly find to be ill-considered. Dear Mr Oakes Further to my previous advice, I report that my clerk, Mr Robert Cratchit, has observed ribald merriment in the local taverns over the discomfit that you have occasioned for the Chief Justice by your finding with p[1] = A = 23. Mr Cratchit has asked me to tell you that there would be even greater delight were you able to score an "illegally perfect" 12/12, with A = 53, in time for Christmas. Best regards David Broadhurst Solicitor, pro bono publico Kevin Acres Nov 22 11:33 AM ----------------------- Hello Mike, At 11:35 PM 20/11/2010, mikeoakes2 wrote: >--- In primenumbers@yahoogroups.com, Kevin Acres wrote: > > > > I had a preliminary run for 17s. > > > > In my 699 instances, where the chain length was >=9, there were 640 > > chains of 9, 52 chains of 10 and 7 chains of 11. I have still to > > find a chain longer than 11. > >Presumably by "17s" you mean A=20 with max L=18? >(David doesn't let us look at a maximal L=17:-) > >A=18 gives max L=16. >Here is (I think) the longest bounded chain posted so far:- > [18*x + 214555, [86677, 13]] By 17, I meant that the divisor terminating the chain would be 17. Other than that, of course, its A=18 giving a maximum bounded chain length of 16. Yesterday I rewrote my code and overnight I found a couple of chains of length 13. So I can't improve on your find, just equal it. [18*x - 4921333, [4236329, 13]] [18*x - 5182301, [797143, 13]] Also, I like to keep running stats. Just to remind me of the futility of the search using my particular code. The numbers below, from left to right, indicate total chains over length 8 followed by the count of chains found of lengths 9 to 16. [28422, 3642, 501, 69, 9, 2, 0, 0, 0] Obviously its not looking good for even a 14/16 let alone a 16/16 any time soon. Best Regards, Kevin. Phil Carmody Nov 22 4:57 PM ----------------------- -- On Sat, 11/20/10, mikeoakes2 wrote: > --- In primenumbers@yahoogroups.com, > "djbroadhurst" wrote: > > > > I don't mean to be scornful. But I do think > > that I was wise to disallow p[1] = A - 1, > > so as to set a much fairer puzzle than you might > > have done by allowing it. > > 1) > I agree it is a special case. > There's a closely analogous AP-k case - see my 2001 > NMBRTHRY post > http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0106&L=NMBRTHRY&P=R357 This was precisely the problem for which I wrote gensv. > Perhaps we should have Puzzle 3, with p[1]=A-1? > I have solved it for A<=12. > For A=14 I've so far only found > [14*x + 2693409, [13,10]] > Can anyone improve on that? ? b=1209312839547;p=13;for(n=1,13,print(p" "factor(p));p=p*14+b) 13 Mat([13, 1]) 1209312839729 Mat([1209312839729, 1]) 18139692595753 Mat([18139692595753, 1]) 255165009180089 Mat([255165009180089, 1]) 3573519441360793 Mat([3573519441360793, 1]) 50030481491890649 Mat([50030481491890649, 1]) 700427950199308633 Mat([700427950199308633, 1]) 9805992512103160409 Mat([9805992512103160409, 1]) 137283896378757085273 Mat([137283896378757085273, 1]) 1921974550511912033369 Mat([1921974550511912033369, 1]) 26907643708376081306713 Mat([26907643708376081306713, 1]) 376707011918474451133529 Mat([376707011918474451133529, 1]) 5273898166859851628708953 Mat([5273898166859851628708953, 1]) Ditto b=4209599085761 and 6934161472289 djbroadhurst Nov 22 5:42 PM ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > ? b=1209312839547;p=13;for(n=1,13,print(p" "factor(p));p=p*14+b) > Ditto b=4209599085761 and 6934161472289 B=[1209312839547,4209599085761,6934161472289]; f(b)=isprime(vector(13,n,(14^(n-1)-1)*(b/13+13)+13)); for(k=1,3,print(f(B[k]))); [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] Verdicts: pluperfect 13/12, thrice. At this rate, Phil could destroy the jury system. David Phil Carmody Nov 23 2:37 AM ----------------------- -- On Fri, 11/19/10, Jens Kruse Andersen wrote: > David wrote: > > Phil Carmody wrote: > > > >> 17/anything has always been the exclusive domain of > >> the guys with access to 100s of GHz. > > > > That is not clear to me. Understandably. Jens has a way to make it false, but I can hopefully handwave that away by claiming the 17 was accurate to O(1). > > Please see the progression by Jens from > > > > http://tech.groups.yahoo.com/group/primenumbers/message/22048 > > [4*x + 2252715, [1750061, 16]] > > [4*x + 1339065, [1813219, 16]] > > [4*x + 2057595, [2019191, 16]] > > [4*x + 9449115, [2610821, 16]] > > > > to > > > > http://tech.groups.yahoo.com/group/primenumbers/message/22049 > > [4*x + 14882835, [4447297, 17]] > > > > in one day, using (I imagine) considerably less > > than 100 GHz of processing power. > > > > Perhaps Jens might like to comment on Phil's > > overestimate of the burden of 17/infinity? > > It depends on the form and size - and the expected size of > the smallest solution depends on the form. > It only took a few hours at 2.4 GHz and limited efficiency > to find > [4*x + 14882835, [4447297, 17]] > and another case I didn't report: > [4*x + 7792485, [5336489, 17]] > > Phil was probably thinking of problems similar to my > simultaneous primes page. Indeed. > If both a and b are fixed in advance in a prime chain > search for an arbitrary starting prime p then it becomes similar. > My prime chains with arbitrary b wouldn't be allowed at my page. It's not so clear that that should be the case. Would searching for a constellation of Gaussian primes, where you can vary both the x and y coordinates independently be allowed? Merely having 2 parameters isn't enough to put them into a different class. > The required minimum value of a for bounded cases of 17 > mean that the primes > in the smallest solutions will be much larger than in the > unbounded cases > where small a is possible. Finding solutions looks too hard > for me. > > The main reasons I could so easily find 17's are: > 1) The primes in a chain grow relatively slowly with a = 4. > 2) The form allows one to try billions of small (b, p) > combinations. > A few of these combinations are likely to give 17-hits with > small primes. > > A bounded form with a >= 18 doesn't have advantage 1). > Jarek's impressive CC17's didn't have advantage 2) because > a CC fixes b = +/-1 Both of these advantages are ones of size increasing the probability of primality for individual terms. That's not changing the algorithmic complexity of the task as a function of '17', that's just changing the constant factor. However, in contrast, arbitrary prime AP hunts, because they re-use the same primes over and over again, have a clearly smaller big-Oh. I don't see an easy way of re-using the pool technique for arbitrary PAPs as the scaling factor pushes the primes too far apart to sensibly pool. I can imagine multiple pools, one for each band might have some potential, and actually bring the big-Oh() down by more than just the invisible a constant factor. Phil mikeoakes2 Nov 23 9:43 AM ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > > -- On Sat, 11/20/10, mikeoakes2 wrote: > > There's a closely analogous AP-k case - see my 2001 > > NMBRTHRY post > > http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind0106&L=NMBRTHRY&P=R357 > > This was precisely the problem for which I wrote gensv. > > > Perhaps we should have Puzzle 3, with p[1]=A-1? > > I have solved it for A<=12. > > For A=14 I've so far only found > > [14*x + 2693409, [13,10]] > > Can anyone improve on that? > > ? b=1209312839547;p=13;for(n=1,13,print(p" "factor(p));p=p*14+b) > 13 Mat([13, 1]) > 1209312839729 Mat([1209312839729, 1]) > 18139692595753 Mat([18139692595753, 1]) > 255165009180089 Mat([255165009180089, 1]) > 3573519441360793 Mat([3573519441360793, 1]) > 50030481491890649 Mat([50030481491890649, 1]) > 700427950199308633 Mat([700427950199308633, 1]) > 9805992512103160409 Mat([9805992512103160409, 1]) > 137283896378757085273 Mat([137283896378757085273, 1]) > 1921974550511912033369 Mat([1921974550511912033369, 1]) > 26907643708376081306713 Mat([26907643708376081306713, 1]) > 376707011918474451133529 Mat([376707011918474451133529, 1]) > 5273898166859851628708953 Mat([5273898166859851628708953, 1]) > > Ditto b=4209599085761 and 6934161472289 Phil, Many congrats! A few days ago a 22 GHz-hour run with naive, non-sieving pari-GP code (dereived from one of David's posts) had brought me one step away from the goal with [14*x + 2692854861, [13, 12]] Your b in [14*x + 1209312839547, [13, 13]] is about 450 times bigger. This seems like too big a factor. Is it minimal? Another p=13 problem is for a=27, for which after 6 GHz-hours I only have this: [27*x + 714426122, [13,10] Feel like giving it a whirl? Mike Kevin Acres Nov 23 11:27 AM ----------------------- At 07:14 AM 20/11/2010, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >"djbroadhurst" wrote: > > > But how about 16/16, which was what I was encouraging? > > Here we lose Jens's point (1), since a = 17 is the smallest > > bounded possibility. But we still have Jens's point (2), > > which Kevin is currently exploiting, but without Phil's > > smart "gensv" sieve, I imagine. > >Sorry: for "a = 17", read "a = 18", >precisely as Jens had indicated. > >David (not even a decent editor) Getting closer: [18*x + 4143491, [1989217, 15]] [1, 1989217, 1, Mat([1989217, 1])] [2, 39949397, 1, Mat([39949397, 1])] [3, 723232637, 1, Mat([723232637, 1])] [4, 13022330957, 1, Mat([13022330957, 1])] [5, 234406100717, 1, Mat([234406100717, 1])] [6, 4219313956397, 1, Mat([4219313956397, 1])] [7, 75947655358637, 1, Mat([75947655358637, 1])] [8, 1367057800598957, 1, Mat([1367057800598957, 1])] [9, 24607040414924717, 1, Mat([24607040414924717, 1])] [10, 442926727472788397, 1, Mat([442926727472788397, 1])] [11, 7972681094514334637, 1, Mat([7972681094514334637, 1])] [12, 143508259701262166957, 1, Mat([143508259701262166957, 1])] [13, 2583148674622723148717, 1, Mat([2583148674622723148717, 1])] [14, 46496676143209020820397, 1, Mat([46496676143209020820397, 1])] [15, 836940170577762378910637, 1, Mat([836940170577762378910637, 1])] [16, 15064923070399722824534957, 0, [590669385637, 1; 25504831360361, 1]] [17, 271168615267195010845772717, 0, [17, 1; 15951095015717353579163101, 1]] Goodbye! djbroadhurst Nov 23 11:53 AM ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > [18*x + 4143491, [1989217, 15]] > .... > [16, 15064923070399722824534957, 0, > [590669385637, 1; 25504831360361, 1]] Congrats to Kevin for 15/16 in a bounded case. Perhaps Phil's "gensv" might sqeeze it's way to 16/16 ? David Phil Carmody Nov 23 4:12 PM ----------------------- -- On Tue, 11/23/10, mikeoakes2 wrote: > Phil Carmody wrote: > > -- On Sat, 11/20/10, mikeoakes2 wrote: > > > Perhaps we should have Puzzle 3, with p[1]=A-1? > > > I have solved it for A<=12. > > > For A=14 I've so far only found > > > [14*x + 2693409, [13,10]] > > > Can anyone improve on that? > > > > ? b=1209312839547;p=13;for(n=1,13,print(p" "factor(p));p=p*14+b) > > 13 Mat([13, 1]) > > 1209312839729 Mat([1209312839729, 1]) > > 18139692595753 Mat([18139692595753, 1]) > > 255165009180089 Mat([255165009180089, 1]) > > 3573519441360793 Mat([3573519441360793, 1]) > > 50030481491890649 Mat([50030481491890649, 1]) > > 700427950199308633 Mat([700427950199308633, 1]) > > 9805992512103160409 Mat([9805992512103160409, 1]) > > 137283896378757085273 Mat([137283896378757085273, 1]) > > 1921974550511912033369 Mat([1921974550511912033369, 1]) > > 26907643708376081306713 Mat([26907643708376081306713, 1]) > > 376707011918474451133529 Mat([376707011918474451133529, 1]) > > 5273898166859851628708953 Mat([5273898166859851628708953, 1]) > > > > Ditto b=4209599085761 and 6934161472289 > > Phil, > Many congrats! Many thanks. > A few days ago a 22 GHz-hour run with naive, non-sieving If you refuse to sieve, at least please use a dash of CRT. > pari-GP code (dereived from one of David's posts) had > brought me one step away from the goal with > [14*x + 2692854861, [13, 12]] > Your b in > [14*x + 1209312839547, [13, 13]] > is about 450 times bigger. > This seems like too big a factor. > Is it minimal? I've been mostly aiming for minimal ones with the last few little jobs. Something you can get an edge by aiming for a more difficult set where one of several subsets will satisfy your real goal but this wasn't one of them. My tuplet definition file supports my fragile memory, looks like I was looking for 12 (the 0th being for free). > Another p=13 problem is for a=27, for which after 6 > GHz-hours I only have this: > [27*x + 714426122, [13,10] > Feel like giving it a whirl? This should be minimal: b=546529819330 Phil Phil Carmody Nov 23 4:19 PM ----------------------- --- On Tue, 11/23/10, djbroadhurst wrote: > --- In primenumbers@yahoogroups.com, > Kevin Acres wrote: > > > [18*x + 4143491, [1989217, 15]] > > .... > > [16, 15064923070399722824534957, 0, > > [590669385637, 1; 25504831360361, 1]] > > Congrats to Kevin for 15/16 in a bounded case. Indeed, this is a good bit of crunching. > Perhaps Phil's "gensv" might sqeeze it's way to 16/16 ? Not designed for this kind of operation, and too fragile to bend into the right shape. The overhead setting up for the long haul is too much for it to be able to chop and change between lots of related smaller searches. Phil, on an absolute not-gonna-sleep-for-hours buzz from seeing Paul Gilbert live tonight Phil Carmody Nov 23 4:40 PM ----------------------- --- On Wed, 11/24/10, Phil Carmody wrote: > > pari-GP code (dereived from one of David's posts) had > > brought me one step away from the goal with > > [14*x + 2692854861, [13, 12]] > > Your b in > > [14*x + 1209312839547, [13, 13]] > > is about 450 times bigger. > > This seems like too big a factor. > > Is it minimal? > looks like I was looking for 12 (the 0th being for free). Rerunning the search with a target of only 11 gives these: _Tup11: 2692854861 _Tup11: 26162859701 _Tup11: 36770798139 _Tup11: 75890821611 _Tup11: 103977434165 _Tup11: 112295583249 _Tup11: 240372365375 _Tup11: 344428960469 _Tup11: 346201222715 _Tup11: 460936618019 _Tup11: 541450505859 _Tup11: 655277285645 _Tup11: 798426756087 _Tup11: 1199918975517 _Tup12: 1209312839547 (and another at 4209599085761) Perhaps your 12 (i.e. '13' plus 11 more) can be considered early? Then again, the stats after sieving the block containing my hit were: [7:1892 8:614 9:170 10:40 11:14 12:1 ] so mine was certainly a little tardy. (After finding the second: [7:4959 8:1493 9:424 10:113 11:37 12:2] When I pressed ^C: [7:5788 8:1710 9:465 10:130 11:40 12:2] so those full sets are playing hard to find...) Phil Kevin Acres Nov 23 11:12 PM ----------------------- At 06:53 AM 24/11/2010, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >Kevin Acres wrote: > > > [18*x + 4143491, [1989217, 15]] > > .... > > [16, 15064923070399722824534957, 0, > > [590669385637, 1; 25504831360361, 1]] > >Congrats to Kevin for 15/16 in a bounded case. >Perhaps Phil's "gensv" might sqeeze it's way to 16/16 ? I spent a while today writing a C language GMP version of my script. Two items of note here: Firstly my sieve had a big hole in it, so the 15/16 was indeed fortuitous. Now I'm re-running yesterdays ranges to find what I missed. Secondly the C based program only runs 20% faster than GP. GP is fast! If anyone wants a copy of either or both of the C or GP scripts then please let me know and I can pass them on. The're a little scrappy, but functional. Lastly I think that the 16/16 is probably out of reach for a single PC in a sensible amount of time. I observed today that wide shallow searches (high 'b' range and low 'x' range) turn up more long chains than narrow deep searches (low 'b' high 'x'). For example searching with x ranges up to 5*10^12 seems less fruitful than searching a wider range of b values to a depth of 5*10^6 Regards, Kevin. Kevin Acres Nov 24 3:56 PM ----------------------- At 06:27 AM 24/11/2010, Kevin Acres wrote: >[18*x + 4143491, [1989217, 15]] [ snip ] Another 15/16 [18*x + 18192515, [1087, 15]] It's encouraging to get a couple of 15/16 results in as many days. It is, however, a little strange that I'm not seeing any 14/16 as yet. [1, 1087, 1, 1, Mat([1087, 1])] [2, 18212081, 5, 1, Mat([18212081, 1])] [3, 346009973, 5, 1, Mat([346009973, 1])] [4, 6246372029, 5, 1, Mat([6246372029, 1])] [5, 112452889037, 5, 1, Mat([112452889037, 1])] [6, 2024170195181, 5, 1, Mat([2024170195181, 1])] [7, 36435081705773, 5, 1, Mat([36435081705773, 1])] [8, 655831488896429, 5, 1, Mat([655831488896429, 1])] [9, 11804966818328237, 5, 1, Mat([11804966818328237, 1])] [10, 212489402748100781, 5, 1, Mat([212489402748100781, 1])] [11, 3824809249484006573, 5, 1, Mat([3824809249484006573, 1])] [12, 68846566490730310829, 5, 1, Mat([68846566490730310829, 1])] [13, 1239238196833163787437, 5, 1, Mat([1239238196833163787437, 1])] [14, 22306287542996966366381, 5, 1, Mat([22306287542996966366381, 1])] [15, 401513175773945412787373, 5, 1, Mat([401513175773945412787373, 1])] [16, 7227237163931017448365229, 5, 0, [43, 1; 4817, 1; 34892107718936409559, 1]] [17, 130090268950758314088766637, 5, 0, [17, 1; 7652368761809312593456861, 1]] Goodbye! BTW both 15/16 chains are all 5 mod 6 expect for the first value which is 1 mod 6. Is there anyone that can tell me if I should read anything in to this or not? Regards, Kevin. Kevin Acres Nov 24 5:42 PM ----------------------- At 10:56 AM 25/11/2010, Kevin Acres wrote: >Another 15/16 > >[18*x + 18192515, [1087, 15]] > >It's encouraging to get a couple of 15/16 results in as many days. > >It is, however, a little strange that I'm not seeing any 14/16 as yet. Finally got my 14/16: [18*x + 20425405, [580081, 14]] Jens Kruse Andersen Nov 24 8:00 PM ----------------------- Phil Carmody wrote: > -- On Fri, 11/19/10, Jens Kruse Andersen wrote: >> If both a and b are fixed in advance in a prime chain >> search for an arbitrary starting prime p then it becomes similar. >> My prime chains with arbitrary b wouldn't be allowed at my page. > > It's not so clear that that should be the case. > > Would searching for a constellation of Gaussian primes, where > you can vary both the x and y coordinates independently be > allowed? Merely having 2 parameters isn't enough to put them > into a different class. My simultaneous primes page is only for primes in the natural numbers. There is no precedent I'm aware of so I set the rules. I deliberately want to exclude any form where a prime can be "reused" as a potential member of many different sets of primes. Such things will also often have different complexities and make a record page less meaningful. The algorithmic principle for record setters should be: "Are these k numbers all prime?" This will usually be tested with sieving followed by k prp tests when none have small factors. It shouldn't be: "Can we find k numbers with some connection in this prime set?" Nor should it be: "Can this prime somehow be combined with k-1 other numbers that are also prime?" Prime chains with arbitrary b can fix the initial prime and vary b. There may be some judgment calls and I'm the judge at my own website. > I don't see an easy way of re-using the pool technique for > arbitrary PAPs as the scaling factor pushes the primes too far > apart to sensibly pool. I can imagine multiple pools, one for > each band might have some potential, and actually bring the > big-Oh() down by more than just the invisible a constant factor. Actually, my 17's used a pool-like method. All primes below 1.6*10^9 were stored in a bit array and primality tests were made by table lookup for the start of chains. prp tests were only made for chains extending above 1.6*10^9 which was relatively rare for my small numbers and a=4. Other parts of the program were inefficient. Constant factors are often important in practice even though theorists may say things like "Does that really matter when the problem gets a million times larger?" or "Constant factors are implementation dependent". -- Jens Kruse Andersen Kevin Acres Nov 24 11:32 PM ----------------------- At 12:42 PM 25/11/2010, Kevin Acres wrote: >At 10:56 AM 25/11/2010, Kevin Acres wrote: > > >Another 15/16 > > > >[18*x + 18192515, [1087, 15]] > > > >It's encouraging to get a couple of 15/16 results in as many days. > > > >It is, however, a little strange that I'm not seeing any 14/16 as yet. >Finally got my 14/16: > >[18*x + 20425405, [580081, 14]] Perhaps someone can let me know if I have these numbers about right. It seems to me that each longer chain takes about 8 times as long as the one before to pccur. So a 9/16 occurs once in every 8 8/16, a 10/16 once every 8 9/16, etc. Now if I get a 13/16 once an hour then means that I should get a 16/16 after approximately 8^3 hours, or about 3 weeks. Am I wildly wrong on this, or do others find this a possible timeframe. Regards, Kevin. djbroadhurst Nov 25 4:28 AM ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > [16, 7227237163931017448365229, 5, 0, > [43, 1; 4817, 1; 34892107718936409559, 1]] A finer sieve should help. In the "Cratchit" problem, with p[1] = A = 53, I was able to get 11/12 primes after sieving to ensure that none of the 12 targets had a prime divisor less than 10^6: b=1836738674044;p=53;for(k=1,12,print(factor(p));p=53*p+b) Mat([53, 1]) Mat([1836738676853, 1]) Mat([99183888547253, 1]) Mat([5258582831678453, 1]) [2406461, 1; 115816016473, 1] \\ Rats! Mat([14771458358073172853, 1]) Mat([782887294814616835253, 1]) Mat([41493026627011430942453, 1]) Mat([2199130411233442578624053, 1]) Mat([116553911795374293405748853, 1]) Mat([6177357325154839387243363253, 1]) Mat([327399938233206489360636926453, 1]) b=2044903327000;p=53;for(k=1,12,print(factor(p));p=53*p+b) Mat([53, 1]) Mat([2044903329809, 1]) [8272531, 1; 13348367, 1] \\ Rats! Mat([5854558233091481, 1]) Mat([310293631257175493, 1]) Mat([16445564501533628129, 1]) Mat([871614920626185617837, 1]) Mat([46195590795232741072361, 1]) Mat([2448366312149380180162133, 1]) Mat([129763414543919194451920049, 1]) Mat([6877460970827719350855089597, 1]) Mat([364505431453869127640223075641, 1]) I spent a few hours sieving (with ForTran :-) and then merely a few seconds PRPing the sparse output (with Pari-GP). I think the "Cratchit" problem may be solved in a few GHz-days, rather than weeks. David Phil Carmody Nov 25 5:59 PM ----------------------- () ASCII ribbon campaign () Hopeless ribbon campaign /\ against HTML mail /\ against gratuitous bloodshed [stolen with permission from Daniel B. Cristofani] Show message history Phil Carmody Nov 25 6:25 PM ----------------------- From: Jens Kruse Andersen > Phil Carmody wrote: > > -- On Fri, 11/19/10, Jens Kruse Andersen wrote: > >> If both a and b are fixed in advance in a prime chain > >> search for an arbitrary starting prime p then it becomes similar. > >> My prime chains with arbitrary b wouldn't be allowed at my page. > > > > It's not so clear that that should be the case. > > > > Would searching for a constellation of Gaussian primes, where > > you can vary both the x and y coordinates independently be > > allowed? Merely having 2 parameters isn't enough to put them > > into a different class. > > My simultaneous primes page is only for primes in the natural numbers. I threw that example in there to muddy the waters a bit, i.e. to confuse and distract rather than enlighten. I could possibly have chosen a better example. > There is no precedent I'm aware of so I set the rules. > I deliberately want to exclude any form where a prime can be "reused" > as a potential member of many different sets of primes. Such things > will also often have different complexities and make a record page > less meaningful. The algorithmic principle for record setters should be: > "Are these k numbers all prime?" > This will usually be tested with sieving followed by k prp tests when > none have small factors. It shouldn't be: > "Can we find k numbers with some connection in this prime set?" > Nor should it be: > "Can this prime somehow be combined with k-1 other numbers that are also > prime?" > Prime chains with arbitrary b can fix the initial prime and vary b. > > There may be some judgment calls and I'm the judge at my own website. Absolutely. I fully support your strict stance, and the scientific and objective way that you have chosen it. > > I don't see an easy way of re-using the pool technique for > > arbitrary PAPs as the scaling factor pushes the primes too far > > apart to sensibly pool. I can imagine multiple pools, one for > > each band might have some potential, and actually bring the > > big-Oh() down by more than just the invisible a constant factor. > > Actually, my 17's used a pool-like method. All primes below 1.6*10^9 > were stored in a bit array and primality tests were made by table > lookup for the start of chains. prp tests were only made for chains > extending above 1.6*10^9 which was relatively rare for my small > numbers and a=4. Other parts of the program were inefficient. The majority of the potentially interesting candidates (ones somewhere on an extension) were probably not in the pool, so thats not the same kind of pool as with arbibitrary APs, in my book. It's more a cache. > Constant factors are often important in practice even though theorists > may say things like "Does that really matter when the problem gets a > million times larger?" or "Constant factors are implementation > dependent". Indeed true. Phil djbroadhurst Nov 26 12:16 AM ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > ? b=1000020829600;p=53;for(k=1,12,print(factor(p));p=53*p+b) > So you should have already found that one?!?! Not so. 1000020829600 is divisible by 13, so yours is not a "bounded case". There is no 12/12 solution with b less than 5T and coprime to 13. Here is another failure, scoring 11/12, where 12 is the maximum for the "Cratchit" case, p[1] = a = 53 and gcd(b,13) = 1, b=4113911326630;a=53;p=a; for(k=1,13,print([k,factor(p)]);p=a*p+b); [1, Mat([53, 1])] [2, Mat([4113911329439, 1])] [3, Mat([222151211786897, 1])] [4, Mat([11778128136032171, 1])] [5, Mat([624244905121031693, 1])] [6, Mat([33084984085326006359, 1])] [7, Mat([1753504160636189663657, 1])] [8, Mat([92935720517831963500451, 1])] [9, Mat([4925593187449207976850533, 1])] [10, Mat([261056438934812136684404879, 1])] [11, [17936163134069, 1; 771401952587293, 1]] \\ Rats! [12, Mat([733307536967887514097704943131, 1])] [13, [13, 1; 48467295901, 1; 61683623242622853221, 1] \\ Bounded! Thanks, Phil, for your interest and sound advice; I was indeed sieving far too deep. David Broadhurst, per proxy the Timothy Cratchit Festive Fund Phil Carmody Nov 26 3:22 AM ----------------------- --- On Fri, 11/26/10, djbroadhurst wrote: > --- In primenumbers@yahoogroups.com, > > > ? > b=1000020829600;p=53;for(k=1,12,print(factor(p));p=53*p+b) > > So you should have already found that one?!?! > > Not so. > > 1000020829600 is divisible by 13, so yours is not a "bounded case". Ack. And ack. > There is no 12/12 solution with b less than 5T and coprime to 13. Added a 'remove 0 mod 13' to my filter, and got: b=16283956408890 However, I was updating my CV (one of those weeks), and forgot to press ^C, so these also appeared: 19263862775184 27178481084314 38820955823040 47678624731440 72089104084570 78612681049254 113561887221160 113198201738740 126941317757320 130809650617920 178638800388790 226611746113494 281503127904844 366202208750470 385911894122574 402108434845924 419168651610970 442605825190920 458500720068054 472426301730904 558645834378984 569392063117684 And here I ^C'd. > Thanks, Phil, for your interest and sound > advice; I was indeed sieving far too deep. If there's one thing in the world I can do reasonably well, it's probably advice on sieving! > David Broadhurst, per proxy the Timothy Cratchit Festive Humbug! Phil Phil Carmody Nov 26 9:50 AM ----------------------- --- On Thu, 11/25/10, Kevin Acres wrote: > [1, 1087, 1, 1, Mat([1087, 1])] > [2, 18212081, 5, 1, Mat([18212081, 1])] > [3, 346009973, 5, 1, Mat([346009973, 1])] > [4, 6246372029, 5, 1, Mat([6246372029, 1])] > [5, 112452889037, 5, 1, Mat([112452889037, 1])] > [6, 2024170195181, 5, 1, Mat([2024170195181, 1])] > [7, 36435081705773, 5, 1, Mat([36435081705773, 1])] > [8, 655831488896429, 5, 1, Mat([655831488896429, 1])] > [9, 11804966818328237, 5, 1, Mat([11804966818328237, 1])] > [10, 212489402748100781, 5, 1, Mat([212489402748100781, 1])] > [11, 3824809249484006573, 5, 1, Mat([3824809249484006573, 1])] > [12, 68846566490730310829, 5, 1, Mat([68846566490730310829, 1])] > [13, 1239238196833163787437, 5, 1, Mat([1239238196833163787437, 1])] > [14, 22306287542996966366381, 5, 1, Mat([22306287542996966366381, 1])] > [15, 401513175773945412787373, 5, 1, Mat([401513175773945412787373, 1])] > [16, 7227237163931017448365229, 5, 0, [43, 1; 4817, 1; 34892107718936409559, 1]] > [17, 130090268950758314088766637, 5, 0, [17, 1; 7652368761809312593456861, 1]] > > BTW both 15/16 chains are all 5 mod 6 expect for the first value > which is 1 mod 6. > > Is there anyone that can tell me if I should read anything > in to this or not? Well, multiplying by 18 and then adding a constant tends to keep your residue modulo 18 pretty constant. Phil Kevin Acres Nov 26 12:42 PM ----------------------- Hi Phil, At 04:50 AM 27/11/2010, Phil Carmody wrote: >--- On Thu, 11/25/10, Kevin Acres wrote: > > [1, 1087, 1, 1, Mat([1087, 1])] >[ snip ] > > [17, 130090268950758314088766637, 5, 0, [17, 1; > 7652368761809312593456861, 1]] > > > > BTW both 15/16 chains are all 5 mod 6 expect for the first value > > which is 1 mod 6. > > > > Is there anyone that can tell me if I should read anything > > in to this or not? > >Well, multiplying by 18 and then adding a constant tends to keep >your residue modulo 18 pretty constant. I was just wondering, given the odds of finding 2 15/16 chains and then both having the same 15555.. residues, whether I could focus the search a little more? It's just that this is my first attempt at writing something to perform such a task and I could use every speedup possible. I've identified the start position of potential 16/16 chains by creating a wheel of size 510510. I've not yet been able to correctly code up something to avoid sieving out collisions with primes above 17. One of the main problems that I'm finding is that ispseudoprime() is dumping about 2/3 of candidates from the wheel, so I have to try and work something out for better efficiency in this area too. Best Regards, Kevin. djbroadhurst Nov 27 7:21 AM ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > Added a 'remove 0 mod 13' to my filter, and got: > b=16283956408890 .... > 569392063117684 Great stuff, Phil. Here is a compact proof of your 23 solutions: cratchit(b)=sum(n=1,12,isprime((53^(n-1)-1)*(b/52+53)+53)); {B=[16283956408890, 19263862775184, 27178481084314, 38820955823040, 47678624731440, 72089104084570, 78612681049254, 113561887221160, 113198201738740, 126941317757320, 130809650617920, 178638800388790, 226611746113494, 281503127904844, 366202208750470, 385911894122574, 402108434845924, 419168651610970, 442605825190920, 458500720068054, 472426301730904, 558645834378984, 569392063117684];} print(sum(k=1,#B,B[k]%13&&cratchit(B[k])==12)); 23 David Kevin Acres Nov 27 8:48 PM ----------------------- At 10:56 AM 25/11/2010, Kevin Acres wrote: >>[18*x + 4143491, [1989217, 15]] > >Another 15/16 > >[18*x + 18192515, [1087, 15]] I must be beating the odds on the 15/16 chains: [18*x - 54818687, [16723501, 15]] [1, 18, -54818687, 1, 16723501, Mat([16723501, 1])] [2, 18, -54818687, 1, 246204331, Mat([246204331, 1])] [3, 18, -54818687, 1, 4376859271, Mat([4376859271, 1])] [4, 18, -54818687, 1, 78728648191, Mat([78728648191, 1])] [5, 18, -54818687, 1, 1417060848751, Mat([1417060848751, 1])] [6, 18, -54818687, 1, 25507040458831, Mat([25507040458831, 1])] [7, 18, -54818687, 1, 459126673440271, Mat([459126673440271, 1])] [8, 18, -54818687, 1, 8264280067106191, Mat([8264280067106191, 1])] [9, 18, -54818687, 1, 148757041153092751, Mat([148757041153092751, 1])] [10, 18, -54818687, 1, 2677626740700850831, Mat([2677626740700850831, 1])] [11, 18, -54818687, 1, 48197281332560496271, Mat([48197281332560496271, 1])] [12, 18, -54818687, 1, 867551063986034114191, Mat([867551063986034114191, 1])] [13, 18, -54818687, 1, 15615919151748559236751, Mat([15615919151748559236751, 1])] [14, 18, -54818687, 1, 281086544731474011442831, Mat([281086544731474011442831, 1])] [15, 18, -54818687, 1, 5059557805166532151152271, Mat([5059557805166532151152271, 1])] [16, 18, -54818687, 1, 91072040492997578665922191, [83, 1; 3863, 1; 30549061, 1; 9297889937239, 1]] [17, 18, -54818687, 1, 1639296728873956415931780751, [17, 1; 43961, 1; 381644633, 1; 5747539022831, 1]] Regards, Kevin. mikeoakes2 Nov 29 3:27 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "djbroadhurst" wrote: > > > > hence the chain length cannot be longer than M primes > > Counterexample: The chain of primes 2, 3, 7, 23 > > satisfies the recursion x ==> 4*x - 5. > > Off list, Warren wrote to me saying: > > > In computer programming this is called a "boundary case bug." > > I actually knew this when I wrote the theorem+proof > > but I was too lazy/lame to state+do it fully right. > > In mathematics, this is called an "error in reasoning". > The error is easily repaired: for > "cannot be longer than M primes", read > "cannot be longer than 2*M-1 primes". > > Proof: An integer sequence generated by the map x ==> A*x + B, > with A = 1 mod M, and B coprime to the prime M, will > contain at least two multiples of M if the length of the sequence > exceeds 2*M-1. No more than one of these multiples may be prime. [David's post was on 14 November: http://tech.groups.yahoo.com/group/primenumbers/message/22050 ] I can improve this bound to "cannot be longer than M+1 primes" Proof: An integer sequence generated by the map x ==> A*x + B, with A = 1 mod M, and B coprime to the prime M, will contain at least two multiples of M if the length of the sequence exceeds M-1. If both these are to be prime, the first must be M itself. This need not be the first prime in the sequence, but cannot come later than the second. Because MA Proof: p3=A*p2+B=A*p2+(p2-A*p1)=A*(p2-p1)+p2>A QED Mike djbroadhurst Nov 29 5:02 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > I can improve this bound to > "cannot be longer than M+1 primes" > Proof: p3=A*p2+B=A*p2+(p2-A*p1)=A*(p2-p1)+p2>A A good proof, thanks. Note that I was careful to demand that p[2] > p[1]. > 2, 3, 7, 23 satisfies the recursion x ==> 4*x - 5 > This is now referred to as a "plupluperfect case", since > there are only M-1 distinct non-zero residues modulo > the prime M|A-1, yet Broadhurst found a chain of M+1 primes. Did you find any other plupluperfect case? David mikeoakes2 Nov 29 5:23 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > I can improve this bound to > > "cannot be longer than M+1 primes" > > > Proof: p3=A*p2+B=A*p2+(p2-A*p1)=A*(p2-p1)+p2>A > > A good proof, thanks. > Note that I was careful to demand that p[2] > p[1]. > > > 2, 3, 7, 23 satisfies the recursion x ==> 4*x - 5 > > This is now referred to as a "plupluperfect case", since > > there are only M-1 distinct non-zero residues modulo > > the prime M|A-1, yet Broadhurst found a chain of M+1 primes. > > Did you find any other plupluperfect case? Yes, as well as your [4*x - 5, [2, 4]] I have found 3 more: [10*x - 17, [2, 4]] [16*x - 27, [2, 6]] [730*x - 1457, [2, 4]] Note that the second starts 2, 5,.. and has score "6/5". Mike djbroadhurst Nov 29 5:46 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > Did you find any other plupluperfect case? > > Yes, as well as your > [4*x - 5, [2, 4]] > I have found 3 more: > [10*x - 17, [2, 4]] > [16*x - 27, [2, 6]] > [730*x - 1457, [2, 4]] Is it posssible, in principle, for a plupluperfect chain to begin with an odd prime? David (who does not know) mikeoakes2 Nov 29 6:04 AM ----------------------- > [10*x - 17, [2, 4]] > [16*x - 27, [2, 6]] > [730*x - 1457, [2, 4]] > > Note that the second starts 2, 5,.. and has score "6/5". Here is a fuller picture. In http://tech.groups.yahoo.com/group/primenumbers/message/22094 David wrote: > Definition: A "Smith chain" of length L is a chain > p[n+1] = A*p[n] + B, such that p[n] is prime, > for n = 1 to L, with p[2] > p[1] > A. > Definition: A "maximal Smith chain" is a Smith chain with > integers (A,B) for which there is a proof that no chain > of greater length exists. In http://tech.groups.yahoo.com/group/primenumbers/message/22134 Chief Justice Humpty Dumpty laid down the law regarding this area of number theory. Discussion of this may now be sub judice, so, to avoid possible contempt of court, let me make my own definitions:- Definition: A "power chain" of length L is a chain p[n+1] = A*p[n] + B, such that p[n] is prime, for n = 1 to L, with p[2] > p[1]. Definition: A "maximal power chain" is a power chain with integers (A,B) for which there is a proof that no chain of greater length exists. Nota bene: the condition p[1] > A is nowhere to be seen. Notation: "L1/L2" means that L2 = (largest prime divisor of (A-1)) - 1 L2 is the longest possible power chain starting at an arbitrary p1 L1 = length of chain L1 can = (L2+1) if (L2+1) is the first or second prime in the chain L1 can = (L2+2) if (L2+1) is the second prime in the chain L1 can never exceed (L2+2) (proved in my post earlier today) There are no maximal power chains for A<=2. For A<=53, the longest found to date (by me except where otherwise stated) are listed below. For each A the first example is for "general" p1, the next ones being appropriate to pluperfect and/or plupluperfect cases. A=3 B not multiple of 2 1/1: [3*x + 1, [3, 1]] 2/1: [3*x + 1, [2, 2]] A=4 B odd; B not multiple of 3 2/2: [4*x - 11, [7, 2]] 3/2: [4*x + 1, [3, 3]] 4/2: [4*x - 5, [2, 4]] [David Broadhurst] Note (2) A=5 1 B not multiple of 2 1/1: [5*x + 1, [3, 1]] 2/1: [5*x + 1, [2, 2]] A=6 B odd; B not multiple of 3 or 5 4/4: [6*x + 1, [61, 4]] 5/4: [6*x + 7, [5, 5]] 5/4: [6*x - 13, [3, 5]] Note (1) A=7 B even; B not multiple of 3 or 7 2/2: [7*x + 4, [7, 2]] 3/2: [7*x + 2, [3, 3]] A=8 B odd; B not multiple of 7 6/6: [8*x - 9, [9497, 6]] 7/6: [8*x + 755, [7, 7]] A=9 B not multiple of 2 1/1: [9*x + 1, [3, 1]] 2/1: [9*x + 1, [2, 2]] A=10 B odd; B not multiple of 3 or 5 2/2: [10*x - 1, [3, 2]] 3/2: [10*x + 1, [3, 3] 4/2: [10*x - 17, [2, 4]] Note (2) A=11 B even; B not multiple of 5 or 11 4/4: [11*x - 2, [863, 4]] 5/4: [11*x - 8, [5, 5]] A=12 B odd; B not multiple of 3 or 11 10/10: [12*x - 1267, [4937, 10]] 11/10: [12*x + 143588905, [11, 11]] A=13 2 B even; B not multiple of 3 or 13 2/2: [13*x + 2, [3, 2]] 3/2: [13*x - 2, [3, 3]] A=14 B odd; B not multiple of 7 or 13 12/12: [14*x + 139, [240738291413, 12]] [Phil Carmody] 12/12: [14*x - 2907, [15145447, 12]] [Kevin Acres] 12/12: [14*x + 434527, [83969, 12]] 13/12: [14*x + 1209312839547, [13, 13]] [Phil Carmody] A=15 B even; B not multiple of 3 or 5 or 7 6/6: [15*x + 2, [331, 6]] 7/6: [15*x + 8248, [7, 7]] A=16 B odd; B not multiple of 15 4/4: [16*x + 3, [1933, 4]] 5/4: [16*x + 9, [5, 5]] 6/4: [16*x - 27, [2, 6]] Note (2) A=17 B not multiple of 2 1/1: [17*x + 1, [3, 1]] 2/1:[17*x + 3, [2, 2]] A=18 B odd; B not multiple of 3 or 17 15/16: [18*x + 4143491, [1989217, 15]] [Kevin Acres] 11/16: [18*x + 8616643901, [17, 11]] A=19 B even; B not multiple of 3 2/2: [19*x - 2, [7, 2]] 3/2: [19*x + 2, [3, 3]] A=20 B odd; B not multiple of 5 or 19 12/18: [20*x - 236433, [38047, 12]] 11/18: [20*x + 816431099, [19, 11]] A=21 B even; B not multiple of 3 or 5 or 7 4/4: [21*x + 2, [17, 4]] 5/4: [21*x + 32, [5, 5]] A=22 B odd; B not multiple of 11 or 21 6/6: [22*x - 15, [1063,6]] 7/6: [22*x + 67665, [7,7]] A=23 B even; B not multiple of 11 or 23 10/10: [23*x - 35230, [5437,10]] 11/10: [23*x + 895648, [11,11]] A=24 B odd; B not multiple of 3 or 23 11/22: [24*x + 195151, [463,11]] 9/22: [24*x + 74800001, [23, 9]] A=25 B even; B not multiple of 3 or 5 2/2: [25*x + 2, [5,2]] 3/2: [25*x - 2, [3,3]] A=26 B odd; B not multiple of 5 or 13 4/4: [26*x - 1, [79, 4]] 5/4: [26*x - 77, [5, 5]] A=27 B even; B not multiple of 3 or 13 12/12: [27*x + 253750, [21557,12]] 13/12: [27*x + 546529819330, [13,13]] [Phil Carmody] A=28 B odd; B not multiple of 3 or 7 2/2: [28*x - 1, [3, 2]] 3/2: [28*x - 5, [3, 3]] 3/2: [28*x - 53, [2,3]]] Note (1) A=29 B even; B not multiple of 7 or 29 6/6: [29*x + 34, [9281,6]] 7/6: [29*x + 3404, [7,7]] A=30 B odd; B not multiple of 3 or 5 or 29 11/28 [30*x - 74971, [4261, 11]] 10/28: [30*x + 149083787, [29, 10]] A=31 4 B even; B not multiple of 15 or 31 4/4: [31*x - 6, [199, 4]] 5/4: [31*x + 1932, [5, 5]] A=32 B odd; B not multiple of 31 11/30:[32*x + 61435, [9539, 11]] 10/30: [32*x + 10764725, [31, 10]] A=33 B not multiple of 2 1/1: [33*x + 1, [3, 1]] 2/1: [33*x + 1, [2, 2]] A=34 B odd; B not multiple of 17 or 33 10/10: [34*x - 120171, [9013, 10]] 11/10 [34*x + 1065279669, [11, 11]] 35 16 B even; B not multiple of 5 or 7 or 17 11/16: [35*x + 9372, [547, 11]] 10/16: [35*x + 224171062, [17, 10]] A=36 B odd; B not multiple of 3 or 35 6/6: [36*x - 5, [5021, 6]] 7/6: [36*x + 406555, [7, 7]] A=37 B even; B not multiple of 3 or 37 2/2: [37*x - 2, [7, 2]] 3/2: [37*x - 8, [3, 3]] A=38 B odd; B not multiple of 19 or 37 12/36: [38*x + 198513, [3371, 12]] 10/36: [38*x + 240171935, [37, 10]] A=39 B even; B not multiple of 3 or 13 or 19 10/18: [39*x + 1694, [4987, 10]] 10/18: [39*x + 335356142, [19, 10]] A=40 B odd; B not multiple of 5 or 39 9/12: [40*x - 2109, [179, 9]] 9/12: [40*x + 270765429, [13, 9]] A=41 B even; B not multiple of 5 or 41 4/4: [41*x - 2, [1493, 4]] 5/4: [41*x - 8, [5, 5]] A=42 B odd; B not multiple of 3 or 7 or 41 12/40: [42*x + 800617, [8443, 12]] 10/40: [42*x + 393399485, [41, 10]] A=43 B even; B not multiple of 3 or 7 or 43 6/6: [43*x - 30, [9973, 6]] 7/6: [43*x + 22710, [7, 7]] A=44 B odd; B not multiple of 11 or 43 12/42: [44*x - 8829, [389, 12]] 10/42: [44*x + 97190571, [43, 10]] A=45 10 B even; B not multiple of 3 or 5 or 11 10/10: [45*x - 19208, [823, 10]] 10/10: [45*x + 152616148, [11, 10]] A=46 4 B odd; B not multiple of 23 or 15 4/4: [46*x - 3, [2287, 4]] 5/5: [46*x - 117, [5, 5]] A=47 22 B even; B not multiple of 23 or 47 11/22: [47*x + 84018, [4297, 11]] 11/22: [47*x + 339856132, [23, 11]] A=48 46 B odd; B not multiple of 3 or 47 11/46: [48*x - 294205, [6829, 11]] 9/46: [48*x + 713735, [47, 9]] A=49 B even; B not multiple of 3 or 7 2/2: [49*x + 2, [11, 2]] 3/2: [49*x - 8, [3, 3]] A=50 B odd; B not multiple of 5 or 7 6/6: [50*x - 3, [8761, 6]] 7/6: [50*x + 22031, [7, 7]] A=51 B even; B not multiple of 3 or 5 or 17 4/4: [51*x - 2, [3, 4]] 5/4: [51*x - 14, [5, 5]] A=52 B odd; B not multiple of 13 or 51 9/16: [52*x - 7245, [3499, 9]] 9/16: [52*x + 924931623, [17, 9]] A=53 B even; B not multiple of 13 or 53 11/12: [53*x - 129488, [81749, 11]] 10/12: [53*x + 776681300, [13, 10]] Note (1): a second pluperfect Note (2): a plupluperfect Each of these data points comes from at most a few hours' processing with very inefficient code, so there is plenty of scope for improvement. Of course, to turn 11/46: [48*x - 294205, [6829, 11]] into 46/46: [48*x - ??, [??, 46]] would take many times the age of the universe. Mike djbroadhurst Nov 29 6:23 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > A=53 B even; B not multiple of 13 or 53 > 11/12: [53*x - 129488, [81749, 11]] > 10/12: [53*x + 776681300, [13, 10]] Please do not forget Phil's feat in finding 12/12 in 23 cases with p[1] = A = 53: http://tech.groups.yahoo.com/group/primenumbers/message/22169 David mikeoakes2 Nov 29 8:18 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > A=53 B even; B not multiple of 13 or 53 > > 11/12: [53*x - 129488, [81749, 11]] > > 10/12: [53*x + 776681300, [13, 10]] > > Please do not forget Phil's feat in finding > 12/12 in 23 cases with p[1] = A = 53: > http://tech.groups.yahoo.com/group/primenumbers/message/22169 Indeed, and apologies to Phil for my oversight. Also, if people were to work actively on other improvements (easy enough), the table would need updating. Is there enough interest in this do you think to merit your allocating a website page to record the latest status of the group's communal efforts? Mike djbroadhurst Nov 29 11:34 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > [10*x - 17, [2, 4]] > [16*x - 27, [2, 6]] > [730*x - 1457, [2, 4]] > Note that the second starts 2, 5,.. and has score "6/5". I call that 6/4 amd so (it seems) do you: > A=16 B odd; B not multiple of 15 > 6/4: [16*x - 27, [2, 6]] Note (2) David djbroadhurst Nov 29 11:37 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Is it posssible, in principle, for a > plupluperfect chain to begin with an odd prime? It seems to me to be possible, in principle, but it may be heuristically improbable. Consider this near miss: addprimes(1702797053666877373); a=2147483648000000001;b=-6442450943999999998; p=3;for(k=1,6,print(factor(p));p=a*p+b); Mat([3, 1]) Mat([5, 1]) Mat([4294967296000000007, 1]) Mat([9223372036854775820884901888000000009, 1]) Mat([19807040628566084435279475731419103257769803776000000011, 1]) [307, 1; 1579, 1; 1702797053666877373, 1; 51530702425970397925353744317622361514359534110977, 1] There was, a priori, no obvious reason why the 6th term must be composite. It was, however, rather improbable that all 6 terms would be prime. David mikeoakes2 Nov 30 1:08 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > Is it posssible, in principle, for a > > plupluperfect chain to begin with an odd prime? > > It seems to me to be possible, in principle, > but it may be heuristically improbable. > > Consider this near miss: > > addprimes(1702797053666877373); > a=2147483648000000001;b=-6442450943999999998; > p=3;for(k=1,6,print(factor(p));p=a*p+b); > > Mat([3, 1]) > Mat([5, 1]) > Mat([4294967296000000007, 1]) > Mat([9223372036854775820884901888000000009, 1]) > Mat([19807040628566084435279475731419103257769803776000000011, 1]) > [307, 1; 1579, 1; 1702797053666877373, 1; > 51530702425970397925353744317622361514359534110977, 1] > > There was, a priori, no obvious reason why the 6th term > must be composite. It was, however, rather improbable > that all 6 terms would be prime. D'accord. I had planned to make exactly this point, based on > [6*x - 13, [3, 5]] Note (1) for which p6=3113=11*283. I ran searches like yours, of type A=2^s*3^t*5^u*7^v+1, a couple of days ago and found no more pluluperfects than the 4 we know of. I'm coming to believe their number is in fact finite (not necessarily 4, but...), for the same sort of reason that the number of Fermat primes (almost certainly) is. A probability argument, using PNT, shouldn't be too hard to construct. Mike mikeoakes2 Nov 30 2:04 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > [10*x - 17, [2, 4]] > > [16*x - 27, [2, 6]] > > [730*x - 1457, [2, 4]] > > Note that the second starts 2, 5,.. and has score "6/5". > > I call that 6/4 amd so (it seems) do you: > > > A=16 B odd; B not multiple of 15 > > 6/4: [16*x - 27, [2, 6]] Note (2) Yes, 6/5 was a typo. For a plupluperfect chain of length 4, A must be of form 3^t+1. For 1<=t<=10000, there are only the 3 we know of, namely: t=1,2,6. Mike djbroadhurst Nov 30 2:05 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > a=2147483648000000001;b=-6442450943999999998; > I ran searches like yours, of type A=2^s*3^t*5^u*7^v+1, > a couple of days ago and found no more pluluperfects In the course of such searches I happened to see the prime p = 12566416644664544212553 flash by on screen. It seemed to me to have a rather pleasing "shape" in base 10. I tried to demystify this, but the best I could do was to trace its appearance on screen as the largest prime divisor of the cubic f(x) = x^3 + 5*x^2 + 10*x + 10 with 5*x = 80^10. I remark that the cubic has discriminant -200. if(poldisc(f(x))==-200&&Mod(f(80^10/5),p)==0,print(OK)); OK Yet I cannot see why a /factor/ of N = f(80^10/5) should have any notable shape in base 10. So perhaps the "shape" of p = 12566416644664544212553 was just an accident? David mikeoakes2 Nov 30 3:52 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > > For a plupluperfect chain of length 4, A must be of form 3^t+1. > For 1<=t<=10000, there are only the 3 we know of, namely: t=1,2,6. Predicted number, from PNT, is: 2*zeta(2)/log(3)^2=(Pi/log(3))^2/3=2.72577237357 which agrees nicely with the experimental value of 3. Exercise for the reader: derive this formula. Mike djbroadhurst Nov 30 4:03 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > found no more pluluperfects than the 4 we know of I have found more than 60 :-) > I'm coming to believe their number is in fact finite Seems unlikely to me, since it's rather easy to manufacture them: a=28108400488659906;b=-84325201465979713; p=3;for(k=1,6,print(factor(p));p=a*p+b) Mat([3, 1]) Mat([5, 1]) Mat([56216800977319817, 1]) Mat([1580164356061792941035408441177489, 1]) Mat([44415892558090266401505943385819479019796838076321, 1]) Mat([1248459696084090326462578778340820797435925794167271904670774706113, 1]) David djbroadhurst Nov 30 4:18 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > For a plupluperfect chain of length 4, A must be of form 3^t+1. Not so. a=1531473015305018167008722120995247602572259132860010870169890; b=3-2*a;p=2;for(k=1,4,print1(isprime(p)" ");p=a*p+b); 1 1 1 1 David djbroadhurst Nov 30 4:32 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: Here's a plupluperfect chain of 8: p=3;for(k=1,9,print([k,factor(p)]);p=140820*p-422453) [1, Mat([3, 1])] [2, Mat([7, 1])] [3, Mat([563287, 1])] [4, Mat([79321652887, 1])] [5, Mat([11170075159124887, 1])] [6, Mat([1572969983907966164887, 1])] [7, Mat([221505633133919795338964887, 1])] [8, Mat([31192423257918585579633034964887, 1])] [9, [7, 1; 627502434740013603046274854822137841, 1]] \\ Bounded! David mikeoakes2 Nov 30 4:42 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > found no more pluluperfects than the 4 we know of > > I have found more than 60 :-) > > > I'm coming to believe their number is in fact finite > > Seems unlikely to me, since it's rather easy to manufacture them: > > a=28108400488659906;b=-84325201465979713; > p=3;for(k=1,6,print(factor(p));p=a*p+b) > > Mat([3, 1]) > Mat([5, 1]) > Mat([56216800977319817, 1]) > Mat([1580164356061792941035408441177489, 1]) > Mat([44415892558090266401505943385819479019796838076321, 1]) > Mat([1248459696084090326462578778340820797435925794167271904670774706113, 1]) > That's not a plupluperfect 6/4, it's a far-from-perfect 6/5621680097731982 isn't it? Mike djbroadhurst Nov 30 5:02 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > a far-from-perfect > 6/5621680097731982 > isn't it? Absolutely not. There is a proof that in a chain of primes with this (A,B) pair there are no more than 4 primes with p > 5 and no more than 6 primes in toto. Hence Mat([3, 1]) Mat([5, 1]) Mat([56216800977319817, 1]) Mat([1580164356061792941035408441177489, 1]) Mat([44415892558090266401505943385819479019796838076321, 1]) Mat([1248459696084090326462578778340820797435925794167271904670774706113, 1]) gives the "plupluperfect" score of 6/4. Your observation that the chain length cannot exceed 5621680097731982 is utterly relevant, since we have proven that it cannot exceed 6, which is well known to be less than 5621680097731982. David djbroadhurst Nov 30 5:07 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Your observation that the chain length cannot exceed 5621680097731982 > is utterly relevant, since we have proven that it cannot exceed > 6, which is well known to be less than 5621680097731982. There is a nice Freudian slip above :-) David (irrelevantly:-) mikeoakes2 Nov 30 5:17 AM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > a far-from-perfect > > 6/5621680097731982 > > isn't it? > > Absolutely not. There is a proof that in a chain of > primes with this (A,B) pair there are no more than 4 > primes with p > 5 and no more than 6 primes in toto. Hence > > Mat([3, 1]) > Mat([5, 1]) > Mat([56216800977319817, 1]) > Mat([1580164356061792941035408441177489, 1]) > Mat([44415892558090266401505943385819479019796838076321, 1]) > Mat([1248459696084090326462578778340820797435925794167271904670774706113, 1]) > > gives the "plupluperfect" score of 6/4. > > Your observation that the chain length cannot exceed 5621680097731982 > is utterly [ir]relevant, since we have proven that it cannot exceed > 6, which is well known to be less than 5621680097731982. We are at cross purposes. (Like Humpty Dumpty, I too can make rules:-) I thought you were playing the game as per http://tech.groups.yahoo.com/group/primenumbers/message/22175 where I defined "L1/L2" by > Notation: > "L1/L2" means that > L2 = (largest prime divisor of (A-1)) - 1 and where a plupluperfect chain has L1=L2+2. You are playing a different game. Please define /your/ notation! Mike djbroadhurst Nov 30 6:16 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > Please define /your/ notation! "Plupluferfect" was first used in: http://tech.groups.yahoo.com/group/primenumbers/message/22134 > 2, 3, 7, 23 satisfies the recursion x ==> 4*x - 5 > This is now referred to as a "plupluperfect case", since > there are only M-1 distinct non-zero residues modulo > the prime M|A-1, yet Broadhurst found a chain of M+1 primes. I have used that coinage consistently ever since, in at least half a dozen messages on the plupluperfect case. Moreover I am also scrupulously abiding by /your/ definitions: http://tech.groups.yahoo.com/group/primenumbers/message/22175 > Definition: A "power chain" of length L is a chain > p[n+1] = A*p[n] + B, such that p[n] is prime, > for n = 1 to L, with p[2] > p[1]. > Definition: A "maximal power chain" is a power chain with > integers (A,B) for which there is a proof that no chain > of greater length exists. Thus Mat([3, 1]) Mat([5, 1]) Mat([56216800977319817, 1]) Mat([1580164356061792941035408441177489, 1]) Mat([44415892558090266401505943385819479019796838076321, 1]) Mat([1248459696084090326462578778340820797435925794167271904670774706113, 1]) is a "maximal power chain" of length 6, according to Oakes, a "maximal Smith chain" of length 4, according to Humpty, and hence a "plupluperfect" 6/4, according to Broadhurst. Apologies if my abbreviation of Oakes/Humpty = 6/4, for the above, was confusing, in the light of the notation > L2 = (largest prime divisor of (A-1)) - 1 adopted in your tables, which post-date my consistent questions about the plupluperfect case. Clearly /your/ L2 is irrelevant to /your/ definition of "maximal", since for "maximality" we must replace your "largest" by "smallest". A chain whose length is 6, in a situation where we have /proven/ that there can be no longer chain, is clealry "maximal", according to you, and hence "plupluperfect" according to me. That it has L2 > 6 is irrelevant to plupluperfection. Conclusion: You were pefectly free to use L2 in your tables. But those tables did not adequately address my question about the plupluperfect case. David mikeoakes2 Nov 30 6:24 AM ----------------------- The only way I can rescue the picture in http://tech.groups.yahoo.com/group/primenumbers/message/22175 from David's onslaughts is by appending the 3 words "for that A" to > Definition: A "maximal power chain" is a power chain with > integers (A,B) for which there is a proof that no chain > of greater length exists. That's what was behind > Notation: > "L1/L2" means that > L2 = (largest prime divisor of (A-1)) - 1 Apologies to David in particular for my carelessness. Mike djbroadhurst Nov 30 9:36 AM ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > For 1<=t<=10000, there are only the 3 we know of, namely: > t=1,2,6. Mike was asking that N = 3^t+4 M = (N-2)*(N-3)+3 be simultaneously prime. The Poisson mean for such cases with t > x >> 1 may be estimated as C/(2*log(3)^2)*sum(t>x,1/t^2) =~ C/(2*log(3)^2)/x where C is a constant of order unity. To determine C we would need to take account of the discriminant D = -11 of the quadratic M = (N-2)*(N-3)+3. For example, M is always coprime to 2, 3, 7, 13, 17, 19, 29 ... > Predicted number, from PNT, is: > 2*zeta(2)/log(3)^2=(Pi/log(3))^2/3=2.72577237357 > which agrees nicely with the experimental value of 3. > Exercise for the reader: derive this formula. To "derive" the formula we would need to make 2 rather poor choices: 1) set C = 4, thus ignoring the discriminant, above, 2) set x = 0, thus applying the PNT all the way down to N = 7. More meaningfully, I estimate that C =~ 5.5 and hence that the probabilty of a 4th case, with t > 10^4, is about 5.5/(2*log(3)^2)/10^4 =~ 0.00023. David djbroadhurst Nov 30 1:19 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > asking that > N = 3^t+4 > M = (N-2)*(N-3)+3 > be simultaneously prime. The Poisson mean for > such cases with t > x >> 1 may be estimated as > C/(2*log(3)^2)*sum(t>x,1/t^2) =~ C/(2*log(3)^2)/x > where C is a constant of order unity. Sieving to depth 10^8, with the aid of "znorder" and "polrootsmod" in Pari-GP, I estimated C ~ 6.5, but the convergence is not good: {mp=nextprime(10^8);default(primelimit,mp); default(realprecision,5);n=1;g=1.;forprime(p=5,mp, if(p>10^n,print([g*log(p)^2*exp(2*Euler),p]);n++); a=znorder(Mod(3,p));b=znorder(Mod(-4,p));c=if(a%b,0,1); f=lift(polrootsmod((x+1)*(x+2)+3,p));for(k=1,#f,r=f[k]; if(r,b=znorder(Mod(r,p));c+=if(a%b,0,1)));g*=1-c/a);} [7.6000, 11] [7.4962, 101] [7.4031, 1009] [7.5940, 10007] [7.2959, 100003] [7.0154, 1000003] [6.7590, 10000019] [6.5402, 100000007] David (puzzled by this slow convergence) djbroadhurst Nov 30 1:32 PM ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > "Plupluferfect" was first used in: > http://tech.groups.yahoo.com/group/primenumbers/message/22134 It's a good day for Freudian slips :-) Perhaps "plupluferfect" might apply to Joyce's Anna Livia Plurabelle, as here: http://www.youtube.com/watch?v=TUS7HgyouSI David mikeoakes2 Dec 1, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > "mikeoakes2" wrote: > > > For 1<=t<=10000, there are only the 3 we know of, namely: > > t=1,2,6. > > Mike was asking that > N = 3^t+4 > M = (N-2)*(N-3)+3 > be simultaneously prime. The Poisson mean for > such cases with t > x >> 1 may be estimated as > C/(2*log(3)^2)*sum(t>x,1/t^2) =~ C/(2*log(3)^2)/x > where C is a constant of order unity. > To determine C we would need to take account of the discriminant > D = -11 of the quadratic M = (N-2)*(N-3)+3. For example, > M is always coprime to 2, 3, 7, 13, 17, 19, 29 ... > > > Predicted number, from PNT, is: > > 2*zeta(2)/log(3)^2=(Pi/log(3))^2/3=2.72577237357 > > which agrees nicely with the experimental value of 3. > > Exercise for the reader: derive this formula. > > To "derive" the formula we would need to make 2 rather poor choices: > 1) set C = 4, thus ignoring the discriminant, above, > 2) set x = 0, thus applying the PNT all the way down to N = 7. > > More meaningfully, I estimate that C =~ 5.5 and hence that > the probabilty of a 4th case, with t > 10^4, is about > 5.5/(2*log(3)^2)/10^4 =~ 0.00023. Thanks for those refinements, David. As you know, my "4" came from the fact that the 3rd and 4th terms of the sequence are known to be odd; and I didn't get round to including those other factors which increase the probability of primehood by a amall multiple, analogous to what happens for AP-k's. I have an analogous bound, considerably less than 1, for the expected number of plupluperfect maximal power chains (in my sense) of length L=6 (of which exactly one example is known). As L increases beyond 6, the expectation is << 1, as there are more and more powers of log(2), log(3), log(5) etc. in the denominator of the expression, and also a factor (L-2)! there. I reckon the series converges. It's relatively unusual in [prime] number theory to find a small finite set of objects, so I'm happy to proffer the following. Definition: A "power chain" of length L is a chain p[n+1] = A*p[n] + B, such that p[n] is prime, for n = 1 to L, with p[2] > p[1]. Definition: A "maximal power chain" is a power chain with integers (A,B) for which there is a proof that no chain of greater length exists for that A. Defininition: L2(A) = (largest prime divisor of (A-1)) - 1. Conjecture: there are only 4 maximal power chains of length >= L2(A)+2. $$lots for anyone who can find a 5th one (not:-) Mike djbroadhurst Dec 1, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > Definition: A "maximal power chain" is a power chain with > integers (A,B) for which there is a proof that no chain > of greater length exists for that A. "For that A" does not make sense. If you specify only A, then I may always choose a B such that /no/ proof exists. Hence your "maximal" length is unbounded, "for that A". However, no worry: we do not need the word "maximal". > Definition: L2(A) = (largest prime divisor of (A-1)) - 1. > Conjecture: there are only 4 maximal power chains of > length >= L2(A)+2. So let's make that clear and self contained: ! Mike Oakes conjectures that for chains x-->Ax+B, with ! A > 2 and B /coprime/ to the /largest/ prime divisor M|A-1, ! it is possible to find a chain of M+1 increasing primes ! in precisely 4 cases. This erases historical confusion and concentrates on what you actually studied, with /coprime/ and /largest/ spelled out as the central points of a (now) coherent conjecture. > $$lots for anyone who can find a 5th one (not:-) How many zlotys are you offering :-? David djbroadhurst Dec 1, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > As you know, my "4" came from the fact that the 3rd and 4th > terms of the sequence are known to be odd Those terms are also coprime to 3, so you might, with equal arbitrariness, have set C = (2/1)^2*(3/2)^2 = 9, as I did on first seeing your "exercise". The asymptotic constant seems to lie between 4 and 9, but is hard (for me) to estimate accurately. David (over-exercised :-) djbroadhurst Dec 1, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Here's a plupluperfect chain of 8: > > p=3;for(k=1,9,print([k,factor(p)]);p=140820*p-422453) > [1, Mat([3, 1])] > [2, Mat([7, 1])] > [3, Mat([563287, 1])] > [4, Mat([79321652887, 1])] > [5, Mat([11170075159124887, 1])] > [6, Mat([1572969983907966164887, 1])] > [7, Mat([221505633133919795338964887, 1])] > [8, Mat([31192423257918585579633034964887, 1])] > [9, [7, 1; 627502434740013603046274854822137841, 1]] \\ Bounded! Puzzle 11: Find a plupluperfect chain of 12, i.e. a triplet (A, B, p[1]) such that A = 1 mod 11, B is coprime to 11, and the iteration p[n+1] = A*p[n] + B yields a chain of 12 increasing primes, p[n], for n = 1 to 12. Comments: Clearly, p[2] = 11 and hence B = 11 - A*p[1], with p[1] = 2, 3, 5 or 7. So this boils down to 4 sub-problems of Carmody-scale difficulty (maybe easy for Phil; harder for mere mortals like Kevin, Mike, or me). I did not yet find a solution. David Kevin Acres Dec 1, 2010 ----------------------- Hello David, At 02:18 PM 2/12/2010, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >"djbroadhurst" wrote: > > > Here's a plupluperfect chain of 8: > > > > p=3;for(k=1,9,print([k,factor(p)]);p=140820*p-422453) > > [1, Mat([3, 1])] > > [2, Mat([7, 1])] > > [3, Mat([563287, 1])] > > [4, Mat([79321652887, 1])] > > [5, Mat([11170075159124887, 1])] > > [6, Mat([1572969983907966164887, 1])] > > [7, Mat([221505633133919795338964887, 1])] > > [8, Mat([31192423257918585579633034964887, 1])] > > [9, [7, 1; 627502434740013603046274854822137841, 1]] \\ Bounded! > >Puzzle 11: Find a plupluperfect chain of 12, i.e. a triplet >(A, B, p[1]) such that A = 1 mod 11, B is coprime to 11, >and the iteration p[n+1] = A*p[n] + B yields a chain of >12 increasing primes, p[n], for n = 1 to 12. > >Comments: Clearly, p[2] = 11 and hence B = 11 - A*p[1], with >p[1] = 2, 3, 5 or 7. So this boils down to 4 sub-problems of >Carmody-scale difficulty (maybe easy for Phil; harder for mere >mortals like Kevin, Mike, or me). I did not yet find a solution. > >David I won't jump into this one just yet. I'm turning over about 56000 8/16 chains per hour currently for Puzzle 2. My hope is that I'll get one 16/16 per 8^8 8/16 and find another five 15/16 chains on the way. I had a quick check though, but my current script doesn't lend itself to pluperfect chains let alone plupluperfect. Best Regards, Kevin. djbroadhurst Dec 1, 2010 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > I won't jump into this one just yet. I indicated that Puzzle 11 is rather tough :-) I was hoping to tempt Phil... > I'm turning over about 56000 8/16 chains per hour currently > for Puzzle 2. My hope is that I'll get one 16/16 16/16 for Puzzle 2 would be magnificent: best of luck! David Kevin Acres Dec 2, 2010 ----------------------- Hello David, At 03:35 PM 2/12/2010, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >Kevin Acres wrote: > > > I won't jump into this one just yet. > >I indicated that Puzzle 11 is rather tough :-) >I was hoping to tempt Phil... > Actually I did have a quick look. We had a power cut here, so before restarting the main puzzle 2 search I had a look at puzzle 11. Seems very difficult to get a 8/12 let alone a 12/12 :-( Best Regards, Kevin. Phil Carmody Dec 2, 2010 ----------------------- > Puzzle 11: Find a plupluperfect chain of 12, i.e. a > triplet > (A, B, p[1]) such that A = 1 mod 11, B is coprime to 11, > and the iteration p[n+1] = A*p[n] + B yields a chain of > 12 increasing primes, p[n], for n = 1 to 12. > > Comments: Clearly, p[2] = 11 and hence B = 11 - A*p[1], with > p[1] = 2, 3, 5 or 7. So this boils down to 4 sub-problems of > Carmody-scale difficulty (maybe easy for Phil; harder for mere > mortals like Kevin, Mike, or me). I did not yet find a solution. This doesn't fit the 'tuplet' pattern, but would fall to raw 'gensv'. Unfortunately the only wrapper around 'gensv' that works currently is 'tuplet', not the raw engine. So I'll have to duck out of this until 2015, when I finally get gensv working again. Phil djbroadhurst Dec 3, 2010 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > Seems very difficult to get a 8/12 I found it rather easy to get a 8/12: p=7;for(k=1,8,print(factor(p));p=96328365*p-674298544); Mat([7, 1]) Mat([11, 1]) Mat([385313471, 1]) Mat([37116615999606371, 1]) Mat([3575382933574921687714871, 1]) Mat([344410792240175811180613435317371, 1]) Mat([33176528504850823203577211921154930229871, 1]) Mat([3195840747248174368104654975623363340731873292371, 1]) and not much harder to get a 9/12: p=3;for(k=1,9,print(factor(p));p=237862725*p-713588164); Mat([3, 1]) Mat([11, 1]) Mat([1902901811, 1]) Mat([452629409458306811, 1]) Mat([107663664748893631236931811, 1]) Mat([25609172680658279861161720490056811, 1]) Mat([6091467598816933241588548501453247755681811, 1]) Mat([1448933082303802516987335475350335971266609083806811, 1]) Mat([344647171299431744552466406656001243790997338184040724431811, 1]) but then it did indeed start to get tough. David Phil Carmody Dec 4, 2010 ----------------------- -- On Fri, 12/3/10, djbroadhurst wrote: > --- In primenumbers@yahoogroups.com, > Kevin Acres wrote:> > > Seems very difficult to get a 8/12 > > I found it rather easy to get a 8/12: > > p=7;for(k=1,8,print(factor(p));p=96328365*p-674298544); > Mat([7, 1]) > Mat([11, 1]) > Mat([385313471, 1]) > Mat([37116615999606371, 1]) > Mat([3575382933574921687714871, 1]) > Mat([344410792240175811180613435317371, 1]) > Mat([33176528504850823203577211921154930229871, 1]) > Mat([3195840747248174368104654975623363340731873292371, > 1]) And you were only looking for an 8 by the looks of it - term 9 has 17 as a factor. > and not much harder to get a 9/12: > > p=3;for(k=1,9,print(factor(p));p=237862725*p-713588164); > Mat([3, 1]) > Mat([11, 1]) > Mat([1902901811, 1]) > Mat([452629409458306811, 1]) > Mat([107663664748893631236931811, 1]) > Mat([25609172680658279861161720490056811, 1]) > Mat([6091467598816933241588548501453247755681811, 1]) > Mat([1448933082303802516987335475350335971266609083806811, > 1]) > Mat([344647171299431744552466406656001243790997338184040724431811, > 1]) Ditto, term 12 having a 23 as a factor. > but then it did indeed start to get tough. Corroborated: (and here, as 2 are for free, 7=9) v=vector(10);p1=2;B=11-x*p1;p=p1;for(k=1,12,print(p);if(k>2,v[k-2]=p);p=p*x+B) while(n=input(),r=0;for(k=1,10,if(ispseudoprime(subst(v[k],x,n)),r++,break));if(r>6,print(r," ",n))) 7 29709057996454 7 7263780549444 7 151166246100 7 65068011125074 7 84114269577064 7 76656931587534 7 59402114114520 7 119930340985104 7 101318539628098 7 116698909426848 7 88188386883268 7 149758381779964 7 130740466545294 7 156653024729950 7 128889269017180 7 212346115784100 7 193981060196650 7 183192393790770 7 245317914267790 7 253470779612920 7 252069956363974 7 281241306114990 7 333285815039134 7 306117971946744 7 376527527757800 7 347395912514014 7 374726694989208 7, 7, 7 - is all I'm gonna get limited to 7!??!!??!!? 7 383891136345938 7 389994524189634 7 391059035903064 7 449305599037824 7 493191506880678 8 491550335809204 9 519815699116440 Phew, that's a little better! 7 595324234851644 7 629916755202098 7 655175951516384 7 704886845640968 7 706950011329310 7 733442990291760 7 807366280229158 7 774858123263324 7 778469035284238 7 842319483923908 7 874455217723220 7 898020387684784 7 888526524582104 7 903179551644778 7 973402495542698 7 955060423888748 7 1068303740684214 7 1045881643505370 7 1086729527030588 7 1116917783358818 9 1188368874866394 7 1177489195413664 7 1172652104044378 7 1223056406479128 7 1240318813279338 7 1212277454482458 7 1224158658202514 7 1221132485837100 7 1236501442911098 Giving up on 2, 11. Will try 3, 11... mikeoakes2 Dec 4, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > --- In primenumbers@yahoogroups.com, > Kevin Acres wrote: > > > Seems very difficult to get a 8/12 > > I found it rather easy to get a 8/12: > > p=7;for(k=1,8,print(factor(p));p=96328365*p-674298544); > Mat([7, 1]) > Mat([11, 1]) > Mat([385313471, 1]) > Mat([37116615999606371, 1]) > Mat([3575382933574921687714871, 1]) > Mat([344410792240175811180613435317371, 1]) > Mat([33176528504850823203577211921154930229871, 1]) > Mat([3195840747248174368104654975623363340731873292371, 1]) > > and not much harder to get a 9/12: > > p=3;for(k=1,9,print(factor(p));p=237862725*p-713588164); > Mat([3, 1]) > Mat([11, 1]) > Mat([1902901811, 1]) > Mat([452629409458306811, 1]) > Mat([107663664748893631236931811, 1]) > Mat([25609172680658279861161720490056811, 1]) > Mat([6091467598816933241588548501453247755681811, 1]) > Mat([1448933082303802516987335475350335971266609083806811, 1]) > Mat([344647171299431744552466406656001243790997338184040724431811, 1]) > > but then it did indeed start to get tough. Using a non-sieving script, I have gone up to a=1.8*10^10, for all 4 starting p, and have found no 10/12's, just your 9/12 and 2 new ones, viz. [237862725*x - 713588164, [3, 9]] [4939393834*x - 9878787657, [2, 9]] [7484387043*x - 52390709290, [7, 9]] Mike mikeoakes2 Dec 4, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > > > asking that > > N = 3^t+4 > > M = (N-2)*(N-3)+3 > > be simultaneously prime. The Poisson mean for > > such cases with t > x >> 1 may be estimated as > > C/(2*log(3)^2)*sum(t>x,1/t^2) =~ C/(2*log(3)^2)/x > > where C is a constant of order unity. > > Sieving to depth 10^8, with the aid of "znorder" and > "polrootsmod" in Pari-GP, I estimated > C ~ 6.5, but the convergence is not good: > > {mp=nextprime(10^8);default(primelimit,mp); > default(realprecision,5);n=1;g=1.;forprime(p=5,mp, > if(p>10^n,print([g*log(p)^2*exp(2*Euler),p]);n++); > a=znorder(Mod(3,p));b=znorder(Mod(-4,p));c=if(a%b,0,1); > f=lift(polrootsmod((x+1)*(x+2)+3,p));for(k=1,#f,r=f[k]; > if(r,b=znorder(Mod(r,p));c+=if(a%b,0,1)));g*=1-c/a);} > > [7.6000, 11] > [7.4962, 101] > [7.4031, 1009] > [7.5940, 10007] > [7.2959, 100003] > [7.0154, 1000003] > [6.7590, 10000019] > [6.5402, 100000007] > > David (puzzled by this slow convergence) That's a really neat script, and (after formatting it properly:-) I believe it. But you were clearly running 64-bit pari, since > default(realprecision,5); gives only 9-digit precision in 32-bit pari, and that's not accurate enough. To make the code portable, you should have written something like \p 18 default(format,"g0.5"); I have gone up to nextprime(4*10^9) and have 2 new points for you:- [6.35205959664247940, 1000000007] [6.25064108108829438, 4000000007] Convergence still slow. Mike djbroadhurst Dec 4, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "mikeoakes2" wrote: > Using a non-sieving script, I have gone up to a=1.8*10^10, > for all 4 starting p, and have found no 10/12's, just your > 9/12 and 2 new ones, viz. > [237862725*x - 713588164, [3, 9]] > [4939393834*x - 9878787657, [2, 9]] > [7484387043*x - 52390709290, [7, 9]] I tested all with p[3] < 10^11, finding 7/12: 2336 8/12: 60 9/12: 3 (as above) Apologies for setting a puzzle that now seems far too hard :-( David djbroadhurst Dec 4, 2010 ----------------------- --- In primenumbers@yahoogroups.com, Phil Carmody wrote: > > but then it did indeed start to get tough. > Corroborated: (and here, as 2 are for free, 7=9) ... > 9 519815699116440 ... > 9 1188368874866394 Congrats to Phil for scoring 11/12, twice: {A=[519815699116440,1188368874866394];q=2; for(k=1,#A,a=A[k];b=11-q*a;p=q;if(a%11==1, for(n=1,12,print1(isprime(p)" ");p=a*p+b));print());} 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 David djbroadhurst Dec 5, 2010 ----------------------- --- In primenumbers@yahoogroups.com, "djbroadhurst" wrote: > Congrats to Phil for scoring 11/12, twice Starting with 3, 11 ... , Phil found a third 11/12: {A=[507876501124257];q=3; for(k=1,#A,a=A[k];b=11-q*a;p=q;if(a%11==1, for(n=1,12,print1(isprime(p)" ");p=a*p+b));print());} 1 1 1 1 1 1 1 1 1 1 1 0 David Kevin Acres Dec 11, 2010 ----------------------- 4th 15/16 see below. Also I had a rather long term (~100 day) search for a 16/16 running. However, repetitive power outages, and a script that didn't really lend it self to multiple restarts, rather negated my interest in continuing this particular search. Instead I have narrowed my search to blocks that take about 80 hours running time with a script that is simple to restart at arbitrary points after loss of power. The first such script is due to complete in a little under 9 hours time and completely covers the (bounded search) range: 1 < b < 102102000 1 < x < 65345280 I'll post the stats later in case anyone is interested. Regards, Kevin. >>>[18*x + 4143491, [1989217, 15]] >>[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] [18, 76622095, 221831641] [1, 221831641, Mat([221831641, 1])] [2, 4069591633, Mat([4069591633, 1])] [3, 73329271489, Mat([73329271489, 1])] [4, 1320003508897, Mat([1320003508897, 1])] [5, 23760139782241, Mat([23760139782241, 1])] [6, 427682592702433, Mat([427682592702433, 1])] [7, 7698286745265889, Mat([7698286745265889, 1])] [8, 138569161491408097, Mat([138569161491408097, 1])] [9, 2494244906921967841, Mat([2494244906921967841, 1])] [10, 44896408324672043233, Mat([44896408324672043233, 1])] [11, 808135349844173400289, Mat([808135349844173400289, 1])] [12, 14546436297195197827297, Mat([14546436297195197827297, 1])] [13, 261835853349513637513441, Mat([261835853349513637513441, 1])] [14, 4713045360291245551864033, Mat([4713045360291245551864033, 1])] [15, 84834816485242420010174689, Mat([84834816485242420010174689, 1])] [16, 1527026696734363560259766497, [26073724847, 1; 58565728743971951, 1]] [17, 27486480541218544084752419041, [17, 1; 19832315467, 1; 81526123322948819, 1]] djbroadhurst Dec 11, 2010 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > 4th 15/16 see below. > [16, 1527026696734363560259766497, > [26073724847, 1; 58565728743971951, 1]] Thanks to strong effort by Kevin and Phil, I have hope that the elusive target of 16/16, in Puzzle 2, http://tech.groups.yahoo.com/group/primenumbers/message/22087?var=0 set on 17 November 2010, might eventually be achieved. It is both chastening and instructive to see others making good progress on a puzzle whose solution lies beyond my present ability. David Kevin Acres Dec 12, 2010 ----------------------- Stats as promisied. At 10:14 AM 12/12/2010, Kevin Acres wrote: >Instead I have narrowed my search to blocks that take about 80 hours >running time with a script that is simple to restart at arbitrary >points after loss of power. > >The first such script is due to complete in a little under 9 hours >time and completely covers the (bounded search) range: > >1 < b < 102102000 >1 < x < 65345280 > >I'll post the stats later in case anyone is interested. For 18*x+b in the range 0 < b < 102102000, 1 < x < 65345280 I found: 8/16: 3744400 9/16: 530548 10/16: 68566 11/16: 8216 12/16: 925 13/16: 107 14/16: 11 15/16: 2 16/16: 0 Giving a total of 4352775 chains of 8/16 or better in an 82 hour period, or ~53000 per hour. My other 2 15/16 chains are outside of this range and I don't have meaningful stats for those. Maybe someone can work out, from the above, a ball park figure for obtaining a 16/16. I originally estimated a power of 8 decrease in chains found for each increase in chain length but it can clearly be seen that I was mistaken in this. Regards, Kevin. Kevin Acres Dec 21, 2010 ----------------------- 5th and 6th 15/16. Still awaiting the elusive 16/16. >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] [18*x + 319862525, [25667359, 15]] [1, 25667359, Mat([25667359, 1])] [2, 781874987, Mat([781874987, 1])] [3, 14393612291, Mat([14393612291, 1])] [4, 259404883763, Mat([259404883763, 1])] [5, 4669607770259, Mat([4669607770259, 1])] [6, 84053259727187, Mat([84053259727187, 1])] [7, 1512958994951891, Mat([1512958994951891, 1])] [8, 27233262228996563, Mat([27233262228996563, 1])] [9, 490198720441800659, Mat([490198720441800659, 1])] [10, 8823576968272274387, Mat([8823576968272274387, 1])] [11, 158824385429220801491, Mat([158824385429220801491, 1])] [12, 2858838937726294289363, Mat([2858838937726294289363, 1])] [13, 51459100879073617071059, Mat([51459100879073617071059, 1])] [14, 926263815823325427141587, Mat([926263815823325427141587, 1])] [15, 16672748684819858008411091, Mat([16672748684819858008411091, 1])] [16, 300109476326757444471262163, [73, 1; 13553, 1; 323052337, 1; 938963095771, 1]] [17, 5401970573881634000802581459, [17, 1; 103, 1; 587, 1; 5255668529038781441807, 1]] [18*x + 386886155, [57802093, 15]] [1, 57802093, Mat([57802093, 1])] [2, 1427323829, Mat([1427323829, 1])] [3, 26078715077, Mat([26078715077, 1])] [4, 469803757541, Mat([469803757541, 1])] [5, 8456854521893, Mat([8456854521893, 1])] [6, 152223768280229, Mat([152223768280229, 1])] [7, 2740028215930277, Mat([2740028215930277, 1])] [8, 49320508273631141, Mat([49320508273631141, 1])] [9, 887769149312246693, Mat([887769149312246693, 1])] [10, 15979844688007326629, Mat([15979844688007326629, 1])] [11, 287637204384518765477, Mat([287637204384518765477, 1])] [12, 5177469678921724664741, Mat([5177469678921724664741, 1])] [13, 93194454220591430851493, Mat([93194454220591430851493, 1])] [14, 1677500175970646142213029, Mat([1677500175970646142213029, 1])] [15, 30195003167471630946720677, Mat([30195003167471630946720677, 1])] [16, 543510057014489357427858341, [1237, 1; 94219, 1; 3295561, 1; 1415044311227, 1]] [17, 9783181026260808434088336293, [17, 1; 3500041, 1; 164421284447488210669, 1]] djbroadhurst Dec 22, 2010 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > 5th and 6th 15/16. ... > [16, 300109476326757444471262163, > [73, 1; 13553, 1; 323052337, 1; 938963095771, 1]] ... > [16, 543510057014489357427858341, > [1237, 1; 94219, 1; 3295561, 1; 1415044311227, 1]] Thanks, Kevin, for persevering. > Still awaiting the elusive 16/16. Any estimate on how many 15's you might need to find before the elusive 16/16 emerges? I still have not understood why Phil does not sieve deeper than thee (whose wheel still allows a factor as small as 73). But then I am a self-confessed failure, at this too-hard puzzle. Best regards David (with chagrin) Kevin Acres Dec 22, 2010 ----------------------- Hello David, At 05:18 AM 23/12/2010, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >Kevin Acres wrote: > > > Still awaiting the elusive 16/16. > >Any estimate on how many 15's you might need >to find before the elusive 16/16 emerges? I'm hoping that it will take about 8 15/16 chains to find a 16/16, so maybe I'm 3/4 of the way there. The incessant power cuts here have driven me to write ever faster scripts that are easier to restart. My processing speed is now 8 times more than the last script I sent you, finding ~400,000 chains of 8/16 or longer in a 1 hour period. >I still have not understood why Phil does not sieve deeper >than thee (whose wheel still allows a factor as small as 73). >But then I am a self-confessed failure, at this too-hard puzzle. In my case it seems to be quicker to test the chain than it is to sieve out to any significant depth. Also I would lose the ability to use the same sieve against multiple (meaningful) 'b' values. I'm just going for testing the greatest amount of chains in the smallest possible time. Statistically this should produce the required result at some stage in the near future. Best Regards, Kevin. (who has just restarted after yet another power cut) djbroadhurst Dec 22, 2010 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > I'm just going for testing the greatest amount of chains in the > smallest possible time. Statistically this should produce the > required result at some stage in the near future. It's hard to argue with that :-) > I'm hoping that it will take about 8 15/16 chains to > find a 16/16, so maybe I'm 3/4 of the way there. Bon courage! David Kevin Acres Dec 22, 2010 ----------------------- Now we're cooking on gas, thanks to MPIR (http://www.mpir.org). 7th 15/16. At 04:17 PM 22/12/2010, Kevin Acres wrote: >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] >[18*x + 319862525, [25667359, 15]] >[18*x + 386886155, [57802093, 15]] [18*x + 94904545, [132628157, 15]] [1, 132628157, Mat([132628157, 1])] [2, 2482211371, Mat([2482211371, 1])] [3, 44774709223, Mat([44774709223, 1])] [4, 806039670559, Mat([806039670559, 1])] [5, 14508808974607, Mat([14508808974607, 1])] [6, 261158656447471, Mat([261158656447471, 1])] [7, 4700855910959023, Mat([4700855910959023, 1])] [8, 84615406492166959, Mat([84615406492166959, 1])] [9, 1523077316953909807, Mat([1523077316953909807, 1])] [10, 27415391705265281071, Mat([27415391705265281071, 1])] [11, 493477050694869963823, Mat([493477050694869963823, 1])] [12, 8882586912507754253359, Mat([8882586912507754253359, 1])] [13, 159886564425139671465007, Mat([159886564425139671465007, 1])] [14, 2877958159652514181274671, Mat([2877958159652514181274671, 1])] [15, 51803246873745255357848623, Mat([51803246873745255357848623, 1])] [16, 932458443727414596536179759, [631, 1; 6967, 1; 21122657, 1; 10041665939231, 1]] [17, 16784251987093462737746140207, [17, 1; 987308940417262513985067071, 1]] My main search has now comprehensively covered the range: 0 < b < 506306000 1 < x < 77087010 I'm presently searching the range: 0 < b < 100151254 77087010 < x < 511205010 I expect this to take another 40 hours or so. Regards, Kevin. Kevin Acres Dec 25, 2010 ----------------------- An 8th, but not overly impressive, 15/16. >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] >[18*x + 319862525, [25667359, 15]] >[18*x + 386886155, [57802093, 15]] >[18*x + 94904545, [132628157, 15]] [18*x + 102486395, [504312947, 15]] [1, 504312947, Mat([504312947, 1])] [2, 9180119441, Mat([9180119441, 1])] [3, 165344636333, Mat([165344636333, 1])] [4, 2976305940389, Mat([2976305940389, 1])] [5, 53573609413397, Mat([53573609413397, 1])] [6, 964325071927541, Mat([964325071927541, 1])] [7, 17357851397182133, Mat([17357851397182133, 1])] [8, 312441325251764789, Mat([312441325251764789, 1])] [9, 5623943854634252597, Mat([5623943854634252597, 1])] [10, 101230989383519033141, Mat([101230989383519033141, 1])] [11, 1822157808903445082933, Mat([1822157808903445082933, 1])] [12, 32798840560262113979189, Mat([32798840560262113979189, 1])] [13, 590379130084718154111797, Mat([590379130084718154111797, 1])] [14, 10626824341524926876498741, Mat([10626824341524926876498741, 1])] [15, 191282838147448683879463733, Mat([191282838147448683879463733, 1])] [16, 3443091086654076309932833589, [109, 1; 31587991620679599173695721, 1]] [17, 61975639559773373578893490997, [17, 1; 509, 1; 7162329776929778525239049, 1]] Kevin Acres Dec 25, 2010 ----------------------- A 9th 15/16. Was sort of hoping for a 16/16 by this stage. >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] >[18*x + 319862525, [25667359, 15]] >[18*x + 386886155, [57802093, 15]] >[18*x + 94904545, [132628157, 15]] >[18*x + 102486395, [504312947, 15]] [18*x + 129499855, [444809429, 15]] [1, 444809429, Mat([444809429, 1])] [2, 8136069577, Mat([8136069577, 1])] [3, 146578752241, Mat([146578752241, 1])] [4, 2638547040193, Mat([2638547040193, 1])] [5, 47493976223329, Mat([47493976223329, 1])] [6, 854891701519777, Mat([854891701519777, 1])] [7, 15388050756855841, Mat([15388050756855841, 1])] [8, 276984913752904993, Mat([276984913752904993, 1])] [9, 4985728447681789729, Mat([4985728447681789729, 1])] [10, 89743112058401714977, Mat([89743112058401714977, 1])] [11, 1615376017051360369441, Mat([1615376017051360369441, 1])] [12, 29076768306924616149793, Mat([29076768306924616149793, 1])] [13, 523381829524643220196129, Mat([523381829524643220196129, 1])] [14, 9420872931443578093030177, Mat([9420872931443578093030177, 1])] [15, 169575712765984405804043041, Mat([169575712765984405804043041, 1])] [16, 3052362829787719304602274593, [43, 1; 80048363, 1; 886778685131718377, 1]] [17, 54942530936178947482970442529, [17, 1; 3231913584481114557821790737, 1]] Kevin Acres Dec 29, 2010 ----------------------- 10th and 11th 15/16. Still no 16/16. >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] >[18*x + 319862525, [25667359, 15]] >[18*x + 386886155, [57802093, 15]] >[18*x + 94904545, [132628157, 15]] >[18*x + 102486395, [504312947, 15]] >[18*x + 129499855, [444809429, 15]] [18*x + 270803885, [91364431, 15]] [18*x + 438255215, [413617013, 15]] Kevin Acres Dec 29, 2010 ----------------------- And, of course, just as I was posting the last 2, a 12th came up. At 06:14 PM 30/12/2010, Kevin Acres wrote: >10th and 11th 15/16. Still no 16/16. > >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] >[18*x + 319862525, [25667359, 15]] >[18*x + 386886155, [57802093, 15]] >[18*x + 94904545, [132628157, 15]] >[18*x + 102486395, [504312947, 15]] >[18*x + 129499855, [444809429, 15]] >[18*x + 270803885, [91364431, 15]] >[18*x + 438255215, [413617013, 15]] [18*x+500677507, [482332909, 15]] Kevin Acres Jan 1, 2011 ----------------------- Another 4 15/16 chains, bringing the current total to 16. Still no sign of a 16/16, which I was hoping that I would have found by now. >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] >[18*x + 319862525, [25667359, 15]] >[18*x + 386886155, [57802093, 15]] >[18*x + 94904545, [132628157, 15]] >[18*x + 102486395, [504312947, 15]] >[18*x + 129499855, [444809429, 15]] >[18*x + 270803885, [91364431, 15]] >[18*x + 438255215, [413617013, 15]] >[18*x + 500677507, [482332909, 15]] [18*x + 466270385, [120478417, 15]] [18*x + 615660455, [65330743, 15]] [18*x + 645148609, [44282963, 15]] [18*x + 904033405, [60651301, 15]] Kevin Acres Jan 2, 2011 ----------------------- Am I missing something obvious or, after now having found 17 15/16 chains, should I reasonably be expecting a 16/16 some time soon? Kevin. >[18*x + 4143491, [1989217, 15]] >[18*x + 18192515, [1087, 15]] >[18*x - 54818687, [16723501, 15]] >[18*x + 76622095, [221831641, 15]] >[18*x + 319862525, [25667359, 15]] >[18*x + 386886155, [57802093, 15]] >[18*x + 94904545, [132628157, 15]] >[18*x + 102486395, [504312947, 15]] >[18*x + 129499855, [444809429, 15]] >[18*x + 270803885, [91364431, 15]] >[18*x + 438255215, [413617013, 15]] >[18*x + 500677507, [482332909, 15]] >[18*x + 466270385, [120478417, 15]] >[18*x + 615660455, [65330743, 15]] >[18*x + 645148609, [44282963, 15]] >[18*x + 904033405, [60651301, 15]] [18*x + 1031114975, [8466239, 15]] djbroadhurst Jan 2, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > after now having found 17 15/16 chains, should > I reasonably be expecting a 16/16 some time soon? Suppose that you guessed a 1/9 chance. Then the odds of /not/ getting a result after 17 tries are exp(-17/9) =~ 15% David Kevin Acres Jan 2, 2011 ----------------------- Hello David, At 09:43 AM 3/01/2011, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, Kevin Acres wrote: > > after now having found 17 15/16 chains, should > > I reasonably be expecting a 16/16 some time soon? > >Suppose that you guessed a 1/9 chance. Then the odds >of /not/ getting a result after 17 tries are >exp(-17/9) =~ 15% Thanks for that. It will give me some idea of what to hope for at least. Right now I'm trawling shallow waters again. This gives me faster processing and a greater 15/16 density. Over the next couple of days I'm going to take b up to just less than 2^31 with x < 51561510. I expect this to give an extra 6 or so 15/16 chains on top of the 18 I have now. The current state of my search is: 0 < b < 506306000, 0 < x < 511020510 -> completed 506306000 < b < 1000479680, 0 < x < 51561510 -> completed 1000479680 < b < 1600328930, 0 < x < 51561510 -> 50% complete (~17 hours to go) 1600328930 < b < 2147085140, 0 < x < 51561510 -> not yet started (~32 hours) For completeness, my 18th 15/16 is: [18*x + 1220760325, [38738527, 15]] Best Regards, Kevin. djbroadhurst Jan 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > I expect this to give an extra 6 or so 15/16 chains on > top of the 18 I have now. The bad news, of course, is that Poisson gives you no credit whatsoever for the 18 previous failures. Your chance of success with the next 6 is about 1 - exp(-6*mu) =~ 50% if we are are right about the mean probability mu =~ 1/9. Good luck! David Phil Carmody Jan 3, 2011 ----------------------- --- On Mon, 1/3/11, djbroadhurst wrote: > --- In primenumbers@yahoogroups.com, > Kevin Acres wrote: > > I expect this to give an extra 6 or so 15/16 chains on > > top of the 18 I have now. > > The bad news, of course, is that Poisson gives you > no credit whatsoever for the 18 previous failures. > Your chance of success with the next 6 is about > 1 - exp(-6*mu) =~ 50% > if we are are right about the mean probability > mu =~ 1/9. > > Good luck! You're being willed on from here in Estonia, too, Kevin! I always like to believe that the same kind of influence that sticks the e^-gamma term into prime density expressions is kind enough to violate the Poisson independence criterion too. Phil Kevin Acres Jan 3, 2011 ----------------------- Hello David, At 08:59 PM 3/01/2011, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >Kevin Acres wrote: > > > I expect this to give an extra 6 or so 15/16 chains on > > top of the 18 I have now. > >The bad news, of course, is that Poisson gives you >no credit whatsoever for the 18 previous failures. >Your chance of success with the next 6 is about >1 - exp(-6*mu) =~ 50% >if we are are right about the mean probability >mu =~ 1/9. In order to better quantify the task at hand, I have collected some stats from the last run. These are the length of chain, the number found and the ratio to the previous count. You'll see why I'm thinking of bringing in some liquid nitrogen to cool down the cpu when this search is finished :-) For the run: 1000479680 < b < 1600328930, 0 < x < 51561510 [1, 1570112112838] [2, 418525248095, 3.75] [3, 103246052869, 4.05] [4, 22330844048, 4.62] [5, 4266000180, 5.23] [6, 755973490, 5.64] [7, 121667493, 6.21] [8, 17851539, 6.82] [9, 2425736, 7.36] [10, 304523, 7.97] [11, 34659, 8.79] [12, 4027, 8.61] [13, 453, 8.89] [14, 46, 9.85] [15, 4, 11.5] [16, 0] Total chains tested = 2119378520000 in 122460 seconds = 17306700.31 chains per second Note that I guestimated the completion time at 34 hours. 122460 seconds puts me at 60 seconds over:-) The 15/16 count is now up to 20. The unreported 2 are: [18*x+1131343495, [47894701, 15]] [18*x+1470558067, [48291589, 15]] Best Regards, Kevin. djbroadhurst Jan 3, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > You'll see why I'm thinking of bringing in some liquid nitrogen > to cool down the cpu when this search is finished :-) Indeed. I hope you are not yet under water in OZ. > [14, 46, 9.85] > [15, 4, 11.5] 4 instances of 15/16 are too small to conclude much; how may 14's produced your 18+ cases of 15/16? David Kevin Acres Jan 3, 2011 ----------------------- Hello David, At 10:48 AM 4/01/2011, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >Kevin Acres wrote: > > > You'll see why I'm thinking of bringing in some liquid nitrogen > > to cool down the cpu when this search is finished :-) > >Indeed. I hope you are not yet under water in OZ. > > > [14, 46, 9.85] > > [15, 4, 11.5] > >4 instances of 15/16 are too small to conclude much; >how may 14's produced your 18+ cases of 15/16? No fear of being underwater here:-) Innumerable power cuts have somewhat destroyed meaningful end of run stats. The most recent outage was just a few minutes after my 34 hour run:-) A review of logs of 14+ chains gives me 17 15/16 amongst 226 14/16. Some of these are outside of my preferred x < 51561510 search area, where the yield of 15/16 becomes somewhat less. Best Regards, Kevin. djbroadhurst Jan 4, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > A review of logs of 14+ chains gives me 17 15/16 amongst 226 14/16. > Some of these are outside of my preferred x < 51561510 search area, > where the yield of 15/16 becomes somewhat less. Some way back, you reported using a wheel of size 510510 = 17# and you reported the factorization > [16, 3052362829787719304602274593, > [43, 1; 80048363, 1; 886778685131718377, 1]] In such a case, prod(p=2,17,1-isprime(p)/p)*log(3052362829787719304602274593) =~ 11.4 estimates the mean number of 15's that you might need for a 16. By my reckoning you now have about 23 runs of 15. The a priori probability of a 16th prime was about 1 - exp(-23/11.4) = 87% so it appears that you have been unlucky. David Kevin Acres Jan 4, 2011 ----------------------- Hello David, At 07:31 AM 20/11/2010, djbroadhurst wrote: >Please read the rules for the bounded case: >http://tech.groups.yahoo.com/group/primenumbers/message/22087 > > > Let A, B and L be integers with A > 1 and L > 1. > > > > Definition: A "Smith chain" of length L is a chain > > p[n+1] = A*p[n] + B, such that p[n] is prime, > > for n = 1 to L, with p[2] > p[1] > A. > > > Definition: A "maximal Smith chain" is a Smith chain with > > integers (A,B) for which there is a proof that no chain > > of greater length exists. Something like [18*x-448552937, [15788701, 15]] probably violates your search criteria. I just need to know if A < p[1] < p[2] can be stretched to A < abs(p[1]) < abs(p[2]) or is that outside of these rules? Best Regards, Kevin. (with 25 conforming 15/16s) djbroadhurst Jan 5, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > Something like [18*x-448552937, [15788701, 15]] probably violates > your search criteria. Negative primes not allowed, sorry. So this case p=-15788701;for(k=0,16,print([k,factor(p)]);p=18*p+448552937); [0, [-1, 1; 15788701, 1]] [1, Mat([164356319, 1])] [2, Mat([3406966679, 1])] [3, Mat([61773953159, 1])] [4, Mat([1112379709799, 1])] [5, Mat([20023283329319, 1])] [6, Mat([360419548480679, 1])] [7, Mat([6487552321205159, 1])] [8, Mat([116775942230245799, 1])] [9, Mat([2101966960592977319, 1])] [10, Mat([37835405291122144679, 1])] [11, Mat([681037295240647157159, 1])] [12, Mat([12258671314332097381799, 1])] [13, Mat([220656083657978201425319, 1])] [14, Mat([3971809505843608074208679, 1])] [15, [29, 1; 67, 1; 36794941381978870707313, 1]] [16, [17, 1; 653, 1; 115923455534936404338899, 1]] gives only 14 positive primes. David Kevin Acres Jan 5, 2011 ----------------------- Hello David, At 10:29 PM 5/01/2011, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, Kevin Acres > wrote: > > > Something like [18*x-448552937, [15788701, 15]] probably violates > > your search criteria. > >Negative primes not allowed, sorry. So this case In the end I didn't need the wiggle room. Only to modify my code to run sensibly with negative b, where, as I think you know, it is not as efficient as running with positive b. So, after ~30 15/16 chains I can now post: [18, -143835631, [44253593, 16]] [1, 44253593, Mat([44253593, 1])] [2, 652729043, Mat([652729043, 1])] [3, 11605287143, Mat([11605287143, 1])] [4, 208751332943, Mat([208751332943, 1])] [5, 3757380157343, Mat([3757380157343, 1])] [6, 67632698996543, Mat([67632698996543, 1])] [7, 1217388438102143, Mat([1217388438102143, 1])] [8, 21912991742002943, Mat([21912991742002943, 1])] [9, 394433851212217343, Mat([394433851212217343, 1])] [10, 7099809321676076543, Mat([7099809321676076543, 1])] [11, 127796567790025542143, Mat([127796567790025542143, 1])] [12, 2300338220220315922943, Mat([2300338220220315922943, 1])] [13, 41406087963965542777343, Mat([41406087963965542777343, 1])] [14, 745309583351379626156543, Mat([745309583351379626156543, 1])] [15, 13415572500324833126982143, Mat([13415572500324833126982143, 1])] [16, 241480305005846996141842943, Mat([241480305005846996141842943, 1])] [17, 4346645490105245930409337343, [17, 1; 29, 1; 2092457, 1; 4213575300261521443, 1]] This was found just 11 hours into a search with negative b. Best Regards, Kevin. djbroadhurst Jan 5, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > So, after ~30 15/16 chains I can now post: > > [18, -143835631, [44253593, 16]] > > [1, 44253593, Mat([44253593, 1])] > [2, 652729043, Mat([652729043, 1])] > [3, 11605287143, Mat([11605287143, 1])] > [4, 208751332943, Mat([208751332943, 1])] > [5, 3757380157343, Mat([3757380157343, 1])] > [6, 67632698996543, Mat([67632698996543, 1])] > [7, 1217388438102143, Mat([1217388438102143, 1])] > [8, 21912991742002943, Mat([21912991742002943, 1])] > [9, 394433851212217343, Mat([394433851212217343, 1])] > [10, 7099809321676076543, Mat([7099809321676076543, 1])] > [11, 127796567790025542143, Mat([127796567790025542143, 1])] > [12, 2300338220220315922943, Mat([2300338220220315922943, 1])] > [13, 41406087963965542777343, Mat([41406087963965542777343, 1])] > [14, 745309583351379626156543, Mat([745309583351379626156543, 1])] > [15, 13415572500324833126982143, Mat([13415572500324833126982143, 1])] > [16, 241480305005846996141842943, Mat([241480305005846996141842943, 1])] > [17, 4346645490105245930409337343, [17, 1; 29, 1; 2092457, 1; > 4213575300261521443, 1]] Many congratulations, from UK and Estonia! David Kevin Acres Jan 5, 2011 ----------------------- At 05:49 AM 6/01/2011, djbroadhurst wrote: >--- In primenumbers@yahoogroups.com, >Kevin Acres wrote: > > > So, after ~30 15/16 chains I can now post: > > > > [18, -143835631, [44253593, 16]] > >Many congratulations, from UK and Estonia! > >David Thank you David and Phil for the inspiration on this. With my code eventually churning out about 3 chains of 15 per day, the 16 had to turn up in the end. I'd say that Phil was spot on the money with his comments regarding 5 year old technology. Even running an Intel i7 at 3.9Ghz this was still a formidable task. Best Regards, Kevin. Kevin Acres Jan 5, 2011 ----------------------- At 05:42 AM 6/01/2011, Kevin Acres wrote: >At 10:29 PM 5/01/2011, djbroadhurst wrote: > > >Negative primes not allowed, sorry. So this case I'm running the current search to its end, just in case anything else turns up. This will cover 0 > b > -510510000, 0 < x < 12813810 and currently is at just over 50% complete. Meanwhile a prime example of a disallowable 16/16 :-) [18*x - 351626155, [607147, 16]] [1, 607147, Mat([607147, 1])] [2, -340697509, [-1, 1; 340697509, 1]] [3, -6484181317, [-1, 1; 6484181317, 1]] [4, -117066889861, [-1, 1; 117066889861, 1]] [5, -2107555643653, [-1, 1; 2107555643653, 1]] [6, -37936353211909, [-1, 1; 37936353211909, 1]] [7, -682854709440517, [-1, 1; 682854709440517, 1]] [8, -12291385121555461, [-1, 1; 12291385121555461, 1]] [9, -221244932539624453, [-1, 1; 221244932539624453, 1]] [10, -3982408786064866309, [-1, 1; 3982408786064866309, 1]] [11, -71683358149519219717, [-1, 1; 71683358149519219717, 1]] [12, -1290300446691697581061, [-1, 1; 1290300446691697581061, 1]] [13, -23225408040450908085253, [-1, 1; 23225408040450908085253, 1]] [14, -418057344728116697160709, [-1, 1; 418057344728116697160709, 1]] [15, -7525032205106100900518917, [-1, 1; 7525032205106100900518917, 1]] [16, -135450579691909816560966661, [-1, 1; 135450579691909816560966661, 1]] [17, -2438110434454376698449026053, [-1, 1; 17, 1; 701, 1; 201997, 1; 3278333, 1; 308950177409, 1]] Mark Jan 6, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > [snip] > > So, after ~30 15/16 chains I can now post: > > [18, -143835631, [44253593, 16]] > > [1, 44253593, Mat([44253593, 1])] > [2, 652729043, Mat([652729043, 1])] > [3, 11605287143, Mat([11605287143, 1])] > [4, 208751332943, Mat([208751332943, 1])] > [5, 3757380157343, Mat([3757380157343, 1])] > [6, 67632698996543, Mat([67632698996543, 1])] > [7, 1217388438102143, Mat([1217388438102143, 1])] > [8, 21912991742002943, Mat([21912991742002943, 1])] > [9, 394433851212217343, Mat([394433851212217343, 1])] > [10, 7099809321676076543, Mat([7099809321676076543, 1])] > [11, 127796567790025542143, Mat([127796567790025542143, 1])] > [12, 2300338220220315922943, Mat([2300338220220315922943, 1])] > [13, 41406087963965542777343, Mat([41406087963965542777343, 1])] > [14, 745309583351379626156543, Mat([745309583351379626156543, 1])] > [15, 13415572500324833126982143, Mat([13415572500324833126982143, 1])] > [16, 241480305005846996141842943, Mat([241480305005846996141842943, 1])] > [17, 4346645490105245930409337343, [17, 1; 29, 1; 2092457, 1; > 4213575300261521443, 1]] > Your persistence paid off with a great find, congratulations Kevin! And that all the primes except the first end in 43 is a nice touch. :) Kevin Acres Message 142 of 143 , Jan 6, 2011 ----------------------- Thanks Mark, At 04:26 PM 7/01/2011, Mark wrote: >--- In primenumbers@yahoogroups.com, Kevin Acres wrote: > > So, after ~30 15/16 chains I can now post: > > > > [18, -143835631, [44253593, 16]] > >Your persistence paid off with a great find, congratulations Kevin! >And that all the primes except the first end in 43 is a nice touch. :) The last search block was 47 hours and located 9 permissible 15/16 and 1 permissible 16/16. For the first time in weeks the cpu fan has slowed to a quiet speed and the core temperature has dropped back some 32 degrees Celsius. A very much related problem has caught my eye in determining how often the form x=a*x+b either is a square or has a square as a major factor. So I expect the cpu to be ramping up again soon :-) The astute may also cotton on to my next, possibly futile, quest. Best Regards, Kevin. djbroadhurst Message 143 of 143 , Jan 7, 2011 ----------------------- --- In primenumbers@yahoogroups.com, Kevin Acres wrote: > x=a*x+b either is a square or has a square as a major factor. Suppose that we want to start with a square and get a square. Then we must solve the Diophantine equation y^2 = a*x^2 + b For any pair (a,b), Dario will tell us all the solutions: http://www.alpertron.com.ar/QUAD.HTM David