cp's OEIS Frontend

A303917 Number of ordered pairs of primes (p,q) such that p < q <= n and p*q > n.

%I A303917 #20 Jun 10 2018 12:53:32
%S A303917 0,0,1,1,3,2,5,5,5,4,8,8,13,12,11,11,17,17,24,24,23,22,30,30,30,29,29,
%T A303917 29,38,38,48,48,47,46,45,45,56,55,54,54,66,66,79,79,79,78,92,92,92,92,
%U A303917 91,91,106,106,105,105,104,103,119,119,136,135,135,135,134,134,152,152,151,151,170,170
%N A303917 Number of ordered pairs of primes (p,q) such that p < q <= n and p*q > n.
%C A303917 From _Robert Israel_, May 07 2018: (Start)
%C A303917 If n is prime, a(n) = a(n-1) + A000720(n-1).
%C A303917 If n is in A006881, a(n) = a(n-1) - 1.
%C A303917 Otherwise, a(n) = a(n-1). (End)
%F A303917 n^2/2 <= a(n) <= A000720(n/2)*(A000720(n)-A000720(n/2)) ~ n^2/(4*log(n))^2 as n -> infinity. - _Robert Israel_, May 07 2018
%e A303917 a(1) = a(2) = 0 because there are no two distinct primes less than or equal to 2.
%e A303917 a(3) = 1 because there is only one ordered pair of distinct primes less than or equal to 3: (2,3), and 2*3 > 3.
%e A303917 a(4) = 1 because there is only one ordered pair of distinct primes less than or equal to 4: (2,3), and 2*3 > 4.
%e A303917 a(5) = 3 because there are three ordered pairs of distinct primes less than or equal to 5: (2,3), (2,5) and (3,5), and 2*3 > 5, 2*5 > 5 and 3*5 > 5.
%p A303917 a[1]:= 0: d:= 0:
%p A303917 for n from 2 to 100 do
%p A303917   if isprime(n) then a[n]:= a[n-1]+d; d:= d+1
%p A303917   elif numtheory:-bigomega(n)=2 and not issqr(n) then a[n]:= a[n-1]-1
%p A303917   else a[n]:= a[n-1] fi;
%p A303917 od:
%p A303917 seq(a[i],i=1..100); # _Robert Israel_, May 07 2018
%t A303917 a[n_] := Count[Subsets[Prime@Range@PrimePi@n, {2}], _?(Times @@ # > n &)];
%t A303917 Table[a[n], {n, 100}];
%o A303917 (PARI) a(n) = {my(nb = 0); forprime(q=1, n, forprime(p=1, q-1, if (p*q >n, nb++););); return (nb);} \\ _Michel Marcus_, May 05 2018
%Y A303917 Cf. A000720, A006881, A072613, A280710.
%K A303917 nonn
%O A303917 1,5
%A A303917 _Andres Cicuttin_, May 02 2018