At fist glance Cullen or Woodall primes seem to be quite rare compared to Proth primes. Is it just because they are special cases of Proth primes? Or is the prime density actually lower?

If we say k <= n, then the amount of Proth numbers in range 0...n is n², correct? And we only have n Cullen or Woodall numbers in that range. So there would be square root amount of C/W primes compared to Proth primes?

For n,k < 100, there are 433 Proth primes, while there are only 10 Cullen and only 6 Woodall primes instead of 433^1/2 = 21. Is my reasoning wrong or is larger n required or is the density really much lower? If the latter, does anyone know why?

At fist glance Cullen or Woodall primes seem to be quite rare compared to Proth primes. Is it just because they are special cases of Proth primes? Or is the prime density actually lower?

If we say k <= n, then the amount of Proth numbers in range 0...n is n², correct?

For n, k < 100, there are 433 Proth primes, while there are only 10 Cullen and only 6 Woodall primes

Going further, we can use the Proth primes found by PrimeGrid and the previous searches.
Let n <= 1,500,000.
Proth: for 1 < k <= 9999 (4999 k's), 168901 primes were found.
The ratio is 33.8 primes/k. We can compute the mean weight in this range and we have weight = 2.002 (2 <=> random odd numbers).

In this range we have 14 Cullen primes and 30 Woodall primes.
We can estimate the weights with these numbers of primes:
Integrate(1/log(n * 2^n), n <= 1,500,000) ~ 19.9
Cullen weight ~ 14 / 19.9 = 0.7
Woodall weight ~ 30 / 19.9 = 1.5

We have a better estimate with the current limit: n <= 18M
16 Cullen primes and 34 Woodall primes.
Integrate(1/log(n * 2^n), n <= 18M) ~ 23.5
Cullen weight ~ 16 / 23.5 = 0.68
Woodall weight ~ 34 / 23.5 = 1.4

The formula indicated in Weight can also be applied to compute the number of expected primes.
With p_max = 10,000,000 and 10,000 n's, we have:
Estimated Cullen weight = 0.715
Estimated Woodall weight = 1.56
This means that the number of primes is related to the sieving process (many candidates are removed at this stage) and not to an unknown algebraic factorization.

Then the expected number of Proth primes for k < K and n < N is
K/2 * 2 * log_2(N) = K * log_2(N).
And the expected numbers of Cullen/Woodall primes are
Cullen: 0.7 * log_2(N)
Woodall: 1.5 * log_2(N)

I don't know if the divisibility properties of C/W_(p+1)/2 and C/W_(3p-1)/2 are sufficient to explain the values of the weight.

n²/2, right, thanks.

So the density is approximately 9%, 1%, 6% when looking at just 100 numbers. That doesn't say much either way, to be honest. I had to manually count the Proth primes, that's why I only checked up to n = 100.

Because of them there are few small Cullen primes. But for large n, the density may be close to the density of Proth primes.

If Proth numbers are sieved, they are similar to random odd numbers: 3 removes 1/3 of them, 5 1/5 of them, etc. This is no different with Cullen or Woodall numbers.

Mersenne, Thabit, Sierpinski, Riesel, Proth, Fermat, they are basically all the same (chosen for their relative ease to prove primality?), just with different restrictions about k and n and b. Do they all have the same prime density for large enough k, n, b?

Are there other types of primes that have, either proven or conjectured, a different prime density?

Or, more generally, are there other types of primes at all? I mean "are" in the sense of being studied.

If Proth numbers are sieved, they are similar to random odd numbers: 3 removes 1/3 of them, 5 1/5 of them, etc. This is no different with Cullen or Woodall numbers.

True--but the conditions for divisibility by different primes aren't independent. I would expect this to account for the different weights of the two sequences.

Mersenne, Thabit, Sierpinski, Riesel, Proth, Fermat, they are basically all the same (chosen for their relative ease to prove primality?), just with different restrictions about k and n and b. Do they all have the same prime density for large enough k, n, b? Are there other types of primes that have, either proven or conjectured, a different prime density?

Or, more generally, are there other types of primes at all? I mean "are" in the sense of being studied.

Ah, now I understand what you were saying!

weight = 2.002 (2 <=> random odd numbers).

In this range we have 14 Cullen primes and 30 Woodall primes.
We can estimate the weights with these numbers of primes:
Integrate(1/log(n * 2^n), n <= 1,500,000) ~ 19.9
Cullen weight ~ 14 / 19.9 = 0.7
Woodall weight ~ 30 / 19.9 = 1.5

Cullen: 0.7 * log_2(N)
Woodall: 1.5 * log_2(N)

I suppose Factorial, Primorial, and the WWWW projects. Also the Phi entries on top20 at T5K. Dunno what they're called.

This is not an assumption but the results of sieving. It seems that Cullen or Woodall numbers are very different from Proth numbers with fixed k. Any odd prime p removes 1/p of them.

The weight is low (< 2) but this is not because of a particular set of primes but because of some relations like if (2/p) = -1 then p | C_{(p + 1)/2} and if (2/p) = +1 then p | C_{(3p - 1)/2}.

But as Ravi has pointed out, the next question is the dependency for divisibility by different primes.

Surprisingly they may be independent: with the pair
- (3, 5) the ratio is 1/3 + 1/5 - 1/15
- (3, 7) the ratio is 1/3 + 1/7 - 1/21
- (5, 7) the ratio is 1/5 + 1/7 - 1/35
- ...???

weight = 2.002 (2 <=> random odd numbers).

That means the weight of a series of random odd numbers is 2? So Proth numbers behave no different then any random odd number when it comes to producing primes?

In this range we have 14 Cullen primes and 30 Woodall primes.
We can estimate the weights with these numbers of primes:
Integrate(1/log(n * 2^n), n <= 1,500,000) ~ 19.9
Cullen weight ~ 14 / 19.9 = 0.7
Woodall weight ~ 30 / 19.9 = 1.5

What is the 19.9? The amount of primes expected to be found in a random sequence that size? So the weight tells how close we are to the expected number? Odd numbers have weight=2 since they are twice as likely to produce a prime than odd+even numbers?

Cullen: 0.7 * log_2(N)
Woodall: 1.5 * log_2(N)

What does that mean? Woodall numbers are twice as likely to be prime than Cullen?

But why have Proth numbers k * log_2(N)?

I suppose Factorial, Primorial, and the WWWW projects. Also the Phi entries on top20 at T5K. Dunno what they're called.

What is WWWW, I couldn't find anything for some reason

I never heard of Mill's primes before, fascinating as well. :) Wouldn't that make a nice subproject? It could produce a lot of large primes. On the other hand that sounds too easy, so there's probably a catch? Is the exact value of A not known and the deviation becomes too large for large n? Or is it too difficult to test for primality of these numbers?

A few more of these:

If p is odd, then p | C_{p-1}.
If p is 1 mod 4 and 2 is a fourth power mod p, then p | C_{(9p-1)/4}.
If p is 1 mod 4 and 2 is a square but not a fourth power mod p, then p | C_{(7p+1)/4}.

You may have done this already, but it might be worthwhile to recalculate the weight with p_max << n_max, to see how much the weight is affected by primes on the order of n.

The problem is that it's a bit artificial because you have to compute the primes first and then some digits of A.

The problem is that it's a bit artificial because you have to compute the primes first and then some digits of A.

I was under the impression that if the Riemann hypothesis is true, then A can be calculated? Or does that just mean, then primes can be used to calculate A?

Is there a chance we will ever be able to calculate A indenpently? To me it feels like, if mathematicians fully understand why A^3^n produces only primes, we should be able to determine A's exact value. Like it is possible to calculate digits of Pi without feeding experimentally determined pairs of C, r into Pi = C/2r.