A317545 Number of multimin factorizations of n.

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 5, 1, 2, 2, 8, 1, 4, 1, 5, 2, 2, 1, 12, 2, 2, 4, 5, 1, 5, 1, 16, 2, 2, 2, 11, 1, 2, 2, 12, 1, 5, 1, 5, 5, 2, 1, 28, 2, 4, 2, 5, 1, 8, 2, 12, 2, 2, 1, 15, 1, 2, 5, 32, 2, 5, 1, 5, 2, 5, 1, 29, 1, 2, 4, 5, 2, 5, 1, 28, 8, 2, 1, 15, 2, 2, 2, 12, 1, 12, 2, 5, 2, 2, 2, 64, 1, 4, 5, 11, 1, 5, 1, 12, 5

Offset

1,4

Comments

A multimin factorizations of n is an ordered factorization of n into factors greater than 1 such that the sequence of minimal primes dividing each factor is weakly increasing.

Links

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

Formula

a(1) = 1; a(n > 1) = Sum_{d|(n/p)} a(d), where p is the smallest prime dividing n.

Example

The a(36) = 11 multimin factorizations:
  (36),
  (2*18), (4*9), (6*6), (12*3), (18*2),
  (2*2*9), (2*6*3), (4*3*3), (6*2*3),
  (2*2*3*3).

Mathematica

a[n_]:=If[n==1, 1, Sum[a[d], {d, Divisors[n/FactorInteger[n][[1, 1]]]}]];
Array[a, 100]

Prog

(PARI) A317545(n) = if(1==n, 1, my(spf = factor(n)[1, 1]); sumdiv(n/spf, d, A317545(d))); \\ Antti Karttunen, Sep 10 2018
(PARI)
memo317545 = Map(); \\ Memoized version.
A317545(n) = if(1==n, 1, if(mapisdefined(memo317545, n), mapget(memo317545, n), my(spf = factor(n)[1, 1], v = sumdiv(n/spf, d, A317545(d))); mapput(memo317545, n, v); (v))); \\ Antti Karttunen, Sep 10 2018

Crossrefs

Cf. A007716, A020639, A034691, A255397, A296560, A300335, A317546.

Sequence in context: A234541 A066389 A077191 * A319002 A050363 A308063

Adjacent sequences: A317542 A317543 A317544 * A317546 A317547 A317548

Keyword

nonn

Author

Gus Wiseman, Jul 31 2018

Extensions

More terms from Antti Karttunen, Sep 10 2018

Status

approved