A110475 Number of symbols '*' and '^' to write the canonical prime factorization of n.

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

Offset: 1

Author

Reinhard Zumkeller, Sep 08 2005

Keywords

• nonn

Comments

It is conjectured that 1,2,3,4,5,6,7,9,11 are the only positive integers which cannot be represented as the sum of two elements of indices n such that a(n) = 1. - Jonathan Vos Post, Sep 11 2005

a(n) = 2 iff n is a sphenic number (A007304) or n is a prime p times a prime power q^e with e > 1 and q not equal to p. a(n) = 3 iff n has exactly four distinct prime factors (A046386); or n is the product of two prime powers (p^e)*(q^f) with e > 1, f > 1 and p not equal to q; or n is a semiprime s times a prime power r^g with g > 1 and r relatively prime to s. For a(n) > 3, Reinhard Zumkeller's description is a simpler description than the above compound descriptions. - Jonathan Vos Post, Sep 11 2005

Examples

			a(208029250) = a(2*5^3*11^2*13*23^2) = 4 '*' + 3 '^' = 7.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Eric Weisstein's World of Mathematics, Prime Factorization.

Crossrefs

Cf. A050252, A001358, A025475, A000040, A238949.

Cf. A007304, A046386, A008578.

Cf. A001221, A056170, A118914, A077761, A085548.

Programs

Haskell

a110475 1 = 0
a110475 n = length us - 1 + 2 * length vs where
            (us, vs) = span (== 1) $ a118914_row n
-- Reinhard Zumkeller, Mar 23 2014

Mathematica

A110475[n_] := 2*Length[#] - 1 - Count[#, 1] & [FactorInteger[n][[All, 2]]];
Array[A110475, 100] (* Paolo Xausa, Mar 10 2025 *)

Formula

a(n) = A001221(n) - 1 + A056170(n) for n > 1.

a(n) = 0 iff n=1 or n is prime: a(A008578(n)) = 0.

a(n) = 1 iff n is a semiprime or a prime power p^e with e > 1.

From Amiram Eldar, Sep 27 2024: (Start)

a(n) = A238949(n) - 1 for n >= 2.

Sum_{k=1..n} a(k) ~ n * (log(log(n)) + B + C - 1), where B is Mertens's constant (A077761) and C = Sum_{p prime} 1/p^2 (A085548). (End)