Integer chemistry III

The $complexity(x)$ of a number $x$ can be defined recursively as follows

$\begin{cases} x & x\leq 5 \\ \min(complexity(x-i)+complexity(i),complexity(x/j)+complexity(j)) & x\geq 5; \: i\leq n ;\: n\equiv 0 (mod j)\\ \end{cases}$ Scroll to the right to view full expression

Basically,the complexity of a number $x$ equals the smaller of the two below values:

1. $complexity(x-i)+complexity(i)$ for some $i<x$ or

2. $complexity(x/j)+complexity(j)$ for some divisor $j$ of $x$

Memoizing the function saves a lot of time since values are saved and aren't recomputed whenever the recursive function is called more than once. In Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

Save = {i:i for i in range(6)}
def Complexity(n):
    if n <= 5:return n
    if n in Save:return Save[n]
    Min=n
    for i in range(2,n):
        Sum = Complexity(n-i)+Complexity(i)
        if Sum < Min:Min = Sum
        if  n%i==0:
            Product = Complexity( n / i ) + Complexity( i )
            if Product < Min:Min = Product
    Save[n]=Min
    return Min       
n = 5
while complexity(n)!=13:
    n += 1
print n 

The answer should be a prime number because at every prime number the complexity of the numbers above it are either less or equal. So in such a way we can get 47 :)

the problem is solvable using dynamic programing (c++ code):

int main(){
int A[1000];
for (int i=0;i<1000;i++){
A[i]=i;
}
for (int i=5;i<300;i++){
for (int j=2;j<sqrt(i)+2;j++){
if (i%j==0&&A[i/j]+A[j]<A[i]){A[i]=A[i/j]+A[j];}
}
for (int j=1;j<i;j++){
if (A[i-j]+j<A[i]){A[i]=A[i-j]+j;}
}
}
for (int i=1;i<200;i++){
cout<<i<<"  "<<A[i]<<endl;
}

Pretty self-explanatory; any way to make a number ends with adding 1 or multiplying two other expressions.

import qualified Data.MemoCombinators as Memo
complexity = Memo.integral c
    where
        c 1 = 1
        c n = minimum $ (1 + complexity (n-1)) : [complexity f + complexity (n `div` f) | f <- [2..n-1], n `mod` f == 0]

main = print $ head $ dropWhile ((/= 13) . complexity) [1..]

I wrote a little script that would spit out the complexity of every number in a sequence of numbers (for example $1$ to $100$ ) and i got comlexity $13$ for $46$ , and indeed it could be writen out like the following:

$46 = 23\times 2 = (11\times 2+1)\times 2 = ((5\times 2+1)\times 2+1)\times 2) = ((1+1+1+1+1)\times (1+1)+1)\times (1+1)+1)\times (1+1))$

So $13$ one's goes into $46$ , yet the 'correct' answer to this question is $47$ , any clarification please?

P.S. after i got it wrong for entering $46$ I tried $47$ by pure luck.

Here's my brute-force solution which also prints the equation:

def possibleCouples(z):
    t=[]
    for i in range(1,z/2+1):
        t+=[[i,z-i,"+"]]
    for i in range(2,int(z*.5)+1):
        if z%i<1:
            t+=[[i,z/i,"*"]]
    return t

def cpst(i):
    if i<2:
        return (1,"1")
    global b
    if not b[i][0]:
        a=possibleCouples(i)
        m=999
        for g,h,f in a:
            j,k = cpst(g),cpst(h)
            if j[0]+k[0] < m:
                m = j[0]+k[0]
                if f == "*":
                    c="("+j[1]+")"+f+"("+k[1]+")"
                else:
                    c=j[1]+f+k[1]
        b[i]=(m,c)
    return b[i]

b=[[0,""]]*999
i=1
while cpst(i)[0]!=13: i+=1

print i,cpst(i)

And the output:

>>> print i,cpst(i)
47 (13, '1+1+(1+1+1)*((1+1+1)*(1+1+1+1+1))')
>>>

By the way,

>>> cpst(46)
(12, '1+(1+1+1)*((1+1+1)*(1+1+1+1+1))')
>>>

You can calculate the complexity of a number based on the complexity of the previous numbers, thereby defining it recursively.

Python solution:

def factor(n):
    """Returns the smallest factor of a number n, except 1 and n"""
    for i in xrange(2,int(n ** (0.5))+1):
        if n % i == 0:
            return i
    return None

data = {0:0, 1:1}
num = 2
while True:
    f = float('inf')
    x = factor(num)
    if x:
        f = data[x] + data[num/x]
    r = min(map(lambda x: data[num-x] + x, xrange(1,num)))
    data[num] = min([f,r])
    if data[num] == 13:
        print num, data[num]
        break
    num += 1

End result: $\boxed{47}$