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

Author

Wouter Meeussen, Oct 09 2001

Keywords

• nonn
• easy
• base

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

Examples

			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.
		

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.

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, A382294.

Programs

Haskell

a064547 1 = 0
a064547 n = length $ a213925_row n  -- Reinhard Zumkeller, Mar 20 2013

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}]

PARI

a(n) = {my(f = factor(n)[,2]); sum(k=1, #f, hammingweight(f[k]));} \\ Michel Marcus, Feb 10 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

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

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... (A382294), 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