A066883 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give

A066883

Number of primes in the interval [p(n), p(n)^2] minus p(n), where p(n) is the n-th prime.

0, 0, 2, 5, 15, 21, 38, 46, 68, 108, 121, 171, 210, 227, 268, 341, 412, 441, 524, 585, 612, 711, 781, 888, 1042, 1126, 1165, 1247, 1286, 1381, 1720, 1814, 1972, 2018, 2306, 2361, 2536, 2715, 2838, 3029, 3217, 3290, 3635, 3709, 3848, 3920, 4370, 4836

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

Haga's conjecture (see link below) is that if the integers from 1 to p^2 (p prime) are put in a p by p square in standard order, then there's a transversal consisting of primes; i.e., a set of p primes containing exactly one number in each row and column. E.g., for p=5 the primes 5, 7, 11, 19, 23 work. Since p is needed for the p-th column, primes less than p can't be used. a(n) is the number of primes available minus the number needed for the transversal.

REFERENCES

Paulo Ribenboim, The New Book of Prime Number Records, 3rd ed., 1995, Springer, pp. 397-398

LINKS

Harry J. Smith, Table of n, a(n) for n = 1..1000

Carlos Rivera, The prime puzzles & problems connection, conjecture 26

FORMULA

a(n) = A054272(n)-A000040(n).

MATHEMATICA

a[n_] := PrimePi[(p=Prime[n])^2]-PrimePi[p-1]-p

PROG

(BASIC) 20 for Y=1 to 140 30 A=nxtprm(A):B=A^2 40 for X=A to B 50 if X=prmdiv(X) then C=C+1 60 next X 70 print A; C; C-A; "-"; 80 C=0 90 next Y

(PARI) { for (n=1, 1000, a=primepi((p=prime(n))^2) - primepi(p - 1) - p; write("b066883.txt", n, " ", a) ) } \\ Harry J. Smith, Apr 04 2010