Complex yet real?

Computer Science Level 4

We call the complexity of an integer $n$ as the least number of 1s required to build the integer $n$ using only additions, multiplications and parentheses.

Let $\mathcal C (n)$ denote the complexity of the integer $n$ . Find the value of $\mathcal C(2016)$ .

Details and Assumptions

As an explicit example, the least number of 1s required to build the integer 6 is 5 because $6 = (1+1)\times(1+1+1)$ and we cannot build the integer 6 with four 1's or less.

The answer is 22.

2 solutions

Arjen Vreugdenhil
Dec 22, 2015

int complexity[] = new int[2017];
complexity[1] = 1;

for (int n = 2; n <= 2016; n++) {
    int best = -1;

    for (int k = 1, l = n-1; k <= l; k++, l--) {
        int addc = complexity[k] + complexity[l];
        if (best < 0 || addc < best) best = addc;
    }

    for (int k = 2; k < n; k++) if (n % k == 0) {
        int l = n/k; if (k > l) break;
        int mulc = complexity[k] + complexity[l];
        if (best < 0 || mulc < best) best = mulc;
    }

    complexity[n] = best;
}

out.println(complexity[2016]);

Output:

Abdelhamid Saadi
Dec 19, 2015

My solution in python 3:

def C(n):
    Cn = [0, 1]
    for j in range(2, n+1):
        a = min(Cn[k] + Cn[j -k] for k in range(1, j//2 + 1 ))
        b = min([Cn[k] + Cn[j//k] for k in range(2, j//2 + 1) if j%k == 0] + [j])
        Cn.append(min(a,b))
    return Cn[n]

"Complex yet real?"
print(C(2016))

Output:

Nice solution.(+1)

But by pen and paper $2016=2^{5} . 3^{2} . 7=2^{5} . 3^{2} . (2 \times 3 +1)$ . Hence $C(2016)=\boxed{22}$ .

EDIT: that was by luck.. here is why.

Mahdi Al-kawaz - 5 years, 5 months ago

Exactly what I did! +1

We actually need to prove the following claim to justify the method in your comment :

Claim: If, for positive integer $a$ , $a=\large\prod\limits_i p_i^{q_i}$ is the unique prime representation of $a$ , then $\mathcal{C}(a)=\sum\limits_iq_i\mathcal{C}(p_i)$ and for any prime $p$ , we have $\mathcal{C}(p)=1+\mathcal{C}(p-1)$ with the obvious initial value $\mathcal{C}(1)=1$ .

Intuitively, this seems to be true and I also verified the above claim to be true for numerous values of $a$ by checking the result given by it with the one given by the posted code, but I can't think of a proper formal proof to the above claim.

Prasun Biswas - 5 years, 5 months ago

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

Isaac Buckley - 5 years, 5 months ago

@Isaac Buckley – Well, I'll be damned!

Prasun Biswas - 5 years, 5 months ago

This is actually a very complex problem (no pun intended).

For eg, why not $\mathcal C (p) = (1 + 1) + \mathcal C (p - 2)$ .

Or by considering your approach, $\mathcal C (p) = 1 + \mathcal C (p - 1)$ ,

what if $p - 1 = x \cdot q$ where $q$ is a large prime again? It can be solved easily with computers but it's a hard job manually.

Arulx Z - 5 years, 5 months ago

@Arulx Z – Because....... this will explain better.

Mahdi Al-kawaz - 5 years, 5 months ago

It's funny that you tried that approach, because I started that way too. Then I realized that the complexity of a slightly smaller number (e.g. 2015) might well be significantly less... So that's where I started coding.

Arjen Vreugdenhil - 5 years, 5 months ago

You need to prove that 22 is the minimum.

Pi Han Goh - 5 years, 5 months ago

Complex yet real?

The answer is 22.

2 solutions

0 pending reports