A087436 Number of odd prime factors of n, counted with repetitions.

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

Offset: 1

Author

Reinhard Zumkeller, Sep 03 2003

Keywords

• nonn
• easy

Comments

Number of parts larger than 1 in the partition with Heinz number n. The Heinz number of an integer partition p = [p_1, p_2, ..., p_r] is defined as Product(p_j-th prime, j=1...r) (concept used by Alois P. Heinz in A215366 as an "encoding" of a partition). Example: a(9) = 2 because the partition with Heinz number 9 (=3*3) is [2,2]. - Emeric Deutsch, Oct 02 2015

Totally additive because both A001222 and A007814 are. a(2) = 0, and a(p) = 1 for odd primes p, a(m*n) = a(m)+a(n) for m, n > 1. - Antti Karttunen, Jul 10 2020

Examples

			a(9) = 2 because 9 = 3*3 has 2 odd prime factors. - _Emeric Deutsch_, Oct 02 2015
		

Links

• Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms from G. C. Greubel)

Crossrefs

Cf. A000244 (the first occurrence of each n, and also the positions of records).

Cf. A000265, A001222, A005087, A007814, A083342, A215366, A336118, A336161.

Programs

Maple

seq(bigomega(n) - padic[ordp](n, 2), n=1..102); # Peter Luschny, Dec 06 2017

Mathematica

Join[{0},Table[Length[Select[Flatten[Table[#[[1]],{#[[2]]}]&/@ FactorInteger[ n]],OddQ]],{n,2,110}]] (* Harvey P. Dale, Feb 01 2013 *)

PARI

a(n) = bigomega(n) - valuation(n, 2); \\ Michel Marcus, Sep 10 2019

PARI

A087436(n) = (bigomega(n>>valuation(n,2))); \\ Antti Karttunen, Jul 10 2020

Formula

a(n) = A001222(n) - A007814(n).

a(n) = A001222(A000265(n)). - Antti Karttunen, Jul 10 2020

Sum_{k=1..n} a(k) = n * (log(log(n)) + B_2 - 1) + O(n/log(n)), where B_2 = A083342. - Amiram Eldar, May 16 2025