login
A303917
Number of ordered pairs of primes (p,q) such that p < q <= n and p*q > n.
0
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,5
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)
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
EXAMPLE
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.
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}];
PROG
(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
CROSSREFS
KEYWORD
nonn
AUTHOR
Andres Cicuttin, May 02 2018
STATUS
approved