# Golfing the complexity with subtraction

The Mahler-Popken complexity, $$\C(N)\$$, of a positive integer, $$\N\$$, is the smallest number of ones ($$\1\$$) that can be used to form $$\N\$$ in a mathematical expression using only the integer* $$\1\$$ along with multiplication, addition, and parentheses.

Here are some expressions for $$\N=6\$$, $$\N=11\$$, and $$\N=47\$$ with the fewset possible ones:

$$6=(1+1+1)\times(1+1)$$ $$11=(1+1+1+1+1)\times(1+1)+1$$ $$47=(1+1+1+1+1)\times(1+1+1)\times(1+1+1)+1+1$$ $$94=((1+1+1+1+1)\times(1+1+1)\times(1+1+1)+1+1)\times(1+1)$$

Counting the ones we see that $$\C(6)=5\$$, $$\C(11)=8\$$, $$\C(47)=13\$$, and $$\C(94)=15\$$.
* Note that concatenation is not available so $$\C(11) \neq 2\$$.

This is OEIS: A005245.

Some numbers may be formed using fewer ones by also allowing the use of subtraction, for example:

$$47=(1+1+1+1)\times(1+1+1+1)\times(1+1+1)-1$$

uses $$\12\$$ ones which is fewer than $$\C(47)=13\$$; and

$$94=((1+1+1+1)\times(1+1+1+1)\times(1+1+1)-1)\times(1+1)$$

uses $$\14\$$ ones which is fewer than $$\C(94)=15\$$.

This is OEIS: A253177:

23, 47, 53, 59, 69, 71, 89, 94, 106, 107, 134, 141, 142, 143, 159, 161, 167, 177, ...

This is so attempt to do so in as few bytes of code as possible in your language of choice.

Standard I/O rules apply. At the time of posting these are:

• Indexing: Allowed are both $$\0\$$- and $$\1\$$-based indexing, and the following rules can be applied with both these types of indexing.
• Format: The answers can use one of the following input/output methods:
• Given some index $$\n\$$ it can return the $$\n\$$-th entry of the list.
• Given some index $$\n\$$ it can return all entries up to the $$\n\$$th one in the sequence.
• Without taking any index, it can output all entries by e.g. ...
• ...printing them one by one (potentially infinitely) or...
• ...returning a list (lazy if the sequence is infinite) or...
• ...returning a generator that represents the whole sequence.
• Related: Integer Complexity May 10 at 20:24
• Combo Class video May 10 at 20:27
• Example where it's not $$.*$$x$$.*$$(\+1|-1)* pattern?
– l4m2
May 11 at 6:22
• @l4m2 I have no example that is not a recursive form of that pattern, but I imagine some (possibly very large!) number may exist where one subtracts six at the end using five ones. May 11 at 18:36
• @l4m2 Here are three candidates for such an example: n = 7224834, 9339114, 10780554. Each of these n has the property that each of n, n+1, ..., n+5 is a one-digit number times a prime, while n=6 is highly composite. Not a guarantee of course but maybe worth checking.... May 12 at 13:35

# JavaScript (ES12), 180 bytes

-1 thanks to Mukundan314

This was inspired by the Python code provided on A091333. Some optimizations borrowed from Mukundan314's answer.

Prints the sequence indefinitely.

g=n=>g[n*s]||=new Set((h=i=>--i?[h(i),[...g(i)].map(x=>[...g(n-i)].map(y=>[x+y,x*y]))].flat(3):[1,-s])(n))
for(i=1;j=s=1;g(j,s=-1).has(i)||console.log(i),i++)while(!g(j).has(i))j++

