OFFSET
1,2
COMMENTS
a(n) counts the numbers s <= 10^n whose prime factorization s = p1^q1 * p2^q2 * ... * pk^qk (where p1 < p2 < ... < pk) has pk <= n.
EXAMPLE
For n=2, a(n)=6, because there are 6 numbers not greater than 10^2 whose prime divisors are not greater than 2: {2,4,8,16,32,64}.
MATHEMATICA
f[n0_, M0_] :=
Module[{M = M0, n = n0, k, p},
If[n == 1 || M <= 1, 0,
If[n == 2, Floor[Log[n, M]], p = NextPrime[n + 1, {-1, -2}];
k = Floor[Log[p[[1]], M]];
k + Sum[f[p[[2]], M/p[[1]]^i], {i, 0, k}]]]];
Table[{n, f[n, 10^n]}, {n, 20}]
(* Xianwen Wang, Jul 16 2022 *)
PROG
(Python)
from sympy import prevprime
def intlog(n, base):
ans=0
while n>=base:
n//=base
ans+=1
return (ans)
def count(n, s):
if n==1:
return 0
if n==2:
return intlog(s, n)
else:
p=prevprime(n+1)
p2=prevprime(p)
k=intlog(s, p)
for i in range(k+1):
k+=count(p2, s//(p**i))
return(k)
for n in range(1, 21):
print([n, count(n, 10**n)])
(PARI) a(n) = sum(k=2, 10^n, my(f=factor(k)[, 1]); vecmax(f) <= n); \\ Michel Marcus, Jul 14 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Zhining Yang, Jul 01 2022
EXTENSIONS
Edited by Peter Munn, May 26 2023
STATUS
approved