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

Author

Gus Wiseman, Feb 02 2018

Keywords

• nonn
• base

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

Examples

			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}{}{}.
		

Links

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

Crossrefs

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

Related to A061395 via A225546.

Programs

Mathematica

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

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

Python

from sympy import factorint
def A299090(n): return max(factorint(n).values(),default=0).bit_length() # Chai Wah Wu, Apr 11 2025

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

Extensions

More terms from Antti Karttunen, Jul 29 2018