A341866 The cardinality of the smallest (nontrivial, except for prime n) multiset of positive integers whose product and sum equal n.

1, 1, 1, 2, 1, 3, 1, 4, 5, 5, 1, 6, 1, 7, 9, 8, 1, 9, 1, 10, 13, 11, 1, 12, 17, 13, 17, 14, 1, 15, 1, 16, 21, 17, 25, 18, 1, 19, 25, 20, 1, 21, 1, 22, 29, 23, 1, 24, 37, 25, 33, 26, 1, 27, 41, 28, 37, 29, 1, 30, 1, 31, 41, 32

Offset: 1

Author

Nathaniel Gregg, Feb 22 2021

Keywords

• nonn

Comments

The smallest set is obtained by taking the largest such multiset (A341865(n)) and replacing the largest proper subset that is also a product-sum multiset with its product. A singleton would always be the smallest product-sum multiset, so those are excluded except for prime n where no nontrivial multisets exist.

Examples

			For n = 12, the set of size a(n) = 6 is {1,1,1,1,2,6}.
		

Crossrefs

Cf. A104173, A033178, A033179, A341865.

Equals A330492 + 1. - Hugo Pfoertner, Feb 23 2021

Programs

PARI

a(n) = if (n==1, 1, my(p=vecmin(factor(n)[,1])); (n/p-1)*(p-1) + 1); \\ Michel Marcus, Feb 26 2021

Formula

a(n) = (n/p - 1)*(p-1) + 1, where p is the smallest factor of n.

a(n) = A341865(n) - A341865(n/p) + 1, where p is the smallest prime factor of n.