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

Offset: 1

Author

Reinhard Zumkeller, Sep 04 2001

Keywords

• nonn

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

Examples

			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
                                  19
(End)
		

Links

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

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.

A033677 selects the smallest superior divisor.

A038548 counts inferior divisors.

A063538/A063539 have/lack a superior prime divisor.

A161908 lists superior divisors.

A207375 lists central divisors.

A217581 selects the greatest inferior prime divisor.

A341676 lists the unique superior prime divisors.

- Inferior: A033676, A066839, A069288, A072499, A333749, A333750.

- Superior: A051283, A059172, A070038, A072500, A116883, A341592, A341675.

- Strictly Inferior: A056924, A060775, A070039, A333805, A341596, A341674.

- Strictly Superior: A056924, A140271, A238535, A341594, A341595, A341673.

Cf. A000005, A001248, A005117, A006530, A020639, A048098, A064052, A341643.

Programs

Haskell

a063962 n = length [p | p <- a027748_row n, p ^ 2 <= n]
-- Reinhard Zumkeller, Apr 05 2012

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 *)

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

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

Extensions

Revised definition from Emeric Deutsch, Jan 31 2006