A385418 The number of unordered factorizations of n into powers of primes of the form p^(2^k-1) where p is prime and k >= 0.

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

Offset: 1

Author

Amiram Eldar, Jun 28 2025

Keywords

• nonn
• easy
• mult

Comments

First differs from A304327 and A368248 at n = 64.

First differs from A061704 and A362852 at n = 128.

The number of unordered factorizations of n into powers of primes in A036537.

Examples

			  n | a(n) | factorizations
  --+------+-------------------------------------------------------------------
  2 |    8 | 2 * 2 * 2, 2^3
  3 |   64 | 2 * 2 * 2 * 2 * 2 * 2, 2 * 2 * 2 * 2^3, 2^3 * 2^3
  4 |  128 | 2 * 2 * 2 * 2 * 2 * 2 * 2, 2 * 2 * 2 * 2 * 2^3, 2 * 2^3 * 2^3, 2^7
		

Links

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

Crossrefs

Cf. A000929, A036537.

Cf. A061704, A304327, A362852, A368248.

Similar sequences: A000688, A046951, A050361, A050377, A188581, A188585, A322885, A370256, A384912, A384913, A384914, A384915, A384916.

Programs

Mathematica

T[n_, k_] := T[n, k] = If[k <= n, T[n - k, k] + T[n, 2*k + 1], Boole[n == 0]]; f[p_, e_] := T[e, 1];
a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100]

PARI

t(n, k) = if(k <= n, t(n-k, k) + t(n, 2*k+1), n == 0);
a(n) = vecprod(apply(x -> t(x, 1), factor(n)[,2]));

Formula

Multiplicative with a(p^e) = A000929(e).

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Product_{k>=2} zeta(2^k-1) = 1.21213028603089660618... .