%I #28 Jan 30 2020 08:43:20
%S 0,0,0,0,0,0,0,0,0,0,0,1,2,4,4,6,7,7,9,10,11,12,13,14,15,16,17,18,19,
%T 20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,
%U 43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74
%N A triple of positive integers (n,p,k) is admissible if there exist at least two different multisets of k positive integers, {x_1,x_2,...,x_k} and {y_1,y_2,...,y_k}, such that x_1+x_2+...+x_k=y_1+y_2+...+y_k = n and x_1x_2...x_k = y_1y_2...y_k = p. For each n, let A(n)={k:(n,p,k) is admissible for some p}, and let a(n) = |A(n)|.
%C John Conway proposed an interesting math puzzle in the 1960s, which is now generally known as "Conway's wizard problem." Here is the problem.
%C Last night I sat behind two wizards on a bus and overheard the following:
%C Blue Wizard: I have a positive integer number of children, whose ages are positive integers. The sum of their ages is the number of this bus, while the product is my own age.
%C Red Wizard: How interesting! Perhaps if you told me your age and the number of your children, I could work out their individual ages?
%C Blue Wizard: No, you could not.
%C Red Wizard: Aha! At last, I know how old you are!
%C Apparently the Red Wizard had been trying to determine the Blue Wizard's age for some time. Now, what was the number of the bus?
%C This problem posed by Conway looks at different multisets that correspond to the same ordered triple, which motivated the study of this sequence.
%H Jay Bennett, <a href="https://www.popularmechanics.com/science/math/a27415/riddle-of-the-week-34-two-wizards-ride-a-bus/">Riddle of the week #34: Two wizards ride a bus</a>, Popular Mechanics. Hearst Communications, Inc., 4 Aug. 2017. 12 Jun. 2018 Accessed.
%H John B. Kelly, <a href="http://dx.doi.org/10.1090/S0002-9939-1964-0168542-2">Partitions with equal products</a>, Proc. Amer. Math. Soc. 15 (1964), 987-990.
%H Tanya Khovanova, <a href="http://arxiv.org/abs/1210.5460">Conway's Wizards</a>, arXiv:1210.5460 [math.HO], 2012.
%F a(n) = 0 for 1 <= n <= 11, a(12) = 1, a(13) = 2, a(14) = 4, a(15) = 4, a(16) = 6, a(17) = 7, a(18) = 7, and a(n) = n - 10 for n >= 19.
%e For n = 3, the only partitions of 3 are {3}, {1,2}, and {1,1,1}. Hence, there is no admissible triple (3,p,k).
%e For n = 4, the only partitions of 4 are {4}, {1,3}, {2,2},{1,1,2}, and {1,1,1,1}. Hence, there is no admissible triple (4,p,k).
%e For n = 12, the only admissible triple (12,p,k) is when p = 48 and k = 4. This is achieved by the following multisets: {1,3,4,4} and {2,2,2,6}. Thus a(12) = 1.
%t Table[Count[
%t Table[intpart = IntegerPartitions[sum, {n}];
%t DuplicateFreeQ[
%t Table[Product[intpart[[i]][[j]], {j, n}], {i,
%t Length[intpart]}]], {n, sum}], False], {sum,50}]
%Y Cf. A060277, A316946.
%K nonn,easy
%O 1,13
%A _Byungchul Cha_, _Adam Claman_, _Joshua Harrington_, _Ziyu Liu_, _Barbara Maldonado_, _Alexander M. Miller_, _Ann Palma_, _Wing Hong Tony Wong_, _Hongkwon V. Yi_, Jul 20 2018