A299090 Number of "digits" in the binary representation of the multiset of prime factors of n.

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

Offset

1,4

Comments

a(n) is also the binary weight of the largest multiplicity in the multiset of prime factors of n.

Any finite multiset m has a unique binary representation as a finite word bin(m) = s_k..s_1 such that: (1) each "digit" s_i is a finite set, (2) the leading term s_k is nonempty, and (3) m = 1*s_1 + 2*s_2 + 4*s_3 + 8*s_4 + ... + 2^(k-1)*s_k where + is multiset union, 1*S = S as a multiset, and n*S = 1*S + (n-1)*S for n > 1. The word bin(m) can be thought of as a finite 2-adic set. For example,

bin({1,1,1,1,2,2,3,3,3}) = {1}{2,3}{3},

bin({1,1,1,1,1,2,2,2,2}) = {1,2}{}{1},

bin({1,1,1,1,1,2,2,2,3}) = {1}{2}{1,2,3}.

a(n) is the least k such that columns indexed k or greater in A329050 contain no divisors of n. - Peter Munn, Feb 10 2020

Links

Antti Karttunen, Table of n, a(n) for n = 1..65537

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

Formula

a(n) = A070939(A051903(n)), n>1.

If m is a set then bin(m) has only one "digit" m; so a(n) = 1 if n is squarefree.

If m is of the form n*{x} then bin(m) is obtained by listing the binary digits of n and replacing 0 -> {}, 1 -> {x}; so a(p^n) = binary weight of n.

a(n) = A061395(A225546(n)). - Peter Munn, Feb 10 2020

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 1 + Sum_{k>=1} (1 - 1/zeta(2^k)) = 1.47221057635756400916... . - Amiram Eldar, Jan 05 2024

Example

36 has prime factors {2,2,3,3} with binary representation {2,3}{} so a(36) = 2.
Binary representations of the prime multisets of each positive integer begin: {}, {2}, {3}, {2}{}, {5}, {2,3}, {7}, {2}{2}, {3}{}, {2,5}, {11}, {2}{3}, {13}, {2,7}, {3,5}, {2}{}{}.

Mathematica

Table[If[n===1, 0, IntegerLength[Max@@FactorInteger[n][[All, 2]], 2]], {n, 100}]

Prog

(PARI)
A051903(n) = if((1==n), 0, vecmax(factor(n)[, 2]));
A299090(n) = if(1==n, 0, #binary(A051903(n))); \\ Antti Karttunen, Jul 29 2018

Crossrefs

Cf. A001511, A051903, A052409, A070939, A112798, A329050.

Related to A061395 via A225546.

Sequence in context: A096309 A185102 A049419 * A046951 A159631 A368216

Adjacent sequences: A299087 A299088 A299089 * A299091 A299092 A299093

Keyword

nonn,base

Author

Gus Wiseman, Feb 02 2018

Extensions

More terms from Antti Karttunen, Jul 29 2018

Status

approved