Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 , so the submission with the least amount of bytes wins!

You can assume that the input will never have an uneven number of digits.

share|improve this question
10  
Nit 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 Feb 21 at 19:26
1  
So "period" is the 0-index of the last state which is different from all previous states? – Luis Mendo Feb 21 at 20:33
    
@LuisMendo Yes, that is correct. My mathematical knowledge isn't the best :p. – Adnan Feb 21 at 20:36
    
It'd be more like 'the number of iterations before it stabilizes' – somebody Feb 21 at 22:13
1  
@WashingtonGuedes See this pastebin. Does that make it more clear? – Adnan Feb 21 at 23:45

13 Answers 13

up vote 3 down vote accepted

Jelly, 26 24 18 bytes

³DL⁵*
²:¢½¤%¢µÐĿL’

Try it online!

How it works

³DL⁵*         Helper link. No arguments.

³             Yield the original input.
 D            Convert from integer to base 10.
  L           Get l, the length of the decimal representation.
   ⁵*         Compute 10 ** l.


²:¢½¤%¢µÐĿL’  Main link. Input: n (integer)

²             Square n.
  ¢½¤         Call the helper link and take the square root of the result.
 :            Integer division; divide the left result by the right one.
      ¢       Call the helper link.
     %        Take the left result modulo the right one.
       µ      Convert the previous chain into a link, and begin a new chain.
        ÐĿ    Repeat the previous chain until the results are no longer unique,
              updating n in each iteration. Collect the intermediate results.
          L   Get the length of the list of results.
           ’  Decrement.
share|improve this answer

Pure bash, 162 131 116 113 107

Saved 3 bytes by using $c...

Thanks @Dennis for help me to save 6 more bytes.

---- begin middleSquare ----

