Browse Groups

• ... Hans Riesel discusses this on pp 66-67 of his book, following Theorem 3.1. He asserts that http://tinyurl.com/y9whej4 ... by a factor 2/exp(Euler) =~
Message 1 of 22 , Sep 24, 2009
View Source

> This reminds me of an old chestnut:
> should one replace the Mertens constant
> exp(Euler) =~ 1.78107
> by 2, in this case, where N >> p >> 1.

Hans Riesel discusses this on pp 66-67 of his book,
following Theorem 3.1. He asserts that

http://tinyurl.com/y9whej4

> the sieve of Eratosthenes sieves out numbers
> more efficiently than does a "random" sieve

by a factor 2/exp(Euler) =~ 1.123.

It appears that, as we approach p = sqrt(N), divisibility by
primes is not statistically independent. However this is not
explained further. It is merely inferred from comparing
Mertens' theorem with the PNT.

No wonder Tschebycheff was worried...

David
• ... That s a nice follow-on, to consider primN(x,y,n). You have looked at my Case (5). I have devoted a couple of cpu days to investigating Case (2). For
Message 1 of 22 , Sep 25, 2009
View Source
>
> Here are a couple of gigantic PRPs:
>
> (101^5329+35^5329-lucasV(135,3535,5329))/
> (101^73+35^73-lucasV(135,3535,73)) is Fermat and Lucas PRP!
>
> (106^7921+35^7921-lucasV(140,3710,7921))/
> (106^89+35^89-lucasV(140,3710,89)) is Fermat and Lucas PRP!
>
> with 10535 and 15863 digits.
>
> I chose the composite index n = q^2 to be the
> square of a prime so as to have only two divisors
> of n in the Moebius transformation. For semiprime
> n = q*r, there would be three:
> primN(x,y,q*r) = N(x,y,q*r)/(N(x,y,q)*N(x,y,r))

That's a nice follow-on, to consider primN(x,y,n).

You have looked at my Case (5).
I have devoted a couple of cpu days to investigating Case (2).

For semiprime n, I have found several gigantic PRPs, for example:
lucasV(1,-1,421*263)/(lucasV(1,-1,421)*lucasV(1,-1,263)),
which is the same as L(421*263)/(L(421)*L(263)),
with 22997 digits, and
lucasV(1,-4,269*109)/(lucasV(1,-4,269)*lucasV(1,-4,109)) with 11824 digits.

For n=q^2 the search space is more restricted, and I have been unable to find a gigantic PRP. The largest I can find is
lucasV(1,-480^2,37^2)/lucasV(1,-480^2,37)
with 3574 digits.

Mike
• ... That was found by Bouk, 5 years ago: http://tinyurl.com/y9jos2d Please take care not to duplicate it, chez Henri. These are known PRPs that are gigantic
Message 1 of 22 , Sep 25, 2009
View Source
"mikeoakes2" <mikeoakes2@...> wrote:

> lucasV(1,-1,421*263)/(lucasV(1,-1,421)*lucasV(1,-1,263))

That was found by Bouk, 5 years ago:
http://tinyurl.com/y9jos2d

Please take care not to duplicate it, chez Henri.

These are known PRPs that are
gigantic Lucas primitive parts
with odd semi-prime indices:

[ p*q [p , q] digits of primV(1,-1,p*q)]

[ 83481, [3, 27827], 11631]
[110723, [263, 421], 22997] \\ your rediscovery
[138989, [23, 6043], 27780]
[154281, [3, 51427], 21495]
[177247, [7, 25321], 31750]
[180309, [3, 60103], 25121]
[184971, [3, 61657], 25771]
[218341, [29, 7529], 44052]
[220567, [367, 601], 45894]

The biggest was found by Michael Porter in 2007.

David
• ... Success at last: lucasV(1,-470^2,109^2)/lucasV(1,-470^2,109) has 31463 digits, and has been submitted to Henri s repository. Mike
Message 1 of 22 , Sep 25, 2009
View Source
>
> For n=q^2 the search space is more restricted, and I have been
> unable to find a gigantic PRP.

Success at last:
lucasV(1,-470^2,109^2)/lucasV(1,-470^2,109) has 31463 digits,
and has been submitted to Henri's repository.

Mike
• ... There was one remaining inaccuracy here: I only gave the sieving depth to a rounded value of 50 billion. I have just done another NewPGen sieve and
Message 1 of 22 , Sep 26, 2009
View Source
>
> You were within 2 sigma of theory:
>
> \p6
> pr109=1;forprime(q=2,109,pr109*=q);km=2*10^9;p=5*10^10;
> tried=393614016;found=140719122;hitrate=1.*found/tried;
> theory=exp(Euler)*log(p)*intnum(k=1,km,1/log(k*pr109))/km;
> test=hitrate/theory;sigm=(test-1)*sqrt(found);
> print([hitrate,theory,test,sigm])
>
> [0.357505, 0.357450, 1.00015, 1.82364]
>
> The fidelity with theory is now wonderful.
>
> Your AP15 project measured exp(Euler) to better
> than 2 parts in 10^4, in 3 GHz-days.

There was one remaining inaccuracy here: I only gave the sieving depth to a rounded value of 50 billion.

I have just done another NewPGen sieve and recorded the exact depth. After pfgw'ing (combined processing time < 1 GHz-day), the figures are very satisfactory, as sigma is down from 1.82 to 1.53:-

\p6
pr83=1;forprime(q=2,83,pr83*=q);km=2*10^9;p=50066810303;
tried=370597641;found=171068264;hitrate=1.*found/tried;
theory=exp(Euler)*log(p)*intnum(k=1,km,1/log(k*pr83))/km;
test=hitrate/theory;sigm=(test-1)*sqrt(found);
print([hitrate,theory,test,sigm])

[0.461601, 0.461547, 1.00012, 1.52844]

Mike
• ... Great stuff, Mike. There is a corollary: both NewPgen and OpenPFGW must have been behaving near perfectly to give such wondrous agreement with Mertens,
Message 1 of 22 , Sep 26, 2009
View Source
"mikeoakes2" <mikeoakes2@...> wrote:

> [0.461601, 0.461547, 1.00012, 1.52844]

Great stuff, Mike.

There is a corollary: both NewPgen and OpenPFGW
must have been behaving near perfectly to give
such wondrous agreement with Mertens, nicht wahr?

PS: How long will Pascal take for the AP16 :-?

David
• ... Dang.., I hoped no-one (at least not one of my APn competitors:-) would spot what that NewPGen run was for; but you of course got it in one. On an Intel
Message 1 of 22 , Sep 26, 2009
View Source
>
> PS: How long will Pascal take for the AP16 :-?

Dang.., I hoped no-one (at least not one of my APn competitors:-) would spot what that NewPGen run was for; but you of course got it in one.

On an Intel Quad at 3.6Ghz, about 4 months elapsed if I'm lucky, twice that if not.

(Current status: after 10 elapsed hours, it has found 7 AP13's.)

Mike
• ... Oh what a tangled web remains, When author candidly explains! David, pace Marmion http://www.quotationspage.com/quote/27150.html
Message 1 of 22 , Sep 26, 2009
View Source
"mikeoakes2" <mikeoakes2@...> wrote:

> Dang.., I hoped no-one
> (at least not one of my APn competitors:-)
> would spot what that NewPGen run was for;
> but you of course got it in one.

Oh what a tangled web remains,
When author candidly explains!

David, pace Marmion
http://www.quotationspage.com/quote/27150.html
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.