cp's OEIS Frontend

The prime constant (A051006) is essentially a set of flags that tell us whether a given integer is prime. But since all even numbers (except 2) are composite, every other bit is guaranteed to be 0.

Depending on the algorithm for which this is used, it may be more efficient to store a set of flags for just the odd numbers (and handle 2 as a special case). Lehmer (1969) suggests using about 64 kilobytes for the storage of this "characteristic number."

The fact that a(k(n)) is predominantly negative exhibits the Chebyshev Bias (where the congruences that are not quadratic residues generally lead in the prime number races, at least for "small" integers, over the congruences that are quadratic residues).

This bias seems caused (among other causes?) by the presence of all those squares (even powers) coprime to 4 taking away opportunities for primes to appear in the quadratic residue class +1 (mod 4), while the non-quadratic residue class -1 (mod 4) is squarefree.

The density of squares congruent to +1 (mod 4) is 1/(4*sqrt(k(n))) since 1/2 of squares are congruent to +1 (mod 4), while the density of primes in either residue class -1 or +1 (mod 4) is 1/(phi(4)*log(k(n))), with phi(4) = 2.

Here 1 is quadratic residue mod 4, but 3 (or equivalently -1) is quadratic non-residue mod 4. All the even powers (included in the squares) map congruences {-1, +1} to {+1, +1} respectively and so contribute to the bias, whereas all the odd powers map {-1, +1} to {-1, +1} respectively and so do not contribute to the bias.

One would then expect the ratio of this bias, if caused exclusively by the even powers, relative to the number of primes in either congruences to asymptotically tend towards to 0 as k(n) increases (since 1/(4*sqrt(k(n))) is o(1/(phi(4)*log(k(n))))).

The persistence or not of such bias in absolute value then does not contradict The Prime Number Theorem for Arithmetic Progressions (Dirichlet) which states that the asymptotic (relative) ratio of the count of prime numbers in each congruence class coprime to m tends to 1 in the limit towards infinity. (Cf. 'Prime Number Races' link below.)

Also, even if this bias grows in absolute value, it is expected to be drowned out (albeit very slowly) by the increasing fluctuations in the number of primes in each congruence class coprime to 4 since, assuming the truth of the Riemann Hypothesis, their maximum amplitude would be, with x standing for k(n) in our case, h(x) = O(sqrt(x)*log(x)) <= C*sqrt(x)*log(x) in absolute value which gives relative fluctuations of order h(x)/x = O(log(x)/sqrt(x)) <= C*log(x)/sqrt(x) in the densities of primes pi(x, {4, 1})/x and pi(x, {4, 3})/x in either congruence class.

Since 1/(4*sqrt(x)) is o(log(x)/sqrt(x)) the bias will eventually be overwhelmed by the "pink noise or nearly 1/f noise" corresponding to the fluctuations in the prime densities in either congruence class. The falsehood of the Riemann Hypothesis would imply even greater fluctuations since the RH corresponds to the minimal h(x).

