cp's OEIS Frontend

A138651 Number of distinct values obtained when each of the operators # in the expression 1#2#3#...#n is replaced by + (add) or x (multiply) in all possible ways, for n=1,2,3,...

%I A138651 #13 Jan 15 2022 10:03:07
%S A138651 1,2,3,7,14,26,52,104,201,379,751,1422,2679,5068,9383,17249,31285,
%T A138651 57171,103476,186921,333991,594921,1044076,1837839,3198889,5561453,
%U A138651 9689270,16763804,28909679,49142265,83418913
%N A138651 Number of distinct values obtained when each of the operators # in the expression 1#2#3#...#n is replaced by + (add) or x (multiply) in all possible ways, for n=1,2,3,...
%C A138651 a(n) can be found incrementally by storing pairs (v, p) where v is the value of the expression and p is the product of all terms appearing after the last + operator.  The process starts with (1, 1) and at stage n, each (v, p) maps to (v+n, n), (v-p+p*n, p*n) for operator + and *, respectively. See second Python program. - _Michael S. Branicky_, Jan 14 2022
%e A138651 For n=4, the eight expressions {1+2+3+4,1+2+3x4,1+2x3+4,1+2x3x4,1x2+3+4,1x2+3x4, 1x2x3+4,1x2x3x4} are obtained, with the eight values {10,15,11,25,9,14,10,24} respectively, seven of which are distinct, so a(4)=7.
%o A138651 (Python)
%o A138651 from itertools import product
%o A138651 def a(n): return len(set(eval("1" + "".join(op+str(i) for op, i in zip(ops, range(2, n+1)))) for ops in product("+*", repeat=n-1)))
%o A138651 print([a(n) for n in range(1, 16)]) # _Michael S. Branicky_, Jan 14 2022
%o A138651 (Python) # faster version for initial segment of sequence (see Comments)
%o A138651 def afindn(terms):
%o A138651     vset, vpset = {1}, {(1, 1)}
%o A138651     print(len(vset), end=", ")
%o A138651     for n in range(2, terms+1):
%o A138651         newvset, newvpset = set(), set()
%o A138651         for v, p in vpset:
%o A138651             newvs = [v+n, v+p*(n-1)]
%o A138651             newvset.update(newvs)
%o A138651             if n != terms: # saves memory for that last term
%o A138651                 newvpset.update([(newvs[0], n), (newvs[1], p*n)])
%o A138651         vset, vpset = newvset, newvpset
%o A138651         print(len(vset), end=", ")
%o A138651 afindn(26) # _Michael S. Branicky_, Jan 14 2022
%Y A138651 Cf. A069765, A078389.
%K A138651 nonn,more
%O A138651 1,2
%A A138651 _John W. Layman_, May 15 2008
%E A138651 a(17)-a(26) from _Wojciech Florek_, Feb 27 2018
%E A138651 a(27)-a(31) from _Michael S. Branicky_, Jan 14 2022