login
Number of primes in the interval [prime(n), prime(n)^2].
16

%I #43 Apr 03 2016 10:41:22

%S 2,3,7,12,26,34,55,65,91,137,152,208,251,270,315,394,471,502,591,656,

%T 685,790,864,977,1139,1227,1268,1354,1395,1494,1847,1945,2109,2157,

%U 2455,2512,2693,2878,3005,3202,3396,3471,3826,3902,4045,4119,4581,5059

%N Number of primes in the interval [prime(n), prime(n)^2].

%C These primes are candidates for fortunate numbers (A005235).

%C These are precisely the primes available for the solution of Aguilar's conjecture or Haga's conjecture in Carlos Rivera's The Prime Puzzles and Problems Connection, (conjecture 26). Aguilar's conjecture states that at least one prime will be available for placement on each row and column of a p X p square array. Haga's conjecture states that just p primes are required for such placement in any p X p array. - _Enoch Haga_, Jan 23 2002

%C Also number of times p_n (the n-th prime) occurs as the least prime factor (A020639) among numbers in range [(p_n)+1, ((p_n)^3)-1]. For n=1, p_1 = 2 and there are two even numbers in range [3, 7], namely 4 and 6, so a(1) = 2. See also A250474. - _Antti Karttunen_, Dec 05 2014

%C The number of consecutive primes after the leading 1 in the prime(n)-rough numbers. - _Benedict W. J. Irwin_, Mar 24 2016

%H Antti Karttunen, <a href="/A054272/b054272.txt">Table of n, a(n) for n = 1..5000</a>

%H Carlos Rivera, <a href="http://www.primepuzzles.net/conjectures/conj_026.htm">Conjecture 26. The Calendar-like square Conjecture</a>, The Prime Puzzles and Problems Connection.

%F a(n) = A000879(n) - n + 1.

%F From _Antti Karttunen_, Dec 05-08 2014: (Start)

%F a(n) = A250473(n) - 1 = A250474(n) - 2.

%F a(n) = sum_{d | A002110(n)} moebius(d) * floor((p_n)^2 / d). [Where p_n is the n-th prime (A000040(n)) and A002110(n) gives the product of the first n primes. Because the latter is always squarefree, one could also use Liouville's lambda (A008836) instead of Moebius mu (A008683).]

%F The ratio (a(n) * A002110(n)) / (A001248(n) * A005867(n)) stays near 1, which follows from the above summation formula. See also A249747.

%F (End)

%e n=4, the zone in question is [7,49] and encloses a(4)=12 primes, as follows: {7,11,13,17,19,23,29,31,37,41,43,47}.

%t a[n_] := PrimePi[Prime[n]^2] - n + 1; Array[a, 50] (* _Jean-François Alcover_, Dec 07 2015 *)

%o (PARI)

%o \\ A fast version:

%o default(primelimit, 2^31 + 2^30);

%o A054272(n) = 1 + primepi(prime(n)^2) - n;

%o for(n=1, 5000, write("b054272.txt", n, " ", A054272(n)));

%o \\ The following mirrors the given new formula. It is far from an optimal way to compute this sequence:

%o allocatemem(234567890);

%o A002110(n) = prod(i=1, n, prime(i));

%o A054272(n) = { my(p2); p2 = prime(n)^2; sumdiv(A002110(n), d, moebius(d)*floor(p2/d)); };

%o for(n=1, 22, print1(A054272(n),", ")); \\ _Antti Karttunen_, Dec 05 2014

%Y One less than A250473, two less than A250474.

%Y First differences: A251723.

%Y Cf. A000040, A000879, A001248, A002110, A005235, A005867, A008683, A008836, A020639, A078898, A249747.

%K nonn

%O 1,1

%A _Labos Elemer_, May 05 2000