A091372 Number of numbers <= n having more prime factors than the value of their smallest prime factor.

0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 11, 11, 12, 12, 13, 13, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 18, 18, 19, 19, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 24, 24, 25, 25, 26, 26, 27

Offset: 1

Author

Reinhard Zumkeller, Jan 04 2004

Keywords

• nonn

Comments

a(n) = #{m: A001222(m)>A020639(m), m<=n};

a(n) + A091373(n) + A091374(n) = n.

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A091375, A091371.

Programs

Mathematica

Accumulate@ Boole@ Map[Length@ Flatten[Table[#1, {#2}] & @@@ #] > #[[1, 1]] &@ FactorInteger@ # &, Range@ 80] (* Michael De Vlieger, Jul 06 2016 *)

PARI

a(n)=sum(k=8,n, bigomega(k) > factor(k)[1,1]) \\ Charles R Greathouse IV, Jul 06 2016

PARI

first(n)=my(v=vector(n),s); for(k=8,n, v[k] = s += bigomega(k) > factor(k)[1,1]); v \\ Charles R Greathouse IV, Jul 06 2016

Formula

For any k < 1, a(n) > kn for large enough k. For example, a(n) > n/2 for n > 26474. - Charles R Greathouse IV, Jul 06 2016