A058061 -id:A058061 - cp's OEIS frontend

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

Wouter Meeussen, Oct 09 2001

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

			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.

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.

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.

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

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

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

a(n) = {my(f = factor(n)[,2]); sum(k=1, #f, hammingweight(f[k]));} \\ Michel Marcus, Feb 10 2016

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

;; uses memoizing-macro definec
(definec (A064547 n) (cond ((= 1 n) 0) (else (+ (A000120 (A067029 n)) (A064547 (A028234 n))))))
;; Antti Karttunen, Feb 09 2016

;; uses memoizing-macro definec
(definec (A064547 n) (if (= 1 n) 0 (+ (A000120 (A007814 n)) (A064547 (A064989 n)))))
;; Antti Karttunen, Feb 09 2016

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

A055079 Smallest number with exactly n nonprime divisors.

Original entry on oeis.org

1, 4, 8, 12, 30, 24, 36, 48, 60, 72, 2048, 192, 120, 216, 180, 288, 240, 432, 576, 420, 360, 864, 1296, 900, 960, 1728, 720, 840, 1080, 3456, 9216, 1260, 1440, 6912, 34359738368, 1680, 2160, 10368, 2880, 15552, 15360, 3600, 4620, 2520, 4320, 31104

Offset: 1

Labos Elemer, Jun 13 2000

a(n)<=2^n; see A057838 for the indices n where a(n)=2^n.

			a(5) = 30 because it is the first integer which has five nonprime divisors (1, 6, 10, 15 and 30; the divisors 2, 3 and 5 are prime).
a(35) = 2^35 = 34359738368.
a(71) = 2^71 = 2361183241434822606848.
a(191) = 2^191 = 3138550867693340381917894711603833208051177722232017256448.

Ray Chandler, Table of n, a(n) for n=1..4438

Cf. A001221, A001222, A058060, A058061, A000005, A033273, A057838.

a055079 n = head [x | x <- [1..], a033273 x == n]
-- Reinhard Zumkeller, Dec 16 2013

a = Table[0, {100} ]; Do[ c = Count[ PrimeQ[ Divisors[ n ] ], False]; If[ c < 101 && a[[ c ]] == 0, a[[ c ]] = n], {n, 2, 10077696} ];
Table[SelectFirst[Table[{n,Count[Divisors[n],?(!PrimeQ[#]&)]},{n,10000}],#[[2]]==k&],{k,34}][[;;,1]] (* The program generates the first 34 terms of the sequence. *) (* _Harvey P. Dale, Mar 04 2024 *)

sme(n) = {k = 1; while (sumdiv(k, d, ! isprime(d)) != n, k++); k;} \\ Michel Marcus, Dec 13 2013

a(n)=Min{k; A000005(k)-A001221(k)=A033273(k)=n}

More terms from Robert G. Wilson v, Nov 20 2000

Edited by Ray Chandler, Aug 12 2010

A058060 Number of distinct prime factors of d(n), the number of divisors of n.

Original entry on oeis.org

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

Offset: 1

Labos Elemer, Nov 23 2000

The sums of the first 10^k terms, for k = 1, 2, ..., are 9, 122, 1285, 13096, 131729, 1319621, 13203252, 132055132, 1320621032, 13206429426, 132064984784, ... . From these values the asymptotic mean of this sequence, whose existence was proven by Rieger (1972) and Heppner (1974) (see the Formula section), can be empirically evaluated by 1.3206... . - Amiram Eldar, Jan 15 2024

			n = 120 = 8*3*5, d(n) = 16 = 2^4, so a(120)=1.

József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Chapter V, page 164.

G. C. Greubel, Table of n, a(n) for n = 1..5001
E. Heppner, Über die Iteration von Teilerfunktionen, Journal für die reine und angewandte Mathematik, Vol. 265 (1974), pp. 176-182.
G. J. Rieger, Über einige arithmetische Summen, Manuscripta Mathematica, Vol. 7 (1972), pp. 23-34.

Cf. A001221, A000005, A058061.

Table[PrimeNu[DivisorSigma[0, n]], {n, 1, 100}] (* G. C. Greubel, May 05 2017 *)

a(n)=omega(numdiv(n)) \\ Charles R Greathouse IV, May 05 2017

a(n) = A001221(A000005(n)).

Sum_{k=1..n} a(k) = c * n + O(sqrt(n) * log(n)^5), where c is a constant (Rieger, 1972; Heppner, 1974). - Amiram Eldar, Jan 15 2024

Offset corrected by Sean A. Irvine, Jul 22 2022

A376886 The number of distinct factors of n of the form p^(k!), where p is a prime and k >= 1, when the factorization is uniquely done using the factorial-base representation of the exponents in the prime factorization of n.

Original entry on oeis.org

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, 1, 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

Amiram Eldar, Oct 08 2024

See A376885 for details about this factorization.
First differs from A371090 at n = 2^18 = 262144.
Differs from A064547 at n = 64, 128, 192, 256, 320, 384, 448, 512, ... .
Differs from A058061 at n = 128, 384, 512, 640, 896, ... .

			For n = 8 = 2^3, the representation of 3 in factorial base is 11, i.e., 3 = 1! + 2!, so 8 = (2^(1!))^1 * (2^(2!))^1 and a(8) = 1 + 1 = 2.
For n = 16 = 2^4, the representation of 4 in factorial base is 20, i.e., 4 = 2 * 2!, so 16 = (2^(2!))^2 and a(16) = 1.

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A007623, A058061, A060130, A077761, A371090.

Similar sequences: A064547, A318464, A376885.

fdignum[n_] := Module[{k = n, m = 2, r, s = 0}, While[{k, r} = QuotientRemainder[k, m]; k != 0 || r != 0, If[r > 0, s++]; m++]; s]; f[p_, e_] := fdignum[e]; a[1] = 0; a[n_] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100]

fdignum(n) = {my(k = n, m = 2, r, s = 0); while([k, r] = divrem(k, m); k != 0 || r != 0, if(r > 0, s ++); m++); s;}
a(n) = {my(e = factor(n)[, 2]); sum(i = 1, #e, fdignum(e[i]));}

Additive with a(p^e) = A060130(e).

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.12589120926760155013..., where f(x) = -x + (1-x) * Sum_{k>=1} A060130(k) * x^k.

A057838 Numbers k such that A055079(k) = 2^k.

Original entry on oeis.org

2, 3, 11, 35, 71, 191, 419, 659, 1091, 1199, 1379, 1655, 2015, 2135, 2339, 2591, 3059, 4439, 6119, 6215, 6335, 7055, 8099, 8351, 8519, 9815, 11159, 12419, 12431, 12599, 12719, 12851, 13679, 15119, 15239, 16415, 16919, 17255, 17879, 18215, 18479

Offset: 1

Labos Elemer, Nov 24 2000

nonn

			11 is a term: 2^11 has 11 nonprime divisors; c(11)=A055079(11) could not have r = 2, 3, 4 or more distinct prime divisors because 11 + {2, 3, 4, 5, 6, 7, 8, 9, ...} values of corresponding d(c(11)) = {13, 14, 15, ...} had 1, 2, 2, 4, 1, 3, 1, 3, 2, 2, 1, 4, 2, 2 non-distinct prime divisors, which provides an upper bound for r ... in contradiction with demanded values: 2, 3, 4, 5, 6, 7, ... This is why A055079(11)=2048. Larger cases are handled in a similar way.
a(35) = 15239 since A055079(15239) = 2^15239, which has 4588 decimal digits.
A protocol for 15239 is as follows: u=15239; t0=Table[s, {s, 0, 17}]; t1=Table[mr[w], {w, u, u+17}]; t2=t1-t0; g=Table[{w, mr[w]}, {w, u, u+17}]; i1=TimeUsed[]; Write["a(bad)tx1", u, t1, t2, g]; 15239.
Supposed number of A001221(x) which should be larger or equal than A001222(d(x)): {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17}.
A001222(d(x)) {3, 6, 1, 2, 2, 4, 2, 6, 2, 5, 4, 5, 2, 5, 2, 3, 5, 4}.
A001222(d(x)) - A001221(x) (negative value means "nasty case") {3, 5, -1, -1, -2, -1, -4, -1, -6, -4, -6, -6, -10, -8, -12, -12, -11, -13} numbers (corresponding d(x) values for some x) together with A001222[d(x)] {{15239, 3}, {15240, 6}, {15241, 1}, {15242, 2}, {15243, 2}, {15244, 4}, {15245, 2}, {15246, 6}, {15247, 2}, {15248, 5}, {15249, 4}, {15250, 5}, {15251, 2}, {15252, 5}, {15253, 2}, {15254, 3}, {15255, 5}, {15256, 4}}.

Ray Chandler, Table of n, a(n) for n = 1..13925

Cf. A055079, A001221, A001222, A000005, A058060, A058061, A057841.

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

A001221(A055079(a(n))) = 1.

Edited, corrected and extended by Ray Chandler, Aug 14 2010

A064548 Numbers k for which the sum of the binary digits equals the number of prime factors of k + 1 counted with multiplicity.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 9, 11, 15, 16, 19, 20, 23, 24, 26, 31, 33, 34, 39, 41, 44, 47, 48, 49, 53, 63, 67, 68, 69, 74, 79, 83, 89, 95, 97, 98, 99, 104, 107, 127, 132, 135, 137, 139, 144, 146, 149, 152, 159, 160, 164, 167, 179, 191, 194, 195, 197, 199, 209, 215, 242, 255

Offset: 1

Wouter Meeussen, Oct 09 2001

nonn

This sequence becomes rare for large n: 15 values between 100000 and 101024 and none between 1000000 and 1001024.

Numbers k such that A000120(k) = A001222(k+1). - Franklin T. Adams-Watters, Aug 17 2012

			8 is absent since 8 in binary is (1000) with sum=1, while (8+1) has 2 factors.

Harry J. Smith, Table of n, a(n) for n = 1..1000

Cf. A000120, A001222, A058061, A064547.

Select[ Range[ 1024 ], DigitCount[ #, 2, 1 ]===(Plus@@(Last/@FactorInteger[ #+1 ]))& ]
Select[Range[300],DigitCount[#,2,1]==PrimeOmega[#+1]&] (* Harvey P. Dale, Mar 11 2023 *)

isok(k) = { hammingweight(k) == bigomega(k+1) } \\ Harry J. Smith, Sep 18 2009

A371090 Additive with a(p^1) = 1, a(p^e) = a(A276086(e)) for e > 1, where A276086 is the primorial base exp-function.

Original entry on oeis.org

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, 1, 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, 2, 1, 3, 1, 3, 2, 2, 1, 3, 2, 2, 2, 2, 2, 4, 1, 2, 2, 2, 2, 3, 1, 2

Offset: 1

Antti Karttunen, Mar 31 2024

nonn

Used to construct A371091.

Antti Karttunen, Table of n, a(n) for n = 1..65537
Index entries for sequences computed from exponents in factorization of n

Cf. A001221, A001222, A276086, A371091.
Differs from A064547 for the first time at n=63, where a(64) = 1, while A064547(64) = 2.
Differs from A058061 for the first time at n=128, where a(128) = 2, while A058061(128) = 3.

A276086(n) = { my(m=1, p=2); while(n, m *= (p^(n%p)); n = n\p; p = nextprime(1+p)); (m); };
A371090(n) = vecsum(apply(e->if(1==e,1,A371090(A276086(e))),factor(n)[, 2]));

Additive with a(p^1) = 1, a(p^e) = A371091(e) for e > 1.

For all n >= 1, A001221(n) <= a(n) <= A001222(n).

A057841 a(n) = 2^A057838(n) corresponding to extremal cases of A055079.

Original entry on oeis.org

4, 8, 2048, 34359738368, 2361183241434822606848, 3138550867693340381917894711603833208051177722232017256448

Offset: 1

Labos Elemer, Nov 24 2000

nonn

			a(7) = 2^419 which has 127 decimal digits.
a(35) = 2^15239 which has 4588 decimal digits.

Ray Chandler, Table of n, a(n) for n=1..17

Cf. A000005, A001221, A001222, A055079, A058060, A058061, A057838.

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

Edited by Ray Chandler, Aug 14 2010

A079057 a(n) = Sum_{k=1..n} bigomega(tau(k)).

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 7, 9, 10, 12, 13, 15, 16, 18, 20, 21, 22, 24, 25, 27, 29, 31, 32, 35, 36, 38, 40, 42, 43, 46, 47, 49, 51, 53, 55, 57, 58, 60, 62, 65, 66, 69, 70, 72, 74, 76, 77, 79, 80, 82, 84, 86, 87, 90, 92, 95, 97, 99, 100, 103, 104, 106, 108, 109, 111, 114, 115, 117, 119

Offset: 1

Benoit Cloitre, Feb 02 2003

József Sándor, Dragoslav S. Mitrinovic, Borislav Crstici, Handbook of Number Theory I, Springer Science & Business Media, 2005, Chapter V, page 164.

Harvey P. Dale, Table of n, a(n) for n = 1..1000
E. Heppner, Über die Iteration von Teilerfunktionen, Journal für die reine und angewandte Mathematik, Vol. 265 (1974), pp. 176-182.
G. J. Rieger, Über einige arithmetische Summen, Manuscripta Mathematica, Vol. 7 (1972), pp. 23-34.

Partial sums of A058061.

Cf. A000005, A001222, A076191, A077761.

Accumulate[PrimeOmega[DivisorSigma[0,Range[70]]]] (* Harvey P. Dale, Dec 05 2013 *)

PARI
```
a(n)=sum(i=1,n,bigomega(numdiv(i)))
```

a(n) = n*log(log(n)) + O(n).

a(n) = b * n * log(log(n)) + Sum_{k=0..floor(sqrt(n))} b_k * n/log(n)^k + O(n * exp(-c*sqrt(log(n)))), where b, b_k and c are constants (Heppner, 1974). b = 1 and b_0 = B + C, where B is Mertens's constant (A077761), C = Sum_{k>=2} A076191(k)*P(k) = 0.12861146810484151346..., and P(s) is the prime zeta function. - Amiram Eldar, Jan 15 2024 and Feb 11 2024

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scheme

Scheme

Formula

A055079 Smallest number with exactly n nonprime divisors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A058060 Number of distinct prime factors of d(n), the number of divisors of n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A376886 The number of distinct factors of n of the form p^(k!), where p is a prime and k >= 1, when the factorization is uniquely done using the factorial-base representation of the exponents in the prime factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A057838 Numbers k such that A055079(k) = 2^k.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A064548 Numbers k for which the sum of the binary digits equals the number of prime factors of k + 1 counted with multiplicity.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A371090 Additive with a(p^1) = 1, a(p^e) = a(A276086(e)) for e > 1, where A276086 is the primorial base exp-function.

Views