## Other

drummers-lowrise

Message boards : Proth Prime Search : All ks have the same prime density?

Author Message
Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 4,081

Message 140914 - Posted: 20 Jun 2020 | 5:49:58 UTC

Would even the SoB candidates converge to a similar efficiency as any other k in the end?

Yes, this is a conjecture. Today no statistical deviation was found to disprove it.

In another thread about Sierpinski numbers it seemed to me, that some of the ks are indeed assumed to take much longer until they produce a prime:

the weight of a multiplier k, after adjusting for algebraic factorizations, is empirically a good predictor of how frequently that k produces primes.

Doesn't that mean that for a given range n some k produce less primes?

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 144
ID: 1108183
Credit: 8,505,009
RAC: 158

Message 140915 - Posted: 20 Jun 2020 | 6:18:43 UTC

Yes, some k's produce fewer primes than others. (At least empirically. Basically nothing has been proven about how many primes any given k produces, except in some cases when the answer is 0.) But this discrepancy appears to be well-explained in all cases by how many candidates are sieved out (by small prime factors or algebraic factorizations). So the density of primes *among candidates that remain after sieving* doesn't seem to depend on k in the long run.

A simple, made-up example: Let's say you're testing two k's, "k1" and "k2", for primes up to n=1M. Let's say k1 has a low weight, like SoB k's, and k2 has a high weight. Then you may find that after sieving, you're left with 3000 candidates for k1 and 30000 candidates for k2, out of 1000000 each. When you run all the primality tests, it turns out that k1 produces 5 primes and k2 produces 50. So the higher-weight k, k2, produced more primes. But it didn't produce primes more "efficiently", because in order to find 10 times more primes, you needed to run 10 times more LLR tests. What Yves was saying in your first quote is that we don't expect any k to produce more or fewer primes per LLR test than any other k.

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 4,081

Message 141519 - Posted: 8 Jul 2020 | 16:36:07 UTC - in response to Message 140915.

Ok, so the k's have different prime density but since the ones with lower density also produce less candidates, it evens out?

JeppeSN

Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 2,050

Message 141524 - Posted: 8 Jul 2020 | 17:15:14 UTC - in response to Message 141519.

Ok, so the k's have different prime density but since the ones with lower density also produce less candidates, it evens out?

Exactly. /JeppeSN

Message boards : Proth Prime Search : All ks have the same prime density?