Attempt This Online! (+7 bytes to limit the output range so that the page doesn't hang)

# JavaScript (V8), 112 bytes

for(k=9;f=(n,i=n|=0)=>i-->3?Math.min(f(n,i),F(n/i)+F(i)+F(n%i),1/k+F(n/i+1)+F(i)+F(i-n%i)):n;)F(++k)%1&&print(k)

Try it online!

-1 Byte from Arnauld

The tio header saves states to makes it faster

NB: This answer is likely incorrect, as oeis suggests a stronger conclusion than that I didn't cover all patterns:

Guy asks if a(p) = a(p-1) + 1 for prime p. Martin Fuller found the least counterexample p = 353942783 in 2008

• @Arnauld Is it proven that needn't 10 subtractions?
– l4m2
May 11 at 2:01
• Nah, of course not. My bad. May 11 at 7:45
• That said, is $1/k$ really safe? (We have $\lim\sum_{k=1}^\infty 1/k=\infty$, so a sub-sequence of this may diverge as well.) May 11 at 10:47
• @Arnauld, there can be at most k - 1 subtractions. If there are more, it would imply that there are more than k ones, which is certainly not the most optimal way to represent it. May 11 at 14:46

# Python 3, 165 159 158 156 155 bytes

-6 bytes thanks to @xnor

Based on the Python code provided in A091333.

f=lambda n:{*sum([[a+b,a*b]for i in range(1,n)for a in f(i)for b in f(n-i)],[1,s])}
i=1
while s:=-(j:=1):
while{i}-f(j):j+=1
s=1;{i}&f(j)or print(i);i+=1

Attempt This Online! (Includes a header to cache f. Without this cache, only the first term is printed on ATO. Locally, I managed to compute up to 6 terms in 10 minutes using PyPy)

# Python 3, 128 bytes

Port of @l4m2's answer; so this is likely incorrect

f=lambda x:min([x]+[min(int(f(x//i+1)+f(i-x%i))+.1,f(x//i)+f(x%i))+f(i)for i in range(2,x)])
i=0
while 1:f(i)%1and print(i);i+=1

Try it online!

• <s>What does the +.1 in your code do?</s> Your code fails with #subtractions >10 right?
– Sny
May 11 at 9:49
• @Sny, no it doesn't since we cast to int before adding .1; so decimal part will never exceed .1 May 11 at 11:05
• It looks like you can write while not{i}&f(j,1) as while{i}-f(j,1)
– xnor
May 12 at 4:30
• Also, I think a-b*s suffices, since this is just a when s==0 which is harmless
– xnor
May 12 at 4:40

# Python 3.8 (pre-release), 214 201 (boolean magik) bytes

a=lambda x,f,t=0:x<2or(t if(t:=x if t<1else t)<2else min([a(x-z,f,t-1)+1for z in range(1,f,-2)]+[x if x%i else a(i,f,t-1)+a(x//i,f,t-1)for i in range(2,x)]))
x=0
while 1:x+=1;a(x,0)>a(x,-2)and print(x)

Try it online!

# Ruby, 125 bytes

f=->*r{g=->n{n<6?n:(2..n**0.5).map{|c|g[c]+r.map{|z|g[n/c+z]+g[[n%c,c-n%c][z]]}.min}.min}}
1.step{|x|f[0][x]>f[0,1][x]&&p(x)}

Try it online!

For n = 0..5, the complexity of n is n.

For any number n>5, the complexity f(n) without using subtractions is the minimum of f(i)+f(n/i)+f(n%i) on i = 2..sqrt(n).

If we include subtraction, we have to consider the minimum of f(i)+f(n/i)+f(n%i) and f(i)+f(n/i+1)+f(i-n%i).

# Charcoal, 94 bytes

Ｎθ→≔⦃¹ⅈ⦄η≔ΦηιζＷ‹Ｌυθ«→Ｆ²«≔⎇κζηεＦ⁻ΣＥεΣＥ⌕Ａε⁻ⅈλ…⟦⁺μν×μν↔⁻μν⟧⁺²κＥεμ§≔ελⅈ»≔Φ⌊⁻⊕ＥηλＥηλ∧κ›§ηκ§ζκυ»Ｉ…υθ

Attempt This Online! Link is to verbose version of code. Outputs the first n terms. Explanation: Also based on the Python code provided in A091333.

Ｎθ

Input n.

Start by considering those N where A005245(N)=1 and A091333(N)=1.

≔⦃¹ⅈ⦄η≔Φηιζ

Create dictionaries mapping N to A005245(N) and A091333(N) where those values do not exceed 1.

Ｗ‹Ｌυθ«

Repeat until enough terms have been found.

Consider the next target value for A005245(N) and A091333(N).

Ｆ²«≔⎇κζηε

Loop over both the A005245(N) and A091333(N) dictionaries.

Ｆ⁻ΣＥεΣＥ⌕Ａε⁻ⅈλ…⟦⁺μν×μν↔⁻μν⟧⁺²κＥεμ

Map over all the existing entries in the dictionary, finding those matching entries whose sum gives the new target value, and form the sum and product, and for A091333, the absolute difference, but remove all the results that already have entries in the dictionary.

§≔ελⅈ

Store each newly found term with the target value.

»≔Φ⌊⁻⊕ＥηλＥηλ∧κ›§ηκ§ζκυ

Find the entries where A005425(N)>A091333(N), but only up to the first hole in A005425(N). It might not be necessary to limit the search to the first hole but any bytes saved by doing so would be lost due to having to sort the results so that the first n could be output.

Ｉ…υθ

Output the first n entries where A005425(N)>A091333(N).

76 68 bytes if @GB's algorithm is correct:

ＮθＦ⁶⊞υ⟦ιι⟧Ｗ∧‹ＬΦυ↨κ±¹θＬυ⊞υＥ²⌊Ｅ⁺±…²∧κι…²ιΣＥ↔⟦μ÷ιμ﹪ιμ⟧§§υξκＩ…ΦＬυ↨§υι±¹θ

Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation: Uses dynamic programming rather than recursion.

Ｎθ

Input n.

Ｆ⁶⊞υ⟦ιι⟧

Both A005425(N) and A091333(N) equal N for N<6.

Ｗ∧‹ＬΦυ↨κ±¹θＬυ

Repeat until enough terms have been found, but also capture the next N in a temporary variable.

⊞υＥ²⌊Ｅ⁺±…²∧κι…²ιΣＥ↔⟦μ÷ιμ﹪ιμ⟧§§υξκ

Map over both both A005425(N) and A091333(N), mapping over the positive range from 2 to N for A005425(N) and both the positive and negative ranges for A091333(N), taking the minimum of f(abs(i))+f(abs(N//i))+f(abs(N%i)) over all the values, and push both the results to the predefined empty list.

Ｉ…ΦＬυ↨§υι±¹θ

Get the indices of the first n terms where A005425(N)>A091333(N).