A Number's Persistence!

Computer Science Level 3

A number's persistence is the number of steps required to reduce it to a single digit by multiplying all its digits to obtain a second number, then multiplying all the digits of that number to obtain a third number, and so on until a one-digit number is obtained.

For example, 77 has a persistence of four because it requires four steps to reduce it to one digit: 77-49-36-18-8. The smallest number of persistence one is 10, the smallest of persistence two is 25, the smallest of persistence three is 39, and the smallest of persistence four is 77.

What is the smallest number of persistence five?


The answer is 679.

View wiki
Shravan Kumar by Shravan Kumar , 28, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

2 solutions

Bill Bell
Sep 28, 2015

Memoising saves computing too. 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
def memoise(f):
    class memodict(dict):
        def __init__(self, f):
            self.f = f
        def __call__(self, *args):
            return self[args]
        def __missing__(self, key):
            ret = self[key] = self.f(*key)
            return ret
    return memodict(f)

@memoise
def Persistence(n,count=0):
    if n<10:
        return count
    else:
        prod=1
        while n!=0:
            prod,n=prod*(n%10),n/10
        return Persistence(prod,count+1)

i=9
while True:
    i+=1
    if Persistence(i)==5:
        print i
        break

2 Helpful 0 Interesting 0 Brilliant 0 Confused
Arulx Z
Sep 24, 2015 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
 
>>> def per(n):
        count = 0
        while n / 10 != 0: # n / 10 will be 0 if n is one digit and n is a integer
            n = reduce(lambda x,y:x*y, list(int(x) for x in str(n))) # find the product of digits
            count += 1
        return count
>>> num = 10
>>> while per(num) != 5:
        num += 1
>>> print num
679

0 Helpful 0 Interesting 0 Brilliant 1 Confused

Moderator note:

How do we generalize to finding the smallest number with a large persistence? Is the only approach to test all cases?

Although the program is sufficient for solving for the problem at hand. here are a couple of things that i see that could help make it more efficient if you want to go about solving for large problems....

Avoid numbers that have a zero in them,(the reason is obvious)...

Also avoid numbers with 1 1 in them because you can find a smaller number of the same persistence(except possibly for repunit numbers) by just removing the 1 ′ s 1's .

Avoid numbers that are permutations of a number you already computed..for example 349 → 108 → 0 349\rightarrow 108 \rightarrow 0 and 943 → 108 → 0 943\rightarrow 108 \rightarrow 0 both have a persistence of 3 3 .

And another tricky one consider the numbers 892 892 and 494 494 ..

892 → 144 → 16 → 6 892\rightarrow 144\rightarrow 16\rightarrow 6

494 → 144 → 16 → 6 494\rightarrow 144\rightarrow 16\rightarrow 6

You can see that the first persistence of the numbers is the same(144). The reason is the prime factorization of each digit of both numbers is identical. For example 2223 2223 can be replaced with 83 83 ..

Beakal Tiliksew - 5 years, 8 months ago

Log in to reply

More generally, the number you are looking for has the following properties:

  1. Its digits are in increasing order.

  2. It does not contain any 0 or 1.

  3. It contains at most one of the digits 2 or 4.

  4. It contains at most one 3.

  5. If contains at most one 6.

  6. If it contains a 2, it does not contain a 3.

  7. If it contains a 3, it does not contain a 4.

  8. If it contains a 3 or 4, it does not contain a 6.

  9. If it contains a 5, it contains no even digits.

Proof: The following are guaranteed to make the number smaller while preserving the product of its numbers. 1. Sorting the digits from low to high.

  1. Replacing any number containing zero by 0; removing any 1.

  2. Replacing 22 → 4 22\to4 , 24 → 8 24\to8 , 44 → 28 44\to28 .

  3. Replacing 33 → 9 33\to9 .

  4. Replacing 66 → 49 66\to49 .

  5. Replacing 23 → 6 23\to6 .

  6. Replacing 34 → 26 34\to26 .

  7. Replacing 36 → 29 36\to29 , 46 → 38 46\to38 .

  8. Replacing any number containing 5 and an even number by zero.

This seriously limits the numbers that need checking! Under 100, they are 26 , 27 , 28 , 29 , 35 , 37 , 38 , 39 , 47 , 48 , 49 , 55 , 57 , 59 , 67 , 68 , 69 , 77 , 78 , 79 , 88 , 89 , 99 26,27,28,29,35,37,38,39,47,48,49,55,57,59,67,68,69,77,78,79,88,89,99 and between 100 and 1000 they are 267 , 268 , 269 , 277 , 278 , 279 , 288 , 289 , 299 , 355 , 357 , 359 , 377 , 378 , 379 , 388 , 389 , 399 , 267,268,269,277,278,279,288,289,299,355,357,359,377,378,379,388,389,399, 477 , 478 , 479 , 488 , 489 , 499 , 555 , 557 , 559 , 577 , 579 , 599 , 677 , 678 , 679 , 688 , 689 , 699 , 477,478,479,488,489,499,555,557,559,577,579,599,677,678,679,688,689,699, 777 , 778 , 779 , 788 , 789 , 799 , 888 , 889 , 899 , 999. 777,778,779,788,789,799,888,889,899,999.

Arjen Vreugdenhil - 5 years, 8 months ago

Thanks for your valuable reply! This will, for sure highly optimize my code. I will work on my code and post it later.

Arulx Z - 5 years, 8 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...