A331591 a(n) is the number of distinct prime factors of A225546(n), or equally, number of distinct prime factors of A293442(n).

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

Offset: 1

Author

Antti Karttunen and Peter Munn, Jan 21 2020

Keywords

• nonn

Comments

a(n) is the number of terms in the unique factorization of n into powers of squarefree numbers with distinct exponents that are powers of 2. See A329332 for a description of the relationship between this factorization, canonical (prime power) factorization and A225546.

The result depends only on the prime signature of n.

a(n) is the number of distinct bit-positions where there is a 1-bit in the binary representation of an exponent in the prime factorization of n. - Antti Karttunen, Feb 05 2020

The first 3 is a(128) = a(2^1 * 2^2 * 2^4) = 3 and in general each m occurs first at position 2^(2^m-1) = A058891(m+1). - Peter Munn, Mar 07 2022

Examples

			From _Peter Munn_, Jan 28 2020: (Start)
The factorization of 6 into powers of squarefree numbers with distinct exponents that are powers of 2 is 6 = 6^(2^0) = 6^1, which has 1 term. So a(6) = 1.
Similarly, 40 = 10^(2^0) * 2^(2^1) = 10^1 * 2^2 = 10 * 4, which has 2 terms. So a(40) = 2.
Similarly, 320 = 5^(2^0) * 2^(2^1) * 2^(2^2) = 5^1 * 2^2 * 2^4 = 5 * 4 * 16, which has 3 terms. So a(320) = 3.
10^100 (a googol) factorizes in this way as 10^4 * 10^32 * 10^64. So a(10^100) = 3.
(End)
		

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. A000120, A005117, A048675, A225546, A267116, A293442, A293447, A299090, A329332, A337533, A337534.

Sequences with related definitions: A001221, A331309, A331592, A331593, A331740.

Positions of records: A058891.

Positions of 1's: A340682.

Sequences used to express relationships between the terms: A007913, A008833, A059796, A331590.

Programs

Mathematica

Array[PrimeNu@ If[# == 1, 1, Times @@ Flatten@ Map[Function[{p, e}, Map[Prime[Log2@ # + 1]^(2^(PrimePi@ p - 1)) &, DeleteCases[NumberExpand[e, 2], 0]]] @@ # &, FactorInteger[#]]] &, 105] (* Michael De Vlieger, Jan 24 2020 *)
f[e_] := Position[Reverse[IntegerDigits[e, 2]], 1] // Flatten; a[n_] := CountDistinct[Flatten[f /@ FactorInteger[n][[;; , 2]]]]; a[1] = 0; Array[a, 100] (* Amiram Eldar, Dec 23 2023 *)

PARI

A331591(n) = if(1==n,0,my(f=factor(n),u=#binary(vecmax(f[, 2])),xs=vector(u),m=1,e); for(i=1,u,for(k=1,#f~, if(bitand(f[k,2],m),xs[i]++)); m<<=1); #select(x -> (x>0),xs));

PARI

A331591(n) = if(1==n, 0, hammingweight(fold(bitor, factor(n)[, 2]))); \\ Antti Karttunen, Feb 05 2020

PARI

A331591(n) = if(n==1, 0, (core(n)>1) + A331591(core(n,1)[2])) \\ Peter Munn, Mar 08 2022

Formula

a(n) = A001221(A293442(n)) = A001221(A225546(n)).

From Peter Munn, Jan 28 2020: (Start)

a(n) = A000120(A267116(n)).

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

For m >= 2, a(A005117(m)) = 1.

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

(End)

a(n) <= A331740(n) <= A048675(n) <= A293447(n). - Antti Karttunen, Feb 05 2020

From Peter Munn, Mar 07 2022: (Start)

a(n) <= A299090(n).

a(A337533(n)) = A299090(A337533(n)).

a(A337534(n)) < A299090(A337534(n)).

max(a(n), a(k)) <= a(A059796(n, k)) = a(A331590(n, k)) <= a(n) + a(k).

(End)