for((b=$1;i[c=10#$b]<2;)){ a=${#b}
printf -v b %0$[a*2]d $[c*c]
b=${b:a/2:a};((i[10#$b]++))
};echo ${#i[@]}

---- end middleSquare ----

for testCase in 24 82 123456 8989 789987 111111;do
    printf "%12s: " $testCase
    bash middleSquare $testCase
  done
          24: 2
          82: 5
      123456: 146
        8989: 68
      789987: 226
      111111: 374

Square formated, 131

---- begin middleSquare ----

for((b=$1;i[
10#$b]<2;1))
do a="${#b}" 
printf -v b\
 %0$[a*2]d \
$[10#$b**2];
b=${b:a/2:a}
((i[10#$b]++
));done;ech\
o ${#i[@]:0}

---- end middleSquare ----

for testCase in 24 82 123456 8989 789987 111111;do
    printf "%12s: %9d\n" $testCase $(
        bash middleSquare $testCase)
  done
          24:         2
          82:         5
      123456:       146
        8989:        68
      789987:       226
      111111:       374

Old but with fancy output, 162

---- begin middleSquare ----

for((b=$1;i[10#$b
]<2;1))do a=${#b}
printf -v b %0$[a
*2]d  $[10#$b**2]
b=${b:a/2:a};((i[
10#$b]++));print\
f "%9d %s\n" ${#\
i[@]} $b;done;ec\
ho -- ${#i[@]} --

---- end middleSquare ----

bash middleSquare 24
        1 57
        2 24
        2 57
-- 2 --

for testCase in 24 82 123456 8989 789987 111111
    do while read f v f
        do r=$v;done < <(
        bash middleSquare $testCase)
    printf "%12s: %11d\n" $testCase $r
  done
          24:           2
          82:           5
      123456:         146
        8989:          68
      789987:         226
      111111:         374
share|improve this answer

JavaScript (ES7), 82 bytes

f=(n,p={},m=-1,l=n.length)=>p[n]?m:f(`${n*n+100**l}`.substr(l/2+1,l,p[n]=1),p,++m)

Accepts input in the form of a string, e.g. "82", and returns an integer. Simple tail recursive technique to check each seed in turn against a hash of seeds that have already been seen. I add 100**l to the square to ensure a consistent length.

share|improve this answer
    
@Downgoat Accepts input in the form of a string. – Neil Feb 22 at 0:27
1  
oh yeah, I guess I can't read :| – Downgoat Feb 22 at 0:30
    
@WashingtonGuedes No, that doesn't work when the intermediate value begins with enough zeros. (This is why I "wasted" 7 bytes adding 100**l.) – Neil Feb 22 at 8:36
1  
@WashingtonGuedes There are cases where it doesn't work, for instance try following the chain from 5288. – Neil Feb 22 at 22:41

Python 3 2, 139 114 97 bytes

Thanks to Seeq for golfing off 25 bytes and thanks to Dennis for golfing off 17 bytes! Code:

s=`input()`;u=[];l=len(s)/2
while not s in u:u+=[s];s=`int(s)**2`.zfill(l*4)[l:3*l]
print~-len(u)

Can definitely be golfed further. This was also the code used to make the test cases :P.

share|improve this answer

Pyth, 21 bytes

tl.us_<>_`^N2/lz2lzsz

Try it online: Demonstration or Test Suite

edit: Found the edge case 1000, which didn't worked with my previous code. Fixed it for 1 byte.

Explanation:

tl.us_<>_`^N2/lz2lzsz   implicit: z = input string
  .u               sz   apply the following instructions to N, starting with N = int(z), 
                        until it runs into a loop:
          ^N2              square it
         `                 convert it to a string
        _                  reverse order
       >     /lz2          remove the first len(z)/2
      <          lz        remove everything but the first len(z)  
     _                     reverse order
    s                      convert to int
  .u                   returns the list of all intermediate values
 l                     compute the length of this list
t                      minus 1
share|improve this answer
    
any reason to use sz instead of Q? – ven Feb 22 at 12:53
    
@user1737909 If I use Q, I have to replace all the lz with l`Qs. – Jakube Feb 22 at 12:55
    
mh, it seems surprising Pyth doesn't share input. I guess it's really meant to allow for a second stdin read..? – ven Feb 22 at 12:58
    
@user1737909 Yes. The only possibility to share input is with .z and .Q, though they read multiple lines of input and store them in lists. But I haven't actually seen somebody use this feature. It's only 1 byte to evaluate a string or to stringify a number. – Jakube Feb 22 at 13:03
    
Okay, so you can read stdin at most 4 times in Pyth, Qz.Q.z? – ven Feb 22 at 13:07

MATL, 33 35 40 bytes

`t0)2^10GVnXK2/^/k10K^\vtun@>]n2-

Try it online!

`           % do...while
  t         %   duplicate. Take input implicitly on first iteration
  0)        %   pick last value of array
  2^        %   square
  10        %   push 10
  GVn       %   number of digits of input
  XK        %   copy that to clipboard K
  2/        %   divide by 2
  ^         %   power
  /k        %   divide and floor. This removes rightmost digits from the square value
  10K^      %   10 ^ number of digits of input
  \         %   modulo. This takes the central part of the squared number
  v         %   concatenate this new number to array of previous numbers
  tun@>     %   does the number of unique values exceed the iteration index?
]           % if so: next iteration. Else: exit loop
n2-         % desired result is the amount of numbers minus 2. Implicitly display
share|improve this answer

Oracle SQL 11.2, 184 bytes

WITH v(v,p,n)AS(SELECT:1,'0',-1 FROM DUAL UNION ALL SELECT SUBSTR(LPAD(POWER(v,2),LENGTH(v)*2,0),LENGTH(v)/2+1,LENGTH(v)),v,n+1 FROM v)CYCLE v SET c TO 1 DEFAULT 0 SELECT MAX(n)FROM v;

Un-golfed

WITH v(v,p,n) AS
(
  SELECT :1,'0',-1 FROM DUAL
  UNION ALL
  SELECT SUBSTR(LPAD(POWER(v,2),LENGTH(v)*2,0), LENGTH(v)/2+1, LENGTH(v)),v,n+1 FROM v
)
CYCLE v SET c TO 1 DEFAULT 0
SELECT MAX(n) FROM v;

It uses the build in cycle detection to stop the recursivity.

share|improve this answer

Julia, 64 bytes

f(n,A=[],p=10^endof(dec(n)))=n∈A?-1:f(n^2÷√p%p,[A...n],p)+1

Try it with Coding Ground.

share|improve this answer

Mathematica, 80 bytes

(a=10^⌊Log10@#+1⌋;Length@NestWhileList[⌊#^2/a^.5⌋~Mod~a&,#,Unequal,All]-2)&
share|improve this answer

CJam, 37 bytes

q{__,W*:D;~_*sD2/<D>]___|=:A;~A}g],((

Ran into an annoying stack-order issue that I can't immediately see how to resolve. It's also incredibly slow.

How it works: Each iteration pushes the new value on top of the stack, then we wrap the stack into an array, and see if it's the same as its union with itself (to see if it has any duplicate elements). When it has duplicate elements, stop, and see how many elements are in the stack.

share|improve this answer

Python 2, 82 bytes

def f(n,A=[],l=0):l=l or len(`n`)/2;return-(n in A)or-~f(n*n/10**l%100**l,A+[n],l)

Try it on Ideone.

share|improve this answer

Python, 124 bytes

def f(s,p=-1,n=0,m=[]):
 x=len(str(s))*2
 while n not in m:m+=[s];y=str(s*s).zfill(x);n=int(y[x/4:x*3/4]);p+=1;s=n
 return p
share|improve this answer

VBSCRIPT, 131 bytes

s=inputbox(c):l=len(s):do:t=t&","&s:s=space(l*2-len(s*s))&s*s:s=mid(s,l/2+1,l):i=i+1:loop until instr(t,","&s)>0:msgbox i-1

Best I could do with vbscript, first time poster so go easy on me!

share|improve this answer
    
Welcome to Programming Puzzles and Code Golf Stack Exchange! Great first post! I edited the formatting of your post a little bit to make it more readable and to conform to our standards more. Happy golfing! – GamrCorps Feb 22 at 21:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.