Monty Hall puzzle 4

[assets]

I am looking for the Monty Hall puzzle I saw it about two week ago but could not find it last week. It has a puzzle in it about bases. Can someone give me the link to the Thread please.

Never give up never give in.

There are no short cuts to anything worth doing

 

[assets]

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 smaller of persistence four is 77. What is the smallest number of persistence five?

Never give up never give in.

There are no short cuts to anything worth doing

 

[Olaf Doschke]

It would be time to start a new thread for a new puzzle, but anyway.

At first I thought it's a trick question perhaps, as larger numbers might grow and therefore have infinite persistence, but at max an N digit number has N 9s and 9^N<10^N, any other composition of digits will be even smaller, therefor there always will be a tendency towards smaller numbers with of course less digits. Aside of that you always get straight to 0 once any digit is 0. Therefore you can assume even a brute force calculation will not take long.

I wrote a small routine for CrossProduct and stored already computed values to reduce costs for repeated numbers.

Starting from 78, being too lazy to think of a higher start value, it took 632 computations and in split seconds I arrived at
[hide]679 (679-378-16-48-32-6)[/hide]

I'll not show VFP code here, maybe I'll translate that to C#, C++ or anything else more commonly understood later, if it is of any interest at all.

Bye, Olaf.

 

[kwbMitel]

@ Olaf, why did you assume it would be a number higher than 77?

Not saying your answer is wrong but there is nothing to indicate it couldn't be lower.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[IPGuru]

Very quick & dirty python code confirms olafs answer

def persistance (number,count):
    result=int(str(number)[0])
    count=count+1
    for digit in str(number)[1:]:
        result= result * int(digit)
    if len(str(result))>1:
        result,count=persistance(result,count)
    return result,count

def main():
    for number in range(10,1000):
        result,count=persistance(number,count=0)
        if count==7 :
            print number,result,count
            break

if __name__ == '__main__':
	main()

A Maintenance contract is essential, not a Luxury.
Do things on the cheap & it will cost you dear

 

[kwbMitel]

Confirming Olaf has the correct answer.

The next level answer is [hide]6788, (2688, 768, 336, 54, 20, 0)[/hide]

After that is [hide]68889 (27648, 2688, 768, 336, 54, 20, 0)[/hide]

**********************************************
What's most important is that you realise ... There is no spoon.

 

[Olaf Doschke]

First, what actually is wrong with my answer is the sequence, at one place am 8 is missing.

>why did you assume it would be a number higher than 77?

Assume there is an n<77 with Persistence=6. Since Persistence = Persistence(Crossproduct)+1 at least for n>9 - _{and Persistence=0 for n<10} - there would need to be an m = Crossproduct, so that Persistence(m) = 5. Also m would need to be smaller than n, since m = Crossproduct and Crossproduct<n for n>9. m < n < 77 can't be true at the same time Persistence(m) = 5, since 77 is the smallest number with Persistence 5. There can't be such an m and so the smallest number with Persistence 6 must be higher than 77. I think you can proof by induction this also is true for any following smallest number of Persistence x.

Besides, Crossproduct = Crossproduct(n div 10)*(n mod 10), which allows to define crossproduct recursive and lookup results already computed instead of computing them.

Bye, Olaf.

 

[Olaf Doschke]

Again...

>why did you assume it would be a number higher than 77?

Assume there is an n<77 with Persistence=5. Since Persistence = Persistence(Crossproduct)+1 at least for n>9 - and Persistence=0 for n<10 - there would need to be an m = Crossproduct, so that Persistence(m) = 4. Also m would need to be smaller than n, since m = Crossproduct and Crossproduct<n for n>9. m < n < 77 can't be true at the same time Persistence(m) = 4, since 77 is the smallest number with Persistence 4. There can't be such an m and so the smallest number with Persistence 5 must be higher than 77. I think you can proof by induction this also is true for any following smallest number of Persistence x.

 

[kwbMitel]

@Olaf

Yeah, when I started working on my own solution, the answer to my question became readily obvious. It seems rather stupid in hindsight in fact. I blame the fact that I've done too many puzzles over the years that I never let assumptions get in the way. This particular puzzle is the sort of thing I've seen at the Euler project. They would as for the lowest number with a persistence of 12 or so though.

**********************************************
What's most important is that you realise ... There is no spoon.

 

[Olaf Doschke]

I also know the Euler project, but haven't done something for quite a while.

