vonstaudt

Von Staudt prime number: definition and computation.

Abstract. We introduce the von Staudt prime number thereby splitting the primes in the progression 12n − 1 (n>0) into two classes. Open questions are: Are there infinite many von Staudt primes? Are there more von Staudt primes or complementary von Staudt primes?

Let Bn denote the Bernoulli numbers. By a Bernoulli prime number I understand an integer n > 1 such that denominator(Bn−1) = 6n .
It is assumed that all rational numbers under consideration are reduced to lowest terms. The following list displays all Bernoulli prime numbers smaller then 1000.

Bernoulli Primes
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 239,
263, 347, 359, 383, 443, 467, 479, 503, 563,
587, 647, 659, 719, 827, 839, 863, 887, 983.

There are two numbers in this list which appear somewhat misplaced. Looking at the sequence modulo 6, the number 7 will not fit in. And the number 5 also looks strange here. It is the only split prime in the list, all other numbers are inert primes.

To get rid of these two primes on a conceptual base one might consider the divided Bernoulli numbers  βn = Bn / n (n > 0). These number appear for example in the Kummer congruencies. They are significant because βn is a p-integer for primes p where p − 1  does not divide n. The divided Bernoulli numbers were explored in depth by von Staudt (in an almost unknown 'second' paper, which for 100 years was kept as a kind of technical report intern to von Staudt's university at Erlangen.) This explains the name in the next definition.

An integer n > 1 is a von Staudt prime number if and only if denominator(Bn−1 / (n−1)) = 12n .
The following list displays all von Staudt prime numbers smaller than 1000.

Von Staudt Primes
11, 23, 47, 59, 83, 107, 167, 179, 227, 239,
263, 347, 359, 383, 443, 467, 479, 503, 563,
587, 647, 659, 719, 827, 839, 863, 887, 983.

Comparing the two lists we see that the 5 and the 7 are missing, as intended. By a complementary von Staudt prime number I understand a prime number in the arithmetic progression 12n − 1 which is not a von Staudt prime number. The first few of these prime numbers are:

Complementary Von Staudt Primes
71, 131, 191, 251, 311, 419, 431, 491, 599, 683,
743, 911, 947, 971, 1031, 1091, 1103, 1151,
1163, 1427, 1451, 1511, 1559, 1571, 1583.

Are there infinite many von Staudt primes? In any case there are, due to Dirichlet, infinite many prime numbers, which are either a von Staudt prime or a complementary von Staudt prime. At the On-Line Encyclopedia of Integer Sequences look for the sequences A092307 and A152951.

How to compute the von Staudt prime numbers.

To compute the von Staudt primes we can start from the definition. The following function, coded in Maple, returns a list of all von Staudt prime numbers ≤ n.

LesNombresPremiersDeStaudt := proc(n)
local k, L; L:=[];
for k from 2 to n do
  if 12*k = denom(bernoulli(k − 1)/(k − 1))
then L := [op(L),k]; fi
od; L end;

However, this approach is not efficient. Therefore we retrieve a theorem of von Staudt and Clausen from 1840. It shows among other things that the denominator of the Bernoulli number can be computed as explained by Clausen:

Der Bruch der n-ten Bernoullischen Zahl wird so gefunden: Man addire zu den Theilern von 2n ... 1, 2, a, a', a", ..., 2n die Einheit, wodurch man die Reihe Zahlen 2, 3, a + 1, a' + 1, ..., 2n+1 bekommt. Aus dieser nimmt man bloß die Primzahlen 2, 3, p, p' etc. und bildet den Bruch der n-ten Bernoullischen Zahl ... (as cited by R. Fritsch.)

An almost verbatim translation to the notation of Maple gives:

Clausen := proc(n) local S;
S := divisors(n);
S := map(i->i+1,S);
S := select(isprime,S);
S := S minus {2,3};
S = {n+1} end:

The von Staudt prime numbers can now be easily listed by applying this function.

VonStaudtPrimes :=
proc(n) local k,L; L:= [];
for k from 11 by 12 to n do
  if Clausen(k − 1) then L := [op(L),k] fi;
od; L end:

Similarly the complementary von Staudt prime number can be computed.

ComplementaryVonStaudtPrimes :=
proc(n) local k,L; L:= [];
for k from 11 by 12 to n do
  if isprime(k) then
     if not Clausen(k−1)
        then L := [op(L),k] fi fi;
od; L end:

The implementation VonStaudtPrimes is much faster than LesNombresPremiersDeStaudt. For example to compute the list on a vintage PC anno 2005 with n = 2000 the routine VonStaudtPrimes spend 0,05 seconds whereas the running time of LesNombresPremiers DeStaudt was more than a 2500fold of this.

Characterisations of the von Staudt prime number.

The above considerations amount to a criterion for the von Staudt prime numbers which is free from any reference to the Bernoulli numbers. We can rephrase it as:

 An integer n is a von Staudt prime number <=>
(a)  n is in the arithmetic progression 12n − 1, and
(b) {p is prime and (p − 1) divides (n − 1) } = {2, 3, n}.

Moreover, the von Staudt prime numbers can be understood as fix points of the function denom(Bn−1 / (n − 1)) / 12. Viewed this way and carried over to the language of generating functions this leads us to consider the expansion of h(x) = 12x(x + ln(exp(−x) − 1) − ln(x)).
Let [xn] S(h) denote the coefficient of xn in the series expansion of h. It follows for n > 1 denominator((n-1)! [xn] S(h)) = n  <=>  n is a von Staudt prime.

Let' s check this with Maple.

genFun := proc(n) local h,p,c,i;
h := x -> 12*x*(x+ln(exp(-x)-1)-ln(x));
p := series(h(x),x,n):
c := [seq([i,denom((i-1)!*coeff(p,x,i))],i=2..n)]:
select(i->(i[1]=i[2]),c); end:

Calling genFun(123) produces, as expected,
[[11,11], [23,23], [47,47], [59,59], [83,83], [107,107]].

The ratio von_Staudt / C_von_Staudt.

Are there more von Staudt primes or more complementary von Staudt primes?

RatioStaudtComplementaryStaudt :=
proc(n) local p,S,C; S:=0; C:=0;
for p from 10 by 12 to n do
  if isprime(p + 1) then if Clausen(p)
  then S := S + 1 else C := C + 1 fi fi;
od; [S,C,evalf(S/C)] end:

The table below shows the ratio of the number of von Staudt primes to the number of complementary von Staudt primes for some powers of 10.

100 -> 5/1 ~ 0,200
1000 -> 28/14 ~ 0,500
10000 -> 159/148 ~ 0,931
100000 -> 1133/1264 ~ 1,116
1000000 -> 8770/10884 ~ 1,241
10000000 -> 71419/94795 ~ 1,327

This shows that in the beginning the von Staudt primes dominate, however, later this relation turns around. Does the ratio converge to some finite value?

The relation von Staudt primes / safe primes.

Recall the definition of a safe prime: A safe prime is a prime number of the form (p-1)/2, where p is also a prime.

SafePrimes := proc(n)
select(isprime,[$1..iquo(n,2)]):
map(i->i+i+1,%):
select(isprime,%): end:

The call SafePrimes(1000) computes

5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359,
383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983

Safe primes which are not von Staudt primes are 5 and 7 and no others. Are there von Staudt primes which are no safe primes? Yes!

SeqDiff := proc(F,n,G,k)
sort(convert(convert(F(n),set) minus convert(G(k),set),list)) end:
SeqDiff(VonStaudtPrimes,N,SafePrimes,N);

This gives the following sequence of prime numbers which are not listed on OEIS. Do they deserve it? I hope so.

239, 443, 647, 659, 827, 1223, 1259, 1499, 1787, 1847, 2087,
2243, 2339, 2687, 2699, 3299, 3659, 3767, 4943, 5903