Talk:Iterated digits squaring

Comments on (a nice) task

Hi,

1. Do we need to keep the project Euler limit of 100million, wouldn't one million do?
2. It might be best to explain the limit a bit more w.r.t. inclusive/exclusive end points.
3. Do we need to mention caching in the task description?

Thanks. --Paddy3118 (talk) 21:09, 23 August 2014 (UTC)

Thank you for your comments.

1. The original Euler problem ha a limit of 10 millions. I think it's not a good idea to lower the limit too much (like 1 million): the point of having a high limit is to nudge people away from the very short brute-force solutions and toward a little smarter combinatorics-based solutions. To show it can be done I have added a not too much long Python solution that solves the problem with 100 millions in less than half second on a slow PC.
2. Regarding the limits, I have used standard mathematical notation, but the current <= < notation is OK.
3. Regarding the caching, it can be explained in the task description, but in the solutions I'd like to see less catching and more (simple) combinatorics. --bearophile (talk) 08:17, 24 August 2014 (UTC)

I took your comments on board Bearophile, and de-emphasized the one mill limit and hopefully made it unattractive enough to see more combinatorics examples.

What do you think? --Paddy3118 (talk) 08:54, 24 August 2014 (UTC)

It's OK. --bearophile (talk) 09:07, 24 August 2014 (UTC)

The Combinatorics of Life? The Universe? This Task simple or otherwise

Step 1 Precompile some small values

The following is an array indexed 0 to 648. Entry n==0 means that IDS(n) translates to 89 and n==1 means that IDS(n) translates to 1. The array is a constant and may be copied into a solution or calculated by the solution as you wish.

Set N to [1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0]

Entry 0 is set to 1, and may be used to calculate IDS(100,000,000), ignored, or deleted (if your language supports array indexing starting at 1).--Nigel Galloway (talk) 12:23, 7 September 2014 (UTC)--Nigel Galloway (talk) 12:23, 7 September 2014 (UTC)

Step 2 Iterate over unique digit combinations

Note that IDS(12345678) == IDS(21436587) and indeed any other arrangement of these digits. So we only wish to determine if each of these translate to 89 or 1 once. We can determine how many of these unique digits there are from the following table which I produced earlier using Gnumeric.

1	10	55	220	715 	2002	    5005	11440
1	9	45	165	495 	1287	    3003	6435
1	8	36	120	330 	792	    1716	3432
1	7	28	84	210 	462	    924 	1716
1	6	21	56	126 	252	    462 	792
1	5	15	35	70  	126	    210	        330
1	4	10	20	35  	56	    84  	120
1	3	6	10	15  	21	    28  	36
1	2	3	4	5   	6	    7	        8
1	1	1	1	1   	1	    1	        1
10	55	220	715	2002	5005	   11440	24310

From which we see that we have 24310 unique digit combinations, which is a lot less than 100 million.--Nigel Galloway (talk) 12:33, 7 September 2014 (UTC)

Rosettacode task Combinations may help you find these 24310 unique combinations in your language, or not!!!--Nigel Galloway (talk) 12:52, 9 September 2014 (UTC)

Step 2.1 Count only ones

Looking at the array in Step 1 we see that 90 out of 648 IDSs produce 1, so assuming this continues for larger values we shall do less work counting the 1s rather than the 89s. Square each of the digits in this combination and sum them. Use this value to index the array N from Step 1. If the value is 0 goto next Step 2.--Nigel Galloway (talk) 12:36, 7 September 2014 (UTC)

Step 2.2 Determine how many numbers this digit combination corresponds to

24310*90/648 = 3376.4, so we may expect to perform this step for around 3376.4 combinations. IDS(22266666) also represents IDS(62226666) and many others. We now need to determine how many. To do this we must count the number of each digit we have. In this case 3 twos and 5 sixes, 0 for all others. So 22266666 represents

   40320/0!*0!*3!*0!*0!*0!*5!*0!*0!*0!

remembering that 0! == 1. Add this value to the count of IDSs terminating in 1--Nigel Galloway (talk) 12:45, 7 September 2014 (UTC)

Step 3 Output result

The number if IDSs terminating in 89 is 10**8 - the final count from Step 2.2--Nigel Galloway (talk) 12:47, 7 September 2014 (UTC)