OFFSET
1,2
COMMENTS
Values listed calculated by exhaustive search algorithm.
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.
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
LINKS
FORMULA
Equals partial sum of "number of numbers of complexity n" (A005421). - Jonathan Vos Post, Apr 07 2006
EXAMPLE
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.
MAPLE
b:= proc(n) option remember; `if`(n=1, {1}, {seq(seq(seq(
[f+g, f*g][], g=b(n-i)), f=b(i)), i=1..iquo(n, 2))})
end:
a:= n-> nops(b(n)):
seq(a(n), n=1..35); # Alois P. Heinz, May 05 2019
MATHEMATICA
ReplaceListRepeated[forms_, rerules_]:=Union[Flatten[FixedPointList[Function[pre, Union[Flatten[ReplaceList[#, rerules]&/@pre, 1]]], forms], 1]];
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 *)
PROG
(Python)
from functools import cache
@cache
def f(m):
if m == 1: return {1}
out = set()
for j in range(1, m//2+1):
for x in f(j):
for y in f(m-j):
out.update([x + y, x * y])
return out
def a(n): return len(f(n))
print([a(n) for n in range(1, 40)]) # Michael S. Branicky, Aug 03 2022
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
More terms from David W. Wilson, Oct 10 2001
a(43)-a(44) from Alois P. Heinz, May 05 2019
STATUS
approved