A381391 Number of k <= 10^n that are neither squarefree nor prime powers (i.e., k is in A126706).

0, 29, 367, 3866, 39098, 391838, 3920154, 39205902, 392069187, 3920718974, 39207261564, 392072817656, 3920728751139, 39207289143932, 392072896183208, 3920728975677128, 39207289797472001, 392072898095046811, 3920728981307675534, 39207289814141997459, 392072898144605471040

Offset: 1

Author

Michael De Vlieger, Feb 22 2025

Keywords

• nonn

Examples

			Let S = A126706.
a(1) = 0 since the smallest term in S is 12.
a(2) = 29 since S(1..29) = {12, 18, 20, 24, ..., 99, 100}, etc.
		

Crossrefs

Cf. A011557, A071172, A126706, A267574, A372403, A229099, A380403.

Programs

Mathematica

Table[10^n - Sum[PrimePi@ Floor[10^(n/k)], {k, 2, Floor[Log2[10^n]]}] - Sum[MoebiusMu[k]*Floor[10^n/(k^2)], {k, Floor[Sqrt[10^n]]}], {n, 10}]

Python

from math import isqrt
from sympy import primepi, integer_nthroot, mobius
def A381391(n):
    m = 10**n
    return int(-sum(primepi(integer_nthroot(m,k)[0]) for k in range(2,m.bit_length()))-sum(mobius(k)*(m//k**2) for k in range(2, isqrt(m)+1))) # Chai Wah Wu, Feb 23 2025

Formula

a(n) = 10^n - Sum_{k = 2..log_2(10^n)} pi(floor(10^(n/k))) - Sum_{k = 1..floor(sqrt(10^n))} mu(k)*floor(10^n/k^2), where pi = A000720 and mu = A008683.

a(n) = A011557(n) - A071172(n) - A267574(n).