Return to Answer

First of all, why do you answer multi queries? The problem asks only to find the summation of sg from 1 to 150.

The real bottleneck in your solution is this function:

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

its growth rate is very big and the loop is unbounded. If you tried to bound it to 100 for example you will find it becomes too fast.

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        if p == 100:
            break
        p=p+1

This function will not give us the right answer for sure but it tells us that this function is the bottleneck and make the code too slow.

The real problem is how to calculate g(i) fast. I will give you some ideas and hints:

g(n) is the sum of digits that give us n and form the minimum possible number and at the same time can be represented in the form of $$A1!+A2!+..+Ax!$$ for example: (5 = 1 + 2 + 2) -> ( 122 = 120 + 2 ) -> ( 5! = 120 and 2! = 2 ) so ( 2! + 5! ) gives us 5 i.e. g(5) = 25

and as f(n) calculates the factorial of each digit so we have factorial of digits from 1 to 9 only.

If we calculated the different combinations of sums of factorial digits from 1 to 9 (I think we will need some Dynamic Programming here to make this fast enough) and stored the minimum of them (i.e. the minimum number they can form by adding them) in an array for each digit from 1 to 150. then we will loop throw the array from 1 to 150 and sum .. this will be too fast.

I think this is enough start to go and invest some efforts in this path.

First of all, why do you answer multi queries? The problem asks only to find the summation of sg from 1 to 150.

The real bottleneck in your solution is this function:

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

its growth rate is very big and the loop is unbounded. If you tried to bound it to 100 for example you will find it becomes too fast.

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        if p == 100:
            break
        p=p+1

This function will not give us the right answer for sure but it tells us that this function is the bottleneck and make the code too slow.

The real problem is how to calculate g(i) fast. I will give you some ideas and hints:

g(n) is the sum of digits that give us n and form the minimum possible number and at the same time can be represented in the form of $$A1!+A2!+..+Ax!$$ for example: (5 = 1 + 2 + 2) -> ( 122 = 120 + 2 ) -> ( 5! = 120 and 2! = 2 ) so ( 2! + 5! ) gives us 5 i.e. g(5) = 25

and as f(n) calculates the factorial of each digit so we have factorial of digits from 1 to 9 only.

If we calculated the different combinations of sums of factorial digits from 1 to 9 (I think we can make something faster but this is just a start and you can find some algorithm to follow instead of trying all the combinations which will also be too slow) and store the minimum of them (i.e. the minimum number they can form by adding them) in an array for each digit from 1 to 150. then we will loop throw the array from 1 to 150 and sum .. this will be too fast.

I think this is enough to start going and invest some effort in this path.

I already solved this problem 2 years before. But I will NEVER share the solution and I ask everyone not to share the solutions of projecteuler problems because this is against the conditions of the website. If you can't solve it. You should give it some time or learn some needed topics but never ask anyone for the solution. at most, you can take some hints to help you work on the problems.

This moment really worth and by taking other people solution you will lose this moment

First of all, why do you answer multi queries? The problem asks only to find the summation of sg from 1 to 150.

The real bottleneck in your solution is this function:

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

its growth rate is very big and the loop is unbounded. If you tried to bound it to 100 for example you will find it becomes too fast.

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        if p == 100:
            break
        p=p+1

This function will not give us the right answer for sure but it tells us that this function is the bottleneck and make the code too slow.

The real problem is how to calculate g(i) fast. I will give you some ideas and hints:

g(n) is the sum of digits that give us n for and form the minimum possible number and at the same time can be represented in the form of $$A1!+A2!+..+Ax!$$ for example: 5 = 1 + 2 + 2 -> 120 + 2 -> 5! = 120 and 2! = 2 so 2!+5! gives us 5 i.e. g(5) = 25

and as f(n) calculates the factorial of each digit so we have factorial of digits from 1 to 9 only.

