A063962 - OEIS

A063962

Number of distinct prime divisors of n that are <= sqrt(n).

0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 0, 1, 1, 1, 0, 2, 1, 1, 1, 1, 0, 3, 0, 1, 1, 1, 1, 2, 0, 1, 1, 2, 0, 2, 0, 1, 2, 1, 0, 2, 1, 2, 1, 1, 0, 2, 1, 2, 1, 1, 0, 3, 0, 1, 2, 1, 1, 2, 0, 1, 1, 3, 0, 2, 0, 1, 2, 1, 1, 2, 0, 2, 1, 1, 0, 3, 1, 1, 1, 1, 0, 3, 1, 1, 1, 1, 1, 2, 0, 2, 1, 2, 0, 2, 0, 1, 3

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,12

COMMENTS

For all primes p: a(p) = 0 (not marked) and for k > 1 a(p^k) = 1.

a(1) = 0 and for n > 0 a(n) is the number of marks when applying the sieve of Eratosthenes where a stage for prime p starts at p^2.

If we define a divisor d|n to be inferior if d <= n/d, then inferior divisors are counted by A038548 and listed by A161906. This sequence counts inferior prime divisors. - Gus Wiseman, Feb 25 2021

LINKS

Harry J. Smith, Table of n, a(n) for n = 1..1000

FORMULA

G.f.: Sum_{k>=1} x^(prime(k)^2) / (1 - x^prime(k)). - Ilya Gutkovskiy, Apr 04 2020

a(A002110(n)) = n for n > 2. - Gus Wiseman, Feb 25 2021

EXAMPLE

a(33) = a(3*11) = 1, as 3^2 = 9 < 33 and 11^2 = 121 > 33.

From Gus Wiseman, Feb 25 2021: (Start)

The a(n) inferior prime divisors (columns) for selected n:

n = 3 8 24 3660 390 3570 87780

---------------------------------

{} 2 2 2 2 2 2

3 3 3 3 3

5 5 5 5

13 7 7

17 11

(End)

MAPLE

with(numtheory): a:=proc(n) local c, F, f, i: c:=0: F:=factorset(n): f:=nops(F): for i from 1 to f do if F[i]^2<=n then c:=c+1 else c:=c: fi od: c; end: seq(a(n), n=1..105); # Emeric Deutsch

MATHEMATICA

Join[{0}, Table[Count[Transpose[FactorInteger[n]][[1]], _?(#<=Sqrt[n]&)], {n, 2, 110}]] (* Harvey P. Dale, Mar 26 2015 *)

PROG

(PARI) { for (n=1, 1000, f=factor(n)~; a=0; for (i=1, length(f), if (f[1, i]^2<=n, a++, break)); write("b063962.txt", n, " ", a) ) } \\ Harry J. Smith, Sep 04 2009

(Haskell)

a063962 n = length [p | p <- a027748_row n, p ^ 2 <= n]

-- Reinhard Zumkeller, Apr 05 2012

CROSSREFS

Cf. A055399, A001221.

Cf. A027748, A063962.

Zeros are at indices A008578.

The divisors are listed by A161906 and add up to A097974.

Dominates A333806 (the strictly inferior version).

The superior version is A341591.

The strictly superior version is A341642.

A001221 counts prime divisors, with sum A001414.