It won't take much longer to compute persistences for the smaller numbers, anyway, so thinking about this proof will take much longer than simply computing persistences for 1 to 76, too, despite thinking about that problem you dive deeper into the problem and get to a more elegent and less brute force attack which Euler is often needing. The code I did is needing a minute to compute smallest number of persistence 8, I wonder if I could get to 12 at all with normal integers, you'd have to introduce using string math at some point. you can define a cache or eg a C# Dictionary for already computed solutions and lookup them, then you can get much higher. In regard of crossproduct you can strike out any 1, don't need to analyze and number containing a 0, and you can sort the digits of numbers to map very many numbers to a lowest number you only need to put into that cache/dictionary instead of all other with same crossproduct. Just some ideas to get to the 12th Persistence.

Bye, Olaf.

 

[karluk]

You guys are nothing if not ambitious. There is no number known of persistence > 11, and it is conjectured that 11 is the maximum possible persistence for base 10. According to Wolfram Mathworld, this has been tested up to 10²³³.

 

[IPGuru]

thanks for that I will stop trying to streamline my code now

A Maintenance contract is essential, not a Luxury.
Do things on the cheap & it will cost you dear

 

[kwbMitel]

@Karluk

Long time no see.

12 was simply a guess, I'm impressed that I was at least close

**********************************************
What's most important is that you realise ... There is no spoon.

 

[karluk]

The lower bound for searching for a number with persistence 12 is apparently much larger than 10²³³. The on-line encyclopedia of integer sequences says in its comments to sequence A014553 that

a number with multiplicative persistence 12 must have more than 2530 digits.

http://oeis.org/A014553

 

[karluk]

Here is a link to one of the papers that investigated limits on the size of a number with persistence 12. I gather that the reason for the general belief that there is no number with a persistence of 12 is that, as the number of digits in a number increases, it quickly becomes overwhelmingly likely that multiplying the digits of the number will produce a product with a zero digit. Then the next iteration will result in a product of zero, so large numbers tend to have a persistence of two. But nobody has proven that persistence 11 is the limit, so there has been a flurry of activity in recent years pushing the bounds higher and higher in the search for persistence 12.

http://www41.homepage.villanova.edu...ce/PersistenceStephPerezJournalArtAug2013.pdf

 

[Olaf Doschke]

Here's a version using C# and dictionaries to not make any double calculations.

Due to memory restrictions you get an OutOfMemory Exception for trying to compute the lowest number of persistence 9, though that doesn't leave the int/int32 value range, but either the persistences or the crossproducts dictionary gets too large. So I hard coded 8 (highlighted in red) as the destination for the persistence.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LowestNumberwithPersinstence
{
    class Program
    {
        public static Dictionary<int, int> Persistences = new Dictionary<int, int>();
        public static Dictionary<int, int> CrossProducts = new Dictionary<int, int>();

        static void Main(string[] args)
        {

            int lnNumber, lnPersistence, lnMaxPersistence;
            DateTime t0 = System.DateTime.Now;

            lnNumber = 0;
            lnMaxPersistence = 0;

            while (lnMaxPersistence < [COLOR=red]8[/color])
            {
                lnNumber++;
                lnPersistence = Persistence(lnNumber);
                lnMaxPersistence = lnPersistence > lnMaxPersistence ? lnPersistence : lnMaxPersistence;
            }
            Console.WriteLine(lnNumber);
            Console.WriteLine(DateTime.Now - t0);
        }

        private static int Persistence(int tnNumber)
        {
            int lnPersistence, lnCrossProduct;

            lnPersistence = 0;

            if (tnNumber > 9)
            {
                if (Persistences.ContainsKey(tnNumber))
                {
                    lnPersistence = Persistences[tnNumber];
                }
                else
                {
                    lnCrossProduct = tnNumber%10==0 ? 0 : CrossProduct(tnNumber/10) * (tnNumber%10);
                    lnPersistence = lnCrossProduct > 9 ? Persistence(lnCrossProduct) + 1 : 1;
                    Persistences.Add(tnNumber, lnPersistence);
                }
            }

            return lnPersistence;
        }

        private static int CrossProduct(int tnNumber)
        {
            int lnCrossProduct;

            if (tnNumber > 9)
            {
                if (CrossProducts.ContainsKey(tnNumber))
                {
                    lnCrossProduct = CrossProducts[tnNumber];
                }
                else
                {
                    lnCrossProduct = tnNumber%10==0 ? 0 : CrossProduct(tnNumber/10) * (tnNumber%10);
                    CrossProducts.Add(tnNumber, lnCrossProduct);
                }
            }
            else
            {
                lnCrossProduct = tnNumber;
            }

            return lnCrossProduct;
        }
    }
}

Bye, Olaf.

 

[assets]

well done everyone it has sure started so debate

Never give up never give in.

There are no short cuts to anything worth doing