A064547 Sum of binary digits (or count of 1-bits) in the exponents of the prime factorization of n.

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

Offset

1,6

Comments

This sequence is different from A058061 for n containing 6th, 8th, ..., k-th powers in its prime decomposition, where k runs through the integers missing from A064548.

For n > 1, n is a product of a(n) distinct members of A050376. - Matthew Vandermast, Jul 13 2004

For n > 1: a(n) = length of n-th row in A213925. - Reinhard Zumkeller, Mar 20 2013

Number of Fermi-Dirac factors of n. - Peter Munn, Dec 27 2019

Links

Antti Karttunen, Table of n, a(n) for n = 1..32768 (terms 1..2000 from Harry J. Smith)

Index entries for sequences computed from exponents in factorization of n.

Index entries for sequences related to binary expansion of n.

Formula

a(m*n) <= a(m)*a(n). - Reinhard Zumkeller, Mar 20 2013

From Antti Karttunen, Feb 09 2016: (Start)

a(1) = 0, and for n > 1, a(n) = A000120(A067029(n)) + a(A028234(n)).

a(1) = 0, and for n > 1, a(n) = A000120(A007814(n)) + a(A064989(n)).

(End)

a(n) = log_2(A037445(n)). - Vladimir Shevelev, May 13 2016

a(n) = A286574(A156552(n)). - Antti Karttunen, May 28 2017

Additive with a(p^e) = A000120(e). - Jianing Song, Jul 28 2018

a(n) = A000120(A052331(n)). - Peter Munn, Aug 26 2019

From Peter Munn, Dec 18 2019: (Start)

a(A000379(n)) mod 2 = 0.

a(A000028(n)) mod 2 = 1.

A001221(n) <= a(n) <= A001222(n).

A001221(n) < a(n) => a(n) < A001222(n).

a(n) = A001222(n) if and only if n is in A005117.

a(n) = A001221(n) if and only if n is in A138302.

a(n^2) = a(n).

a(A003961(n)) = a(n).

a(A225546(n)) = a(n).

a(n) = a(A007913(n)) + a(A008833(n)).

a(A050376(n)) = 1.

a(A059897(n,k)) + 2 * a(A059895(n,k)) = a(n) + a(k).

a(A059896(n,k)) + a(A059895(n,k)) = a(n) + a(k).

Alternative definition: a(1) = 0; a(n * m) = a(n) + 1 for m = A050376(k) > A223491(n).

(End)

Sum_{k=1..n} a(k) ~ n * (log(log(n)) + B + C), where B is Mertens's constant (A077761) and C = Sum_{p prime} f(1/p) = 0.13605447049622836522..., where f(x) = -x + Sum_{k>=0} x^(2^k)/(1+x^(2^k)). - Amiram Eldar, Sep 28 2023

a(n) << log n/log log n. - Charles R Greathouse IV, Nov 29 2024

Example

For n = 54, n = 2^1 * 3^3 with exponents (1) and (11) in binary, so a(54) = A000120(1) + A000120(3) = 1 + 2 = 3.

Maple

expts:=proc(n) local t1, t2, t3, t4, i; if n=1 then RETURN([0]); fi; if isprime(n) then RETURN([1]); fi; t1:=ifactor(n); if nops(factorset(n))=1 then RETURN([op(2, t1)]); fi; t2:=nops(t1); t3:=[]; for i from 1 to t2 do t4:=op(i, t1); if nops(t4) = 1 then t3:=[op(t3), 1]; else t3:=[op(t3), op(2, t4)]; fi; od; RETURN(t3); end;
A000120 := proc(n) local w, m, i; w := 0; m := n; while m > 0 do i := m mod 2; w := w+i; m := (m-i)/2; od; w; end:
LamMos:= proc(n) local t1, t2, t3, i; t1:=expts(n); add( A000120(t1[i]), i=1..nops(t1)); end; # N. J. A. Sloane, Dec 20 2007
# alternative Maple program:
A064547:= proc(n) local F;
F:= ifactors(n)[2];
add(convert(convert(f[2], base, 2), `+`), f=F)
end proc:
map(A064547, [$1..100]); # Robert Israel, May 17 2016

Mathematica

Table[Plus@@(DigitCount[Last/@FactorInteger[k], 2, 1]), {k, 105}]

Prog

(PARI) a(n) = {my(f = factor(n)[, 2]); sum(k=1, #f, hammingweight(f[k])); } \\ Michel Marcus, Feb 10 2016
(Haskell)
a064547 1 = 0
a064547 n = length $ a213925_row n  -- Reinhard Zumkeller, Mar 20 2013
(Scheme)
;; uses memoizing-macro definec
(definec (A064547 n) (cond ((= 1 n) 0) (else (+ (A000120 (A067029 n)) (A064547 (A028234 n))))))
;; Antti Karttunen, Feb 09 2016
(Scheme)
;; uses memoizing-macro definec
(definec (A064547 n) (if (= 1 n) 0 (+ (A000120 (A007814 n)) (A064547 (A064989 n)))))
;; Antti Karttunen, Feb 09 2016
(Python)
from sympy import factorint
def wt(n): return bin(n).count("1")
def a(n):
    f=factorint(n)
    return sum([wt(f[i]) for i in f]) # Indranil Ghosh, May 30 2017

Crossrefs

Cf. A000028 (positions of odd terms), A000379 (of even terms).

Cf. A050376 (positions of ones), A268388 (terms larger than ones).

Row lengths of A213925.

A000120, A007814, A028234, A037445, A052331, A064989, A067029, A156552, A223491, A286574 are used in formulas defining this sequence.

Cf. A005117, A058061 (to which A064548 relates), A138302.

Cf. other sequences counting factors of n: A001221, A001222.

Cf. other sequences where a(n) depends only on the prime signature of n: A181819, A267116, A268387.

A003961, A007913, A008833, A059895, A059896, A059897, A225546 are used to express relationship between terms of this sequence.

Cf. A077761, A176699, A037992.

Sequence in context: A058061 A376886 A371090 * A318306 A345935 A214715

Adjacent sequences: A064544 A064545 A064546 * A064548 A064549 A064550

Keyword

nonn,easy,base

Author

Wouter Meeussen, Oct 09 2001

Status

approved