Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

1)
Message boards :
AP26  AP27 Search :
AP 27 Search
(Message 100288)
Posted 1793 days ago by Jarek
Regarding extending AP: The search program extends AP found back and forth, so the reported length is the maximal one. For example if the program reports AP25 found, we are sure this is not a part of an AP26.

2)
Message boards :
AP26  AP27 Search :
AP 27 Search
(Message 100287)
Posted 1793 days ago by Jarek
hi,
is there also a record kept for largest *consecutive* AP? for example3, 7, 11 is a Prime AP but not a consecutive one as there is a prime between 3 and 7. Of course, this would be much harder to look for...
River~~
Yes:
http://primerecords.dk/cpap.htm
However the problem of finding an example of the longest known CPAP is dead in my opinion: While CPAP10 is known, finding CPAP11 seems to be an impossible task for human race at the moment.

3)
Message boards :
AP26  AP27 Search :
AP26 Found!!!
(Message 22544)
Posted 4178 days ago by Jarek
There is a prediction in the AP26 search Thread, that says the chance a AP26 is part of a AP27 is 11% meaning up to 9 AP26 have to be found to get an AP27
To find the first AP26 it took 15 month, to find 9 AP26 would take 10+ years.
Unfortunately things are even worse than that. The problem is that expected time for each next AP26 would be longer and longer. The expected time for 10th AP26 could be 1020 as much as the expected time for the 1st one.
That's true, the 1st AP26 was overdue, we should have found 2 AP26 by now, but that doesn't influence much the order of magnitude of computations needed to expect AP27. Also AP27 search program could run a bit faster that AP26 search, but still, that doesn't influence the order of magnitude.
As for the above quoted 11% figure:
* this could be slightly optimistic like most ratios in my predictions
* even my predictions assumed search for AP26. As the search goes on, all the ratios grow, meaning that on average it would take more than 9 AP26 to honestly expect AP27.
Anyway, AP27 search should be ready to invest 1020 times the computer power than all the power used by the whole PrimeGrid up to now (approaching 2.8G cobblestones at the moment). As you know it is extremely hard to predict how long the actual search would take, but it is reasonable to assume that AP27 search would most likely consume something in the range 10G100G cobblestones.

4)
Message boards :
AP26  AP27 Search :
Improving the AP26 application
(Message 21365)
Posted 4228 days ago by Jarek
I do not know about limitations of various versions of PrimeQ. At the moment the largest primes tested are in 58 bits. With a given SHIFT and K all the primes tested are below MOD*(SHIFT+63)+K*23#*25.
SHIFT is safe up to 35584 which is sky high.
In my original AP26.h you can find lines:
n0=(N0*(K%17835)+((N0*17835)%MOD)*(K/17835)+N30)%MOD;
S31=(PRES2*(K%17835)+((PRES2*17835)%MOD)*(K/17835))%MOD;
S37=(PRES3*(K%17835)+((PRES3*17835)%MOD)*(K/17835))%MOD;
S41=(PRES4*(K%17835)+((PRES4*17835)%MOD)*(K/17835))%MOD;
S43=(PRES5*(K%17835)+((PRES5*17835)%MOD)*(K/17835))%MOD;
S47=(PRES6*(K%17835)+((PRES6*17835)%MOD)*(K/17835))%MOD;
S53=(PRES7*(K%17835)+((PRES7*17835)%MOD)*(K/17835))%MOD;
S59=(PRES8*(K%17835)+((PRES8*17835)%MOD)*(K/17835))%MOD;
where I partly guarded against modular multiplication overflow with a
dummy number 17835, which made program safe up to K=318,000,000.
In human readible form those lines should do
n0=(N0*K+N30)%MOD;
S31=(PRES2*K)%MOD;
etc...
but the above as is would very soon overflow 64bit integers.

5)
Message boards :
Number crunching :
fixed credit vs actual credit
(Message 20138)
Posted 4288 days ago by Jarek
The credit change was from 23.61 to 35.41 per WU, hence the difference is 11.80 per WU.
You are missing 106.20, which is exactly 9*11.80.
Therefore everything is OK under the assumption that you got 9 old WU's.

