Problem Statement | |||||||||||||
Any irrational number greater than 1 can be written as
Q[0] + 1
------------------------
Q[1] + 1
-----------------
Q[2] + 1
----------
Q[3] + 1
---
...
for some infinite sequence Q[0],Q[1],Q[2],Q[3],... where each Q[i] is a positive integer. This method of writing a number is called a continued fraction, and each Q[i] is called a partial quotient. A remarkable
fact from number theory is that, whenever the square root of a non-square positive integer is written in this form, the sequence of
partial quotients is periodic. In other words, there exists some number K such that Q[J+K] = Q[J] for all J > 0. Notice that the repeating pattern begins at Q[1]; the initial partial quotient, Q[0], is not involved in the repetition.
We will represent such a periodic continued fraction as the finite sequence {Q[0],Q[1],...,Q[K]}, where K is the size of the shortest repeating pattern. For example, the square root of 2 has partial quotients 1,2,2,2,... and would be written as {1,2}. Similarly, the square root of 8 has partial quotients 2,1,4,1,4,... and would be written as {2,1,4}. Your task is to take a non-square positive integer n, and calculate its representation as a periodic continued fraction. Several sample calculations will be presented from which you should be able to generalize an algorithm. Although you are not required to follow the same algorithm as the sample calculations, it is highly suggested that you do so. Note that, for the purposes of this problem, the periodic continued fraction will always contain fewer than 100 elements. Here is a sample calculation showing that the square root of 2 is {1,2}:
Step 0: Calculate Q[0] from sqrt(2).
sqrt(2) = 1 + sqrt(2)-1
---------
1
Q[0] is 1. The remainder is (sqrt(2)-1)/1.
Step 1: Calculate Q[1] from (sqrt(2)-1)/1.
sqrt(2)-1 1 1 1 1
--------- = ------------- = --------------------- = ------------- = -------------
1 1 1 sqrt(2)+1 sqrt(2)+1 2 + sqrt(2)-1
--------- --------- * --------- --------- ---------
sqrt(2)-1 sqrt(2)-1 sqrt(2)+1 1 1
Q[1] is 2. The remainder is (sqrt(2)-1)/1.
Step 2: Calculate Q[2] from (sqrt(2)-1)/1. (Same as Step 1!)
Substituting the result of Step 1 into the result of Step 0, we get
sqrt(2) = 1 + 1
-------
2 + ...
and at this point the pattern repeats, so the square root of 2 is {1,2}.
Notice that, at every step, the partial quotient is chosen to force the remainder between 0 and 1 (exclusive), and that there is only one way to do this. Also notice that, in Step 1, we made essential use of the identity (A-B)*(A+B) = A*A - B*B. Here is a more elaborate example, showing that the square root of 41 is {6,2,2,12}:
Step 0: Calculate Q[0] from sqrt(41).
sqrt(41) = 6 + sqrt(41)-6
----------
1
Q[0] is 6. The remainder is (sqrt(41)-6)/1.
Step 1: Calculate Q[1] from (sqrt(41)-6)/1.
sqrt(41)-6 1 1 1 1
---------- = -------------- = ----------------------- = -------------- = --------------
1 1 1 sqrt(41)+6 sqrt(41)+6 2 + sqrt(41)-4
---------- ---------- * ---------- ---------- ----------
sqrt(41)-6 sqrt(41)-6 sqrt(41)+6 5 5
Q[1] is 2. The remainder is (sqrt(41)-4)/5.
Step 2: Calculate Q[2] from (sqrt(41)-4)/5.
sqrt(41)-4 1 1 1 1
---------- = -------------- = ----------------------- = -------------- = --------------
5 5 5 sqrt(41)+4 sqrt(41)+4 2 + sqrt(41)-6
---------- ---------- * ---------- ---------- ----------
sqrt(41)-4 sqrt(41)-4 sqrt(41)+4 5 5
Q[2] is 2. The remainder is (sqrt(41)-6)/5.
Step 3: Calculate Q[3] from (sqrt(41)-6)/5.
sqrt(41)-6 1 1 1 1
---------- = -------------- = ----------------------- = -------------- = ---------------
5 5 5 sqrt(41)+6 sqrt(41)+6 12 + sqrt(41)-6
---------- ---------- * ---------- ---------- ----------
sqrt(41)-6 sqrt(41)-6 sqrt(41)+6 1 1
Q[3] is 12. The remainder is (sqrt(41)-6)/1.
Step 4: Calculate Q[4] from (sqrt(41)-6)/1. (Same as Step 1!)
Substituting the result of each step into the result of the previous step, we get
sqrt(41) = 6 + 1
----------------
2 + 1
------------
2 + 1
--------
12 + ...
and at this point the pattern repeats, so the square root of 41 is {6,2,2,12}.
Notice that the remainders are always of the form (sqrt(n)-d)/m, for some integers d and m. It might sometimes appear that the remainder has the form c*(sqrt(n)-d)/m, but it will always be possible to eliminate the c. | |||||||||||||
Definition | |||||||||||||
| |||||||||||||
Notes | |||||||||||||
| - | Because we have restricted each partial quotient to be a positive integer, each square root has a unique representation as a periodic continued fraction. | ||||||||||||
Constraints | |||||||||||||
| - | n is between 2 and 1000, inclusive. | ||||||||||||
| - | n is not a square number. For example, n is not 4, 9, or 16. | ||||||||||||
Examples | |||||||||||||
| 0) | |||||||||||||
| |||||||||||||
| 1) | |||||||||||||
| |||||||||||||
| 2) | |||||||||||||
| |||||||||||||
| 3) | |||||||||||||
| |||||||||||||
| 4) | |||||||||||||
| |||||||||||||