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

%I #36 Aug 03 2022 10:45:05

%S 1,2,3,4,6,9,11,17,23,30,44,60,80,114,156,212,296,404,556,770,1065,

%T 1463,2032,2795,3889,5364,7422,10300,14229,19722,27391,37892,52599,

%U 73075,101301,140588,195405,271024,376608,523518,726812,1010576,1405013,1952498

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

%C Values listed calculated by exhaustive search algorithm.

%C 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 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 Alois P. Heinz, <a href="/A048249/b048249.txt">Table of n, a(n) for n = 1..75</a>

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%H <a href="/index/Fo#4x4">Index entries for similar sequences</a>

%F Equals partial sum of "number of numbers of complexity n" (A005421). - _Jonathan Vos Post_, Apr 07 2006

%e 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 b:= proc(n) option remember; `if`(n=1, {1}, {seq(seq(seq(

%p [f+g, f*g][], g=b(n-i)), f=b(i)), i=1..iquo(n, 2))})

%p end:

%p a:= n-> nops(b(n)):

%p seq(a(n), n=1..35); # _Alois P. Heinz_, May 05 2019

%t ReplaceListRepeated[forms_,rerules_]:=Union[Flatten[FixedPointList[Function[pre,Union[Flatten[ReplaceList[#,rerules]&/@pre,1]]],forms],1]];

%t 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 (Python)

%o from functools import cache

%o @cache

%o def f(m):

%o if m == 1: return {1}

%o out = set()

%o for j in range(1, m//2+1):

%o for x in f(j):

%o for y in f(m-j):

%o out.update([x + y, x * y])

%o return out

%o def a(n): return len(f(n))

%o print([a(n) for n in range(1, 40)]) # _Michael S. Branicky_, Aug 03 2022

%Y Cf. A000792, A005520, A066739, A070960, A201163, A319850, A318949, A319855, A319856, A319909, A319910, A319911.

%K nonn,nice

%O 1,2

%A _Tony Bartoletti_

%E More terms from _David W. Wilson_, Oct 10 2001

%E a(43)-a(44) from _Alois P. Heinz_, May 05 2019