Persistent Numbers

Computer Science Level 4

We define a number's persistence as the number of steps required to reduce it to a single digit by multiplying all its digits together repeatedly. For example, 77 has a persistence of four because it requires four steps to reduce it to one digit:

$77 \rightarrow 49 \rightarrow 36 \rightarrow 18 \rightarrow 8$

The smallest number with a persistence of one is 10.
The smallest number with a persistence of two is 25.
The smallest number with a persistence of three is 39...
And the smallest number with a persistence of four is 77.

What is the smallest number of persistence nine?

Inspired by Martin Gardner.

The answer is 26888999.

2 solutions

First Last
Dec 2, 2016

//return the multiple digits of a number
long multiplyDigits(unsigned long long number){
    NSMutableArray *digits = [NSMutableArray new] ;
    while(number != 0){
        [digits addObject:[NSNumber numberWithUnsignedLongLong:number - 10*(number/10)]] ;
        number /= 10 ;
    }
    number = 1 ;
    for(NSNumber *junk in digits) number *= [junk integerValue] ;
    return number ;
}

int main(){@autoreleasepool{
    int persistence = 9 ; persistence -= 1 ;
    long copy ;
    BOOL belowNine = true ;
    for(long i = 10 ; ; i += 1){
        copy = i ;
        belowNine = true ;
        for(int a = 0 ; belowNine && a < persistence ; a += 1){
            copy = multiplyDigits(copy) ;
            if(copy/10 == 0) belowNine = false ; //check for one digit
        }
        if(belowNine){ //if never one digit in under 8 iterations, then the value look for
            NSLog(@"%li",i) ;
            break ;
        }
    }}
    return 0;
}

Noureldin Yosri
Feb 14, 2016

first attempt : use a while loop that will stop when it finds a solution (f(n) == 9) -> takes a long time using python

second attempt : use a while loop that will stop when it finds a number from which I can build the solution (f(n) == 8) the least n | f(n) == 8 is 4478976 which has a prime factorization $2^{11} \times 3^7$ now I want a number whose digits has a product equal to that number ... by grouping each 3 2s group in a single 8 and each 2 3s group into a single 9 -> 2^2 * 3 * 888*999 ... the best way to group 2 2 3 is as 26 -> ans = 26888999

How can one prove there is no n<23888999 has a persistence equal to 9?(when using your method).

By factoring and grouping $(2, 10=2 \times 5), (3, 25=5 \times 5), (4, 55?)$ .

Mahdi Al-kawaz - 5 years, 4 months ago

just to be clear I don't know whether you mean

1) how to prove that the least n with digit product = 4478976 is 26888999 ?

2) how to prove that there is no n < 26888999 with digit product m > 4478976 and the persistence of m = 8 which is legit -more below- ?

so I'll prove both

1) how to prove that the least n with digit product = 4478976 is 23888999 ? this can be done in several ways but the one I thought of is using dynamic programming as it has an optimal sub-structure

dp = [["-1" for i in xrange(12)] for j in xrange(12)];

def make_smallest(st):
    ### get the smallest number that has the same digits as st ###
    st = [c for c in st];
    st.sort();
    return "".join(st);

def comp(st1,st2):
    st1 = make_smallest(st1);
    st2 = make_smallest(st2);           
    if len(st1) == len(st2):
        # return the smallest number
        return min(st1,st2);
    # return the number with the least number if digits
    return st1 if len(st1) < len(st2) else st2;

def solve(p2,p3):
    global dp;
    if p2 == 0 and p3 == 0: return "";           #base case
    if dp[p2][p3] != "-1": return dp[p2][p3];    #did I solve this problem before
    dp[p2][p3] = "99999999999999999999999";      #init as infinity
    # try every possibility you can
    if p2 >= 1 and p3 >= 1: dp[p2][p3] = comp(dp[p2][p3],solve(p2 - 1,p3 - 1) + "6");   
    if p2 >= 1 : dp[p2][p3] = comp(dp[p2][p3],solve(p2 - 1,p3) + "2");
    if p2 >= 2 : dp[p2][p3] = comp(dp[p2][p3],solve(p2 - 2,p3) + "4");
    if p2 >= 3 : dp[p2][p3] = comp(dp[p2][p3],solve(p2 - 3,p3) + "8");
    if p3 >= 1 : dp[p2][p3] = comp(dp[p2][p3],solve(p2,p3 - 1) + "3");
    if p3 >= 2 : dp[p2][p3] = comp(dp[p2][p3],solve(p2,p3 - 2) + "9");
    return dp[p2][p3];

print solve(11,7);

2) how to prove that there is no n < 26888999 with digit product m > 4478976 and the persistence of m = 8 which is legit ?

to do that is simple 4478976 < n < 26888999 which implies that n contains at least 7 digits and at most 8 digits with digit product $5314410 = 2\times5\times9^6$ corresponding to 25999999 , any other number < 26888999 has a digit product $\leq 5314410$ ... $5314410$ is not that big and we can verify that there is no number $\leq 5314410$ with persistence = 8 and its prime factorization contains only one digit primes {2,3,5,7} -legit number- other than 4478976 and no number has persistence = 9 in that range using brute force

and as 4478976 is the only legit number < $5314410$ with persistence = 8 it follows that the smallest number with digit product 4478976 is the answer

dp = {}
def persistence(n):
    if n < 10: return 0;
    if dp.has_key(n) : return dp[n];
    N,m = n,1;
    while N:
        m *= N%10;
        N /= 10;
    dp[n] = persistence(m) + 1;
    return dp[n];

def is_legit(n):
    primes = [2,3,5,7];
    for d in primes:
        while n%d == 0:
            n /= d;
    return n == 1;

n = 1; ctr = 0;
while n <= 5314410:
    if persistence(n) == 8 and is_legit(n):
        ctr += 1;
        print n;
    if persistence(n) == 9:
        print "Errr",n  
    n += 1; 

print ctr;

Noureldin Yosri - 5 years, 4 months ago

Meant the second question, thanks for the clear explanation.

Mahdi Al-kawaz - 5 years, 4 months ago

Persistent Numbers

Inspired by Martin Gardner.

The answer is 26888999.

2 solutions

0 pending reports