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?
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.
1 2 3 4 5 6 7 8 9 10 11 |
|
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 in them because you can find a smaller number of the same persistence(except possibly for repunit numbers) by just removing the 1 ′ s .
Avoid numbers that are permutations of a number you already computed..for example 3 4 9 → 1 0 8 → 0 and 9 4 3 → 1 0 8 → 0 both have a persistence of 3 .
And another tricky one consider the numbers 8 9 2 and 4 9 4 ..
8 9 2 → 1 4 4 → 1 6 → 6
4 9 4 → 1 4 4 → 1 6 → 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 2 2 2 3 can be replaced with 8 3 ..
Log in to reply
More generally, the number you are looking for has the following properties:
Its digits are in increasing order.
It does not contain any 0 or 1.
It contains at most one of the digits 2 or 4.
It contains at most one 3.
If contains at most one 6.
If it contains a 2, it does not contain a 3.
If it contains a 3, it does not contain a 4.
If it contains a 3 or 4, it does not contain a 6.
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.
Replacing any number containing zero by 0; removing any 1.
Replacing 2 2 → 4 , 2 4 → 8 , 4 4 → 2 8 .
Replacing 3 3 → 9 .
Replacing 6 6 → 4 9 .
Replacing 2 3 → 6 .
Replacing 3 4 → 2 6 .
Replacing 3 6 → 2 9 , 4 6 → 3 8 .
Replacing any number containing 5 and an even number by zero.
This seriously limits the numbers that need checking! Under 100, they are 2 6 , 2 7 , 2 8 , 2 9 , 3 5 , 3 7 , 3 8 , 3 9 , 4 7 , 4 8 , 4 9 , 5 5 , 5 7 , 5 9 , 6 7 , 6 8 , 6 9 , 7 7 , 7 8 , 7 9 , 8 8 , 8 9 , 9 9 and between 100 and 1000 they are 2 6 7 , 2 6 8 , 2 6 9 , 2 7 7 , 2 7 8 , 2 7 9 , 2 8 8 , 2 8 9 , 2 9 9 , 3 5 5 , 3 5 7 , 3 5 9 , 3 7 7 , 3 7 8 , 3 7 9 , 3 8 8 , 3 8 9 , 3 9 9 , 4 7 7 , 4 7 8 , 4 7 9 , 4 8 8 , 4 8 9 , 4 9 9 , 5 5 5 , 5 5 7 , 5 5 9 , 5 7 7 , 5 7 9 , 5 9 9 , 6 7 7 , 6 7 8 , 6 7 9 , 6 8 8 , 6 8 9 , 6 9 9 , 7 7 7 , 7 7 8 , 7 7 9 , 7 8 8 , 7 8 9 , 7 9 9 , 8 8 8 , 8 8 9 , 8 9 9 , 9 9 9 .
Thanks for your valuable reply! This will, for sure highly optimize my code. I will work on my code and post it later.
Problem Loading...
Note Loading...
Set Loading...
Memoising saves computing too.