A348083 Number of positive numbers that can be built with n ones using +, -, and *, and require at least n ones.

1, 1, 1, 1, 2, 3, 2, 6, 6, 8, 13, 18, 21, 35, 45, 61, 90, 121, 162, 241, 323, 450, 638, 865, 1233, 1698, 2349, 3315, 4592, 6382, 8970, 12421, 17351, 24320, 33714, 47218, 65978, 91784, 128177, 179807, 249689, 349549, 489341, 681468, 953769, 1334490, 1860641, 2606043, 3643618, 5086481, 7124229, 9960420

Offset: 1

Author

Glen Whitney, Sep 27 2021

Keywords

• nonn

Comments

a(n+1)/a(n) appears from the values through n=63 to be oscillating in a narrowing range around 7/5.

Examples

			For n=5, there are two numbers whose minimal expression using 1,+,-, and * uses five ones: 5 = 1+1+1+1+1 and 6 = (1+1)*(1+1+1), so a(5) = 2.
For n=10, there are eight numbers whose minimal expression uses ten ones: 22 = 3(2*3+1)+1, 23 = 2*2*2*3-1, 25 = 5*5, 26 = 3*3*3-1, 28 = 3*3*3+1, 30 = 2*3*5, 32 = 2*2*2*2*2, and 36 = 2*2*3*3. We use numbers k=1..5 in these expressions because each takes k ones to express. Note that n=10 is also the least n for which a(n) differs from A005421(n), which counts the solutions to A005245(k) = n.
		

Links

• Glen Whitney, Table of n, a(n) for n = 1..64 (This file produced with the same C code that generated A348069, simply with division eliminated from the loop over operators.)

Crossrefs

Cf. A005421, A091333, A005245.

Programs

Python

from functools import cache
@cache
def f(m):
    if m == 0: return set()
    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])
                if x != y: out.add(abs(x-y))
    return list(out)
def a(n): return len(f(n)) - len(f(n-1))
print([a(n) for n in range(1, 33)]) # Michael S. Branicky, Sep 27 2021

Formula

a(n) = |{k : A091333(k) = n}|.