A355412 Count of numbers <= 10^n with no prime factor greater than n.

0, 6, 39, 66, 312, 506, 2154, 3426, 5193, 7574, 30523, 44695, 173076, 254064, 364384, 511984, 1945204, 2749999, 10159602, 14427308, 20186025, 27861174, 101837745, 141340074, 193902061, 263152094, 353549941, 470539446, 1730528206, 2319027316

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.

Links

Table of n, a(n) for n=1..30.

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

Sequence in context: A061423 A080298 A253803 * A058897 A058985 A116951

Adjacent sequences: A355409 A355410 A355411 * A355413 A355414 A355415

Keyword

nonn

Author

Zhining Yang, Jul 01 2022

Extensions

Edited by Peter Munn, May 26 2023

Status

approved