19
Introduction
The middle-square method is used for the generation of pseudorandom numbers. However, this is not a good method in practice, since its period is usually very short and has some severe weaknesses. How does this work? Let's take an example:
For the seed, we pick 123456
:
Seed 123456
The seed squared (seed × seed), is equal to:
Seed² 15241383936
We started with a 6-digit number. That means that the seed squared should deliver a 12-digit number. If this is not the case, leading zeroes are added to compensate:
Seed² 015241383936
We then take the middle part of the number, with the same size as the seed:
Seed² 015241383936
^^^^^^
This is then our new seed: 241383
. We repeat the same process as shown above. We get the following:
0: 123456
015241383936
| |
1: 241383
058265752689
| |
2: 265752
070624125504
| |
3: 624125
389532015625
| |
4: 532015
283039960225
| |
5: 039960
001596801600
| |
6: 596801
And this keeps on in a while... Now we know what the middle-square method is, let's get to the challenge:
The Task
Every seed has a period. The period of a n-digit seed cannot be longer than 8n. For example, the seed 82
. This would give the following sequence:
82 > 72 > 18 > 32 > 02 > 00 > 00 > 00 > 00 > 00
|____|____|____|____|____|____|____|____|____|___...
0 1 2 3 4 5 6 7 8 9
You can see that the period is equal to 5, before containing the same digit again. Your task is, when given a seed greater than 0 containing no leading zeroes, output the period of the seed. So, in this case, you need to output 5
.
Another example is: 24
, which gives the following:
24 > 57 > 24
|____|____|___...
0 1 2
As you can see, not all sequences end in 0
. This cycle has a period of 1.
Test cases
Input > Output
24 > 1
82 > 5
123456 > 146
8989 > 68
789987 > 226
The pastebins with the sequences for 123456, 8989, 789987
This is code-golf, so the submission with the least amount of bytes wins!
You can assume that the input will never have an uneven number of digits.
10Nit pick: That's not a period. Period implies that the sequence eventually goes back it its initial state.
24
is periodic (with period 2, I'd say),82
is eventually periodic (with period 1). – Dennis – 2016-02-21T19:26:20.7831So "period" is the 0-index of the last state which is different from all previous states? – Luis Mendo – 2016-02-21T20:33:25.353
@LuisMendo Yes, that is correct. My mathematical knowledge isn't the best :p. – Adnan – 2016-02-21T20:36:09.797
It'd be more like 'the number of iterations before it stabilizes' – ASCII-only – 2016-02-21T22:13:32.507
1
@WashingtonGuedes See this pastebin. Does that make it more clear?
– Adnan – 2016-02-21T23:45:15.663Just did some tests for 2-digit numbers, and found some interesting results. It turns out there are only 5 possible end results for all numbers 0-99. It will either stabilize on
0
(most common: 62% of all inputs), or stabilize on10
(19%),50
(1%),60
(15%), or an endless loop of24
and57
(3%).50
is only possible if you start with50
. – Darrel Hoffman – 2016-02-22T19:25:49.573@DarrelHoffman I also found this diagram, which also might be interesting :).
– Adnan – 2016-02-22T19:26:39.577@Adnan - Yes, I more or less derived the same diagram myself. I thought about posting it, but it'd need to be as an answer to this challenge, and I don't have one of those. – Darrel Hoffman – 2016-02-22T19:29:00.730