## Re: 2 > exp(Euler)

Expand Messages
• ... 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

> 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 2 of 22 , Sep 25, 2009
>
> 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 3 of 22 , Sep 25, 2009
"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 4 of 22 , Sep 25, 2009
>
> 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 5 of 22 , Sep 26, 2009
>
> 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 6 of 22 , Sep 26, 2009
"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 7 of 22 , Sep 26, 2009
>
> 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 8 of 22 , Sep 26, 2009