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
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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Enoch Haga, Jan 26 2002
EXTENSIONS
Edited by Dean Hickerson, Jun 08 2002
STATUS
approved