If we calculated the different combinations of sums of factorial digits from 1 to 9 and stored the minimum of them (i.e. the minimum number they can form by adding them) in an array for each digit from 1 to 150. then we will loop throw the array from 1 to 150 and sum .. this will be too fast.

I think this is enough start to go and invest some efforts in this path.

First of all, why do you answer multi queries? The problem asks only to find the summation of sg from 1 to 150.

The real bottleneck in your solution is this function:

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

its growth rate is very big and the loop is unbounded. If you tried to bound it to 100 for example you will find it becomes too fast.

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        if p == 100:
            break
        p=p+1

This function will not give us the right answer for sure but it tells us that this function is the bottleneck and make the code too slow.

The real problem is how to calculate g(i) fast. I will give you some ideas and hints:

g(n) is the sum of digits that give us n and form the minimum possible number and at the same time can be represented in the form of $$A1!+A2!+..+Ax!$$ for example: (5 = 1 + 2 + 2) -> ( 122 = 120 + 2 ) -> ( 5! = 120 and 2! = 2 ) so ( 2! + 5! ) gives us 5 i.e. g(5) = 25

and as f(n) calculates the factorial of each digit so we have factorial of digits from 1 to 9 only.

If we calculated the different combinations of sums of factorial digits from 1 to 9 (I think we will need some Dynamic Programming here to make this fast enough) and stored the minimum of them (i.e. the minimum number they can form by adding them) in an array for each digit from 1 to 150. then we will loop throw the array from 1 to 150 and sum .. this will be too fast.

I think this is enough start to go and invest some efforts in this path.

First of all, why do you answer multi queries? The problem asks only to find the summation of sg from 1 to 150.

The real bottleneck in your solution is this function:

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

its growth rate is very big and the loop is unbounded. If you tried to bound it to 100 for example you will find the becomes too fast.

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        if p == 100:
            break
        p=p+1

This function will not give us the right answer for sure but it tells us that this function is the bottleneck and make the code too slow.

The real problem is how to calculate g(i) fast. I will give you some ideas and hints:

g(n) is the sum of digits that give us n for and form the minimum possible number and at the same time can be represented in the form of $$A1!+A2!+..+Ax!$$ for example: 5 = 1 + 2 + 2 -> 120 + 2 -> 5! = 120 and 2! = 2 so 2!+5! gives us 5 i.e. g(5) = 25

and as f(n) calculates the factorial of each digit so we have factorial of digits from 1 to 9 only.

If we caluclated the differnet combination of sums of factorial digits from 1 to 9 and stored the minumum of them in an array for each digit from 1 to 150. then we will loop throw the array form 1 to 150 and sum .. this will be too fast.

I think this is enough start to go and invest some efforts in this path.

First of all, why do you answer multi queries? The problem asks only to find the summation of sg from 1 to 150.

The real bottleneck in your solution is this function:

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        p=p+1

its growth rate is very big and the loop is unbounded. If you tried to bound it to 100 for example you will find it becomes too fast.

def g(i):
    p=1
    while True:
        if sf(p)==i:
            return p
        if p == 100:
            break
        p=p+1

This function will not give us the right answer for sure but it tells us that this function is the bottleneck and make the code too slow.

The real problem is how to calculate g(i) fast. I will give you some ideas and hints:

g(n) is the sum of digits that give us n for and form the minimum possible number and at the same time can be represented in the form of $$A1!+A2!+..+Ax!$$ for example: 5 = 1 + 2 + 2 -> 120 + 2 -> 5! = 120 and 2! = 2 so 2!+5! gives us 5 i.e. g(5) = 25

and as f(n) calculates the factorial of each digit so we have factorial of digits from 1 to 9 only.

If we calculated the different combinations of sums of factorial digits from 1 to 9 and stored the minimum of them (i.e. the minimum number they can form by adding them) in an array for each digit from 1 to 150. then we will loop throw the array from 1 to 150 and sum .. this will be too fast.

I think this is enough start to go and invest some efforts in this path.