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

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, 29, 38, 38, 48, 48, 47, 46, 45, 45, 56, 55, 54, 54, 66, 66, 79, 79, 79, 78, 92, 92, 92, 92, 91, 91, 106, 106, 105, 105, 104, 103, 119, 119, 136, 135, 135, 135, 134, 134, 152, 152, 151, 151, 170, 170

Offset: 1

Author

Andres Cicuttin, May 02 2018

Keywords

• nonn

Comments

From Robert Israel, May 07 2018: (Start)

If n is prime, a(n) = a(n-1) + A000720(n-1).

If n is in A006881, a(n) = a(n-1) - 1.

Otherwise, a(n) = a(n-1). (End)

Examples

			a(1) = a(2) = 0 because there are no two distinct primes less than or equal to 2.
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.
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.
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.
		

Crossrefs

Cf. A000720, A006881, A072613, A280710.

Programs

Maple

a[1]:= 0: d:= 0:
for n from 2 to 100 do
  if isprime(n) then a[n]:= a[n-1]+d; d:= d+1
  elif numtheory:-bigomega(n)=2 and not issqr(n) then a[n]:= a[n-1]-1
  else a[n]:= a[n-1] fi;
od:
seq(a[i],i=1..100); # Robert Israel, May 07 2018

Mathematica

a[n_] := Count[Subsets[Prime@Range@PrimePi@n, {2}], _?(Times @@ # > n &)];
Table[a[n], {n, 100}];

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

Formula

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