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

%I #83 Sep 28 2023 04:22:11

%S 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 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 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 Sum of binary digits (or count of 1-bits) in the exponents of the prime factorization of n.

%C 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 For n > 1, n is a product of a(n) distinct members of A050376. - _Matthew Vandermast_, Jul 13 2004

%C For n > 1: a(n) = length of n-th row in A213925. - _Reinhard Zumkeller_, Mar 20 2013

%C Number of Fermi-Dirac factors of n. - _Peter Munn_, Dec 27 2019

%H Harry J. Smith (terms 1..2000) & Antti Karttunen, <a href="/A064547/b064547.txt">Table of n, a(n) for n = 1..32768</a>

%H <a href="/index/Eu#epf">Index entries for sequences computed from exponents in factorization of n</a>.

%H <a href="/index/Bi#binary">Index entries for sequences related to binary expansion of n</a>.

%F a(m*n) <= a(m)*a(n). - _Reinhard Zumkeller_, Mar 20 2013

%F From _Antti Karttunen_, Feb 09 2016: (Start)

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

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

%F (End)

%F a(n) = log_2(A037445(n)). - _Vladimir Shevelev_, May 13 2016

%F a(n) = A286574(A156552(n)). - _Antti Karttunen_, May 28 2017

%F Additive with a(p^e) = A000120(e). - _Jianing Song_, Jul 28 2018

%F a(n) = A000120(A052331(n)). - _Peter Munn_, Aug 26 2019

%F From _Peter Munn_, Dec 18 2019: (Start)

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

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

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

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

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

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

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

%F a(A003961(n)) = a(n).

%F a(A225546(n)) = a(n).

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

%F a(A050376(n)) = 1.

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

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

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

%F (End)

%F 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

%e 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 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 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 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 # alternative Maple program:

%p A064547:= proc(n) local F;

%p F:= ifactors(n)[2];

%p add(convert(convert(f[2],base,2),`+`),f=F)

%p end proc:

%p map(A064547,[$1..100]); # _Robert Israel_, May 17 2016

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

%o (PARI) SumD(x)= { local(s); s=0; while (x>9, s+=x-10*(x\10); x\=10); return(s + x) }

%o baseE(x, b)= { local(d,e,f); e=0; f=1; while (x>0, d=x-b*(x\b); x\=b; e+=d*f; f*=10); return(e) }

%o { for (n=1, 2000, f=factor(n)~; a=0; for (i=1, length(f), a+=SumD(baseE(f[2, i], 2))); write("b064547.txt", n, " ", a) ) } \\ _Harry J. Smith_, Sep 18 2009

%o (PARI) a(n) = {my(f = factor(n)[,2]); sum(k=1, #f, hammingweight(f[k]));} \\ _Michel Marcus_, Feb 10 2016

%o (Haskell)

%o a064547 1 = 0

%o a064547 n = length $ a213925_row n -- _Reinhard Zumkeller_, Mar 20 2013

%o (Scheme, two variants, both using memoizing-macro definec)

%o (definec (A064547 n) (cond ((= 1 n) 0) (else (+ (A000120 (A067029 n)) (A064547 (A028234 n))))))

%o (definec (A064547 n) (if (= 1 n) 0 (+ (A000120 (A007814 n)) (A064547 (A064989 n)))))

%o ;; _Antti Karttunen_, Feb 09 2016

%o (Python)

%o from sympy import factorint

%o def wt(n): return bin(n).count("1")

%o def a(n):

%o f=factorint(n)

%o return sum([wt(f[i]) for i in f]) # _Indranil Ghosh_, May 30 2017

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

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

%Y Row lengths of A213925.

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

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

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

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

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

%Y Cf. A077761, A176699.

%K nonn,easy,base

%O 1,6

%A _Wouter Meeussen_, Oct 09 2001