cp's OEIS Frontend

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

%I A064547 #100 Mar 21 2025 11:56:06
%S A064547 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,
%T A064547 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,
%U A064547 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
%N A064547 Sum of binary digits (or count of 1-bits) in the exponents of the prime factorization of n.
%C A064547 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.
%C A064547 For n > 1, n is a product of a(n) distinct members of A050376. - _Matthew Vandermast_, Jul 13 2004
%C A064547 For n > 1: a(n) = length of n-th row in A213925. - _Reinhard Zumkeller_, Mar 20 2013
%C A064547 Number of Fermi-Dirac factors of n. - _Peter Munn_, Dec 27 2019
%H A064547 Antti Karttunen, <a href="/A064547/b064547.txt">Table of n, a(n) for n = 1..32768</a> (terms 1..2000 from Harry J. Smith)
%H A064547 <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>.
%H A064547 <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.
%F A064547 a(m*n) <= a(m)*a(n). - _Reinhard Zumkeller_, Mar 20 2013
%F A064547 From _Antti Karttunen_, Feb 09 2016: (Start)
%F A064547 a(1) = 0, and for n > 1, a(n) = A000120(A067029(n)) + a(A028234(n)).
%F A064547 a(1) = 0, and for n > 1, a(n) = A000120(A007814(n)) + a(A064989(n)).
%F A064547 (End)
%F A064547 a(n) = log_2(A037445(n)). - _Vladimir Shevelev_, May 13 2016
%F A064547 a(n) = A286574(A156552(n)). - _Antti Karttunen_, May 28 2017
%F A064547 Additive with a(p^e) = A000120(e). - _Jianing Song_, Jul 28 2018
%F A064547 a(n) = A000120(A052331(n)). - _Peter Munn_, Aug 26 2019
%F A064547 From _Peter Munn_, Dec 18 2019: (Start)
%F A064547 a(A000379(n)) mod 2 = 0.
%F A064547 a(A000028(n)) mod 2 = 1.
%F A064547 A001221(n) <= a(n) <= A001222(n).
%F A064547 A001221(n) < a(n) => a(n) < A001222(n).
%F A064547 a(n) = A001222(n) if and only if n is in A005117.
%F A064547 a(n) = A001221(n) if and only if n is in A138302.
%F A064547 a(n^2) = a(n).
%F A064547 a(A003961(n)) = a(n).
%F A064547 a(A225546(n)) = a(n).
%F A064547 a(n) = a(A007913(n)) + a(A008833(n)).
%F A064547 a(A050376(n)) = 1.
%F A064547 a(A059897(n,k)) + 2 * a(A059895(n,k)) = a(n) + a(k).
%F A064547 a(A059896(n,k)) + a(A059895(n,k)) = a(n) + a(k).
%F A064547 Alternative definition: a(1) = 0; a(n * m) = a(n) + 1 for m = A050376(k) > A223491(n).
%F A064547 (End)
%F A064547 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
%F A064547 a(n) << log n/log log n. - _Charles R Greathouse IV_, Nov 29 2024
%e A064547 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.
%p A064547 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;
%p A064547 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:
%p A064547 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
%p A064547 # alternative Maple program:
%p A064547 A064547:= proc(n) local F;
%p A064547 F:= ifactors(n)[2];
%p A064547 add(convert(convert(f[2],base,2),`+`),f=F)
%p A064547 end proc:
%p A064547 map(A064547,[$1..100]); # _Robert Israel_, May 17 2016
%t A064547 Table[Plus@@(DigitCount[Last/@FactorInteger[k], 2, 1]), {k, 105}]
%o A064547 (PARI) a(n) = {my(f = factor(n)[,2]); sum(k=1, #f, hammingweight(f[k]));} \\ _Michel Marcus_, Feb 10 2016
%o A064547 (Haskell)
%o A064547 a064547 1 = 0
%o A064547 a064547 n = length $ a213925_row n  -- _Reinhard Zumkeller_, Mar 20 2013
%o A064547 (Scheme)
%o A064547 ;; uses memoizing-macro definec
%o A064547 (definec (A064547 n) (cond ((= 1 n) 0) (else (+ (A000120 (A067029 n)) (A064547 (A028234 n))))))
%o A064547 ;; _Antti Karttunen_, Feb 09 2016
%o A064547 (Scheme)
%o A064547 ;; uses memoizing-macro definec
%o A064547 (definec (A064547 n) (if (= 1 n) 0 (+ (A000120 (A007814 n)) (A064547 (A064989 n)))))
%o A064547 ;; _Antti Karttunen_, Feb 09 2016
%o A064547 (Python)
%o A064547 from sympy import factorint
%o A064547 def wt(n): return bin(n).count("1")
%o A064547 def a(n):
%o A064547     f=factorint(n)
%o A064547     return sum([wt(f[i]) for i in f]) # _Indranil Ghosh_, May 30 2017
%Y A064547 Cf. A000028 (positions of odd terms), A000379 (of even terms).
%Y A064547 Cf. A050376 (positions of ones), A268388 (terms larger than ones).
%Y A064547 Row lengths of A213925.
%Y A064547 A000120, A007814, A028234, A037445, A052331, A064989, A067029, A156552, A223491, A286574 are used in formulas defining this sequence.
%Y A064547 Cf. A005117, A058061 (to which A064548 relates), A138302.
%Y A064547 Cf. other sequences counting factors of n: A001221, A001222.
%Y A064547 Cf. other sequences where a(n) depends only on the prime signature of n: A181819, A267116, A268387.
%Y A064547 A003961, A007913, A008833, A059895, A059896, A059897, A225546 are used to express relationship between terms of this sequence.
%Y A064547 Cf. A077761, A176699, A037992, A382294.
%K A064547 nonn,easy,base
%O A064547 1,6
%A A064547 _Wouter Meeussen_, Oct 09 2001