We get pink noise or nearly 1/f noise if we consider the prime density fluctuations of pi(x, {4, k})/x as an amplitude spectrum over x (with a power density spectrum of (C*log(x)/sqrt(x))^2 = ((C*log(x))^2)/x and see x as the frequency f. This power density spectrum is then nearly 1/x and would have nearly equal energy (although slowly increasing as (C*log(x))^2) for each octave of x. (Cf. 'Prime Numbers: A Computational Perspective' link below.)

Among the positive integers k(n) up to 100000 that are congruent to -1 or +1 (mod 4) [indexed from n = 1 to 49999, with k(n) = 4*ceiling(n/2) + (-1)^n], a tie is attained or maintained, with a(k(n)) = 0, for only 34 integers and that bias favoring the non-quadratic residue class -1 (mod 4) gets violated only once, i.e., a(k(n)) = +1, for index n = 13430 (corresponding to the prime k(n) = 26861 congruent to +1 (mod 4) since n is even) where the congruence +1 leads once!

Previous name was: Starting with n+(n-1) go on adding n-2, then n-3, etc. until one gets a prime; a(n) = smallest prime in n+(n-1)+(n-2)+...+(n-i) (with the least i that gives a prime), or 0 if no such prime exists.

From Antti Karttunen, Jun 15 2018: (Start)

Number of terms of A005097 that divide n.

For all n >= 1, a(n) > A156660(n). Specifically, a(p) = 2 for all p in A005384 (Sophie Germain primes), although 2's occur in other positions as well.

(End)

Expression for k(n): k(n) = 4*ceiling(n/2) + (-1)^n, so the parity of n gives us the congruence (mod 4) of k(n). - Daniel Forgues, Mar 01 2009

The fact that a(k(n)) is predominantly negative exhibits the Chebyshev Bias (where the congruences that are not quadratic residues generally lead in the prime number races, at least for "small" integers, over the congruences that are quadratic residues).

This bias seems caused (among other causes?) by the presence of all those squares (even powers) coprime to 6 taking away opportunities for primes to appear in the quadratic residue class +1 (mod 6), while the non-quadratic residue class -1 (mod 6) is squarefree.

The density of squares congruent to +1 (mod 6) is 1/(6*sqrt(k(n))) since 1/3 of the squares are congruent to +1 (mod 6), while the density of primes in either residue classes -1 or +1 (mod 6) is 1/(phi(6)*log(k(n))), with phi(6) = 2.

Here 1 is a quadratic residue mod 6, but 5 (or equivalently -1) is a quadratic non-residue mod 6. All the even powers (included in the squares) map congruences {-1, +1} to {+1, +1} respectively and so contribute to the bias, whereas all the odd powers map {-1, +1} to {-1, +1} respectively and so do not contribute to the bias.

One would then expect the ratio of this bias, if caused exclusively by the even powers, relative to the number of primes in either congruences to asymptotically tend towards to 0 as k(n) increases (since 1/(6*sqrt(k(n))) is o(1/(phi(6)*log(k(n))))).

The persistence or not of such bias in absolute value then does not contradict The Prime Number Theorem for Arithmetic Progressions (Dirichlet) which states that the asymptotic (relative) ratio of the count of prime numbers in each congruence class coprime to m tends to 1 in the limit towards infinity. (Cf. 'Prime Number Races' link below.)

Also, even if this bias grows in absolute value, it is expected to be drowned out (albeit very slowly) by the increasing fluctuations in the number of primes in each congruence class coprime to 6 since, assuming the truth of the Riemann Hypothesis, their maximum amplitude would be, with x standing for k(n) in our case, h(x) = O(sqrt(x)*log(x)) <= C*sqrt(x)*log(x) in absolute value which gives relative fluctuations of order h(x)/x = O(log(x)/sqrt(x)) <= C*log(x)/sqrt(x) in the densities of primes pi(x, {6, 1})/x and pi(x, {6, 5})/x in either congruence class.

Since 1/(6*sqrt(x)) is o(log(x)/sqrt(x)) the bias will eventually be overwhelmed by the "pink noise or nearly 1/f noise" corresponding to the fluctuations in the prime densities in either congruence class. The falsehood of the Riemann Hypothesis would imply even greater fluctuations since the RH corresponds to the minimal h(x).

We get pink noise or nearly 1/f noise if we consider the prime density fluctuations of pi(x, {6, k})/x as an amplitude spectrum over x (with a power density spectrum of (C*log(x)/sqrt(x))^2 = ((C*log(x))^2)/x and see x as the frequency f. This power density spectrum is then nearly 1/x and would have nearly equal energy (although slowly increasing as (C*log(x))^2) for each octave of x. (Cf. 'Prime Numbers: A Computational Perspective' link below.)

Among the positive integers k(n) up to 100000 that are congruent to -1 or +1 (mod 6) [indexed from n = 1 to 33332, with k(n) = 6 ceiling(n/2) + (-1)^n], a tie, where a(k(n)) = 0, is attained or maintained for only 9 integers, and that bias favoring the non-quadratic residue class -1 (mod 6) never gets violated, i.e., a(k(n)) is never +1.

Number of ways to represent 2*n as the sum of two distinct noncomposite numbers. - Omar E. Pol, Dec 11 2024

Number of terms of A005097 which are less than n that divide n.

If we drop a(0), for all numbers k(n) [k(n) = 4*ceiling(n/2) + (-1)^n] congruent to -1 or +1 (mod 4) starting with k(n) = {3,5,7,9,11,...}, a(k(n)) is the number of primes up to a(k(n)). - Daniel Forgues, Mar 01 2009

For n > 0, equals 1 (to account for the even prime 2 which is not congruent to -1 or +1 (mod 4)) + partial sums of A101264 (for n > 0). - Daniel Forgues, Mar 01 2009