6)
Message boards :
Number crunching :
2010 Challenge Series suggestions
(Message 20068)
Posted 4291 days ago by Jarek
Is score 25 missing by accident or on purpose? (place 38/39)
Also place 73 appears twice.
Fixing those to follow a nice pattern makes points for 88 places.
You can reach 100 places by repeating each score 14 five times instead of twice.

7)
Message boards :
Number crunching :
2010 Challenge Series suggestions
(Message 20066)
Posted 4291 days ago by Jarek
16 44
17 43
18 44
19 43
After fixing the above, there would be points for 59 top places.

8)
Message boards :
AP26  AP27 Search :
Improving the AP26 application
(Message 19411)
Posted 4316 days ago by Jarek
With the same restriction on p as above, we can deal better with longer n by the direct formula
(p * ((INVp*(n1+1)+INVp2*n2) >> b)) >> (32b)
with
INVp2=Floor[Mod[2^(31b),p]*2^32/p]
n1 = lowest (31b) bits of n
n2 = highest (31b) bits of n
n can have (622b) bits.
Similarly:
(p * ((INVp*(n1+1)+INVp2*n2+INVp3*n3) >> b)) >> (32b)
with
INVp2=Floor[Mod[2^(31b),p]*2^32/p]
INVp3=Floor[Mod[2^(612b),p]*2^32/p]
n1 = lowest (31b) bits of n
n2 = next (30b) bits of n
n3 = highest (30b) bits of n
n can have (913b) bits.
Note that we must assure n1+n2+n3 < 2^(32b) or at least
n1+n2+n3 < (2^32)/p2^b.

9)
Message boards :
AP26  AP27 Search :
Improving the AP26 application
(Message 19410)
Posted 4316 days ago by Jarek
Here are my thoughts about finding remainder n%p with 32bit multiplication only, where n, p are unsigned integers with p being a small constant.
Assumption
p has at most b bits and is not a power of 2.
Case 1
n has at most 32b bits.
Precompute
INVp = Floor[(2^32)/p] = Floor[(2^321)/p]
Then n%p is given by
(p * ((INVp*(n+1)) >> b)) >> (32b)
Case 2
n has at most 623b bits
Take
n1 = n&((1<<(31b))1)
(lowest 31b bits of n)
n2 = n>>(31b)
(highest 312b bits of n)
m = n1 + n2 * Mod[2^(31b),p]
m has at most 32b bits, so m%p falls in case 1.
Case 3
n has at most 915b bits
Cut n into n1,n2,n3 having (31b), (302b), (302b) bits respectively
m = n1 + n2 * Mod[2^(31b),p] + n3 * Mod[2^(613b),p]
Case 4
n has at most 1207b bits
Cut n into n1,n2,n3,n4 having (30b), (302b), (302b), (302b) bits respectively
m = n1 + n2 * Mod[2^(30b),p] + n3 * Mod[2^(603b),p] + n4 * Mod[2^(905b),p]
EDIT: SORRY
I am afraid I haven't predicted all the rounding errors correctly. Will post a correction soon.
EDIT2: CORRECTION
In Case 1 we need
n <= (2^32)/p  2^b
We could try to fix it by making sure n is sufficiently smaller than 2^(32b), but it is much simpler if we just assume
p <= (2^32)/((2^(32b))+2^b)
that is:
b=6 p<=63
b=7 p<=127
b=8 p<=255
b=9 p<=511
b=10 p<=1023
b=11 p<=2046
b=12 p<=4080
b=13 p<=8065
b=14 p<=15420
b=15 p<=26214
b=16 p<=32768

10)
Message boards :
AP26  AP27 Search :
AP26 Search (20082010)
(Message 18910)
Posted 4339 days ago by Jarek
* progression difference is divisible by 29
* every 29 consecutive terms include exactly one term divisible by 29
For these conditions, you could substitute any number, correct? 29 just happens to be a number used by the search program in a way which makes AP29 "invisible" to it.
You can substitute any prime number in place of 29. And 29 is the smallest prime larger than the length of the progression we search.

Next 10 posts
