login
Number of 1 <= i < n such that i*n+1 is prime.
1

%I #16 May 17 2021 18:17:56

%S 0,1,1,2,1,4,2,2,3,5,3,6,4,5,5,5,3,10,2,6,6,9,4,9,5,9,7,11,4,17,3,10,

%T 9,12,9,15,4,9,11,13,5,21,7,11,10,16,8,19,6,18,13,17,5,23,10,18,9,16,

%U 8,27,7,15,13,16,13,29,9,18,13,27,9,26,10,19,18,17,11,29,11,23,18,22,11,32

%N Number of 1 <= i < n such that i*n+1 is prime.

%C Number of primes p < n^2 such that p == 1 (mod n). The standard conjecture here is that a(n) ~ n^2/(2 phi(n)log n), where Euler's totient function phi(n) = A000010(n). - _Thomas Ordowski_, Oct 21 2014

%C Number of primes appearing in the 1st column of an n X n square array whose elements are the numbers from 1..n^2, listed in increasing order by rows. - _Wesley Ivan Hurt_, May 17 2021

%F a(n) = Sum_{k=1..n} pi(1+n*(k-1)) - pi(n*(k-1)), where pi is the prime counting function. - _Wesley Ivan Hurt_, May 17 2021

%e For n=10, i=1,3,4,6,7 give primes, so a(10)=5.

%t f[n_] := Length[ Select[ Range[n - 1], PrimeQ[n# + 1] & ]]; Table[ f[n], {n, 1, 85}]

%t Table[Count[Range[n-1]n+1,_?PrimeQ],{n,90}] (* _Harvey P. Dale_, Oct 10 2013 *)

%o (PARI) nphi(n)=local(c); c=0; for (i=1,n-1,if (isprime(i*n+1),c++)); c for(i=1,60,print1(","nphi(i)))

%Y Cf. A000010 (phi), A000720 (pi).

%K nonn

%O 1,4

%A _Jon Perry_, Jul 28 2003

%E Extended by _Robert G. Wilson v_, Jul 31 2003