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,2

Comments

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

Links

Table of n, a(n) for n=1..31.

Example

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.

Prog

(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

Crossrefs

Cf. A069765, A078389.

Sequence in context: A027957 A300569 A054194 * A131300 A333342 A078043

Adjacent sequences: A138648 A138649 A138650 * A138652 A138653 A138654

Keyword

nonn,more

Author

John W. Layman, May 15 2008

Extensions

a(17)-a(26) from Wojciech Florek, Feb 27 2018

a(27)-a(31) from Michael S. Branicky, Jan 14 2022

Status

approved