Number's Persistence

We can write some Python code to solve this via brute force in about $0.6$ seconds.

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

def product_digits(n):
    total = 1
    for digit in str(n):
        total *= int(digit)
    return total

def persistence(n):
    if len(str(n)) == 1:
        return 0
    else:
        return 1 + persistence(product_digits(n))

success = False
n = 1
while success == False:
    if persistence(n) == 7:
        print n
        success = True
    else:
        n +=1 

While this works, there may be better ways to approach this computationally. For example, we might want to use memoization to avoid making the same computations over and over. How much would this improve our runtime? What else can we do to improve this solution in terms of either speed or memory used?

My solution avoids re-computation via memoizaiton. I imagine a 'classic DP' solution is possible.

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

I = {str(i):i for i in range(10)}
Table = {}

def persist( n ):
    if n in Table:
        return Table[n]
    if len( n ) == 1:
        return 0
    else:
        prod = reduce(lambda x,y: x*y , map(int,n) )
        Table[n] = persist(str(prod)) +  1
        return Table[ n ]


n = 1476
while True:
    n += 1
    if persist( str(n) ) == 7:
        print n
        break

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

def prod_digits(n):
    s = 1
    while n:
        s *= n % 10
        n //= 10
    return s

pers=0
number=1
while True:
    copy=number
    while len(str(copy))>1:
        copy=prod_digits(copy)
        pers+=1
    if pers==7:
        print number
        break
    number+=1
    pers=0

I created a copy of the current number, to which I would apply the prod digits formula then see how many persists it takes per number. If it took seven, i would print and quit. Else, I would add 1 to number and reset persists.

Using C++(just the logic):

int number=1476;
for(    ;   ;   )
{
    int persistence=0,k=number;
    while(k/10)
    {
        int prod=1;
        persistence+=1;

        while(k)
        {
            prod*=(k%10);
            k/=10;
        }
        k=prod;
    }
    if(persistence==7)break;
    else number+=1;
}

    cout<<number<<endl;