A334940 Partial sums of A230595.

0, 0, 0, 1, 1, 3, 3, 3, 4, 6, 6, 6, 6, 8, 10, 10, 10, 10, 10, 10, 12, 14, 14, 14, 15, 17, 17, 17, 17, 17, 17, 17, 19, 21, 23, 23, 23, 25, 27, 27, 27, 27, 27, 27, 27, 29, 29, 29, 30, 30, 32, 32, 32, 32, 34, 34, 36, 38, 38, 38, 38, 40, 40, 40, 42, 42, 42, 42, 44, 44, 44, 44, 44, 46

Offset: 1

Author

Daniel Suteu, May 17 2020

Keywords

• nonn

Comments

Sum of the Dirichlet convolution of the characteristic function of primes (A010051) with itself from 1 to n.

(a(n) + A000720(floor(sqrt(n))))/2 equals the number of semiprimes <= n.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A000720, A001222, A010051, A072000, A230595.

Programs

Maple

a:= proc(n) option remember; `if`(n<4, 0, a(n-1) +
     `if`(numtheory[bigomega](n)=2, `if`(issqr(n), 1, 2), 0))
    end:
seq(a(n), n=1..80);  # Alois P. Heinz, May 20 2020

Mathematica

f[n_] := DivisorSum[n, 1 &, PrimeQ[#] && PrimeQ[n/#] &]; Accumulate @ Array[f, 100] (* Amiram Eldar, May 20 2020 *)

PARI

a(n) = my(s=sqrtint(n)); 2*sum(k=1, s, if(isprime(k), primepi(n\k), 0)) - primepi(s)^2;

Python

from math import isqrt
from sympy import primepi, prime
def A334940(n): return (int(sum(primepi(n//prime(k))-k+1 for k in range(1,primepi(isqrt(n))+1)))<<1) - primepi(isqrt(n)) # Chai Wah Wu, Jul 23 2024

Formula

a(n) = Sum_{k=1..n} Sum_{d|k} A010051(d) * A010051(k/d).

a(n) = 2*Sum_{p prime <= sqrt(n)} A000720(floor(n/p)) - A000720(floor(sqrt(n)))^2.

a(n) = 2*A072000(n) - A000720(floor(sqrt(n))).

a(n) = 2*A072613(n) + A000720(floor(sqrt(n))). - Vaclav Kotesovec, May 21 2020

a(n) ~ 2*n*log(log(n))/log(n). - Vaclav Kotesovec, May 21 2020