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,...
1, 2, 3, 7, 14, 26, 52, 104, 201, 379, 751, 1422, 2679, 5068, 9383, 17249, 31285, 57171, 103476, 186921, 333991, 594921, 1044076, 1837839, 3198889, 5561453, 9689270, 16763804, 28909679, 49142265, 83418913
Offset: 1
Examples
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.
Programs
-
Python
from itertools import product 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))) print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Jan 14 2022 -
Python
# faster version for initial segment of sequence (see Comments) def afindn(terms): vset, vpset = {1}, {(1, 1)} print(len(vset), end=", ") for n in range(2, terms+1): newvset, newvpset = set(), set() for v, p in vpset: newvs = [v+n, v+p*(n-1)] newvset.update(newvs) if n != terms: # saves memory for that last term newvpset.update([(newvs[0], n), (newvs[1], p*n)]) vset, vpset = newvset, newvpset print(len(vset), end=", ") afindn(26) # Michael S. Branicky, Jan 14 2022
Extensions
a(17)-a(26) from Wojciech Florek, Feb 27 2018
a(27)-a(31) from Michael S. Branicky, Jan 14 2022
Comments