cp's OEIS Frontend

A048249 Number of distinct values produced from sums and products of n unity arguments.

%I A048249 #36 Aug 03 2022 10:45:05
%S A048249 1,2,3,4,6,9,11,17,23,30,44,60,80,114,156,212,296,404,556,770,1065,
%T A048249 1463,2032,2795,3889,5364,7422,10300,14229,19722,27391,37892,52599,
%U A048249 73075,101301,140588,195405,271024,376608,523518,726812,1010576,1405013,1952498
%N A048249 Number of distinct values produced from sums and products of n unity arguments.
%C A048249 Values listed calculated by exhaustive search algorithm.
%C A048249 For n+1 operands (n operations) there are (2n)!/((n!)((n+1)!)) possible postfix forms over a single operator. For each such form, there are 2^n ways to assign 2 operators (here, sum and product). Calculate results and eliminate duplicates.
%C A048249 Number of distinct positive integers that can be obtained by iteratively adding or multiplying together parts of an integer partition until only one part remains, starting with 1^n. - _Gus Wiseman_, Sep 29 2018
%H A048249 Alois P. Heinz, <a href="/A048249/b048249.txt">Table of n, a(n) for n = 1..75</a>
%H A048249 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%H A048249 <a href="/index/Fo#4x4">Index entries for similar sequences</a>
%F A048249 Equals partial sum of "number of numbers of complexity n" (A005421). - _Jonathan Vos Post_, Apr 07 2006
%e A048249 a(3)=3 since (in postfix): 111** = 11*1* = 1, 111*+ = 11*1+ = 111+* = 11+1* = 2 and 111++ = 11+1+ = 3. Note that at n=7, the 11 possible values produced are the set {1,2,3,4,5,6,7,8,9,10,12}. This is the first n for which there are "skipped" values in the set.
%p A048249 b:= proc(n) option remember; `if`(n=1, {1}, {seq(seq(seq(
%p A048249      [f+g, f*g][], g=b(n-i)), f=b(i)), i=1..iquo(n, 2))})
%p A048249     end:
%p A048249 a:= n-> nops(b(n)):
%p A048249 seq(a(n), n=1..35);  # _Alois P. Heinz_, May 05 2019
%t A048249 ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];
%t A048249 Table[Length[Select[ReplaceListRepeated[{Array[1&,n]},{{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x+y]],{foe___,x_,mie___,y_,afe___}:>Sort[Append[{foe,mie,afe},x*y]]}],Length[#]==1&]],{n,10}] (* _Gus Wiseman_, Sep 29 2018 *)
%o A048249 (Python)
%o A048249 from functools import cache
%o A048249 @cache
%o A048249 def f(m):
%o A048249     if m == 1: return {1}
%o A048249     out = set()
%o A048249     for j in range(1, m//2+1):
%o A048249         for x in f(j):
%o A048249             for y in f(m-j):
%o A048249                 out.update([x + y, x * y])
%o A048249     return out
%o A048249 def a(n): return len(f(n))
%o A048249 print([a(n) for n in range(1, 40)]) # _Michael S. Branicky_, Aug 03 2022
%Y A048249 Cf. A000792, A005520, A066739, A070960, A201163, A319850, A318949, A319855, A319856, A319909, A319910, A319911.
%K A048249 nonn,nice
%O A048249 1,2
%A A048249 _Tony Bartoletti_
%E A048249 More terms from _David W. Wilson_, Oct 10 2001
%E A048249 a(43)-a(44) from _Alois P. Heinz_, May 05 2019