|
|
A048249
|
|
Number of distinct values produced from sums and products of n unity arguments.
|
|
20
|
|
|
1, 2, 3, 4, 6, 9, 11, 17, 23, 30, 44, 60, 80, 114, 156, 212, 296, 404, 556, 770, 1065, 1463, 2032, 2795, 3889, 5364, 7422, 10300, 14229, 19722, 27391, 37892, 52599, 73075, 101301, 140588, 195405, 271024, 376608, 523518, 726812, 1010576, 1405013, 1952498
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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)):
|
|
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))
|
|
CROSSREFS
|
Cf. A000792, A005520, A066739, A070960, A201163, A319850, A318949, A319855, A319856, A319909, A319910, A319911.
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|