If D is a natural number, we may express the positive square root of D as a simple continued fraction. This continued fraction has a very special form. If D is a perfect square, with square root q0, then we represent the continued fraction of this square root by [q0].
Otherwise the expansion of the square root is infinite in length. It begins with q0, which is the integer part, or "floor", of the square root. Among the following entries, q1,q2,q3, etc. there will be a first occurrence, say qk, which is equal to 2q0. The entries q1,q2,...,qk-1 are a palindrome of numbers, possibly empty (if k=1). The string q1,q2,...,qk-1,2q0 then repeats infinitely. We write
Square Root of D = [q0,q1,q2,...,qk-1,2q0,q1,q2,...,qk-1,2q0,...]
There is a wonderful theorem, usually called the Euler-Muir Theorem, which allows one to calculate, given a palindrome, the three coefficients of a quadratic polynomial f such that, for every natural number n, f(n)= D has this palindrome in the period of the expansion of its square root, and, moreover, every D with this palindrome is f(n) for some n.
D | Palindrome of Continued Fraction for Sqrt(D) | fD(n) (if fD(1)=D) |
---|---|---|
1 | n/a | n2 |
2 | [] | n2+1 |
3 | [1] | n2+2n |
4 | n/a | f1(2) |
5 | [] | f2(2) |
6 | [2] | n2+3n+2 |
7 | [1,1,1] | 9n2-2n |
8 | [1] | f3(2) |
9 | n/a | f1(3) |
10 | [] | f2(3) |
11 | [3] | 9n2+2n |
12 | [2] | f6(2) |
13 | [1,1,1,1] | 25n2-14n+2 |
14 | [1,2,1] | 4n2+7n+3 |
15 | [1] | f3(3) |
16 | n/a | f1(4) |
17 | [] | f2(4) |
18 | [4] | 4n2+9n+5 |
19 | [2,1,3,1,2] | 1521n2-2702n+1200 |
20 | [2] | f6(3) |
21 | [1,1,2,1,1] | 36n2-17n+2 |
22 | [1,2,4,2,1] | 441n2-685n+266 |
23 | [1,3,1] | 25n2-2n |
24 | [1] | f3(4) |
25 | n/a | f1(5) |
26 | [] | f2(5) |
27 | [5] | 25n2+2n |
28 | [3,2,3] | 144n2-161n+45 |
29 | [2,1,1,2] | 169n2-198n+58 |
30 | [2] | f6(4) |
31 | [1,1,3,5,3,1,1] | 74529n2-146018n+71520 |
32 | [1,1,1] | f7(2) |
33 | [1,2,1] | f14(2) |
34 | [1,4,1] | 9n2+17n+8 |
35 | [1] | f3(5) |
36 | n/a | f1(6) |
37 | [] | f2(6) |
38 | [6] | 9n2+19n+10 |
39 | [4] | f18(2) |
40 | [3] | f11(2) |
41 | [2,2] | 25n2+14n+2 |
42 | [2] | f6(5) |
43 | [1,1,3,1,5,1,3,1,1] | 28191n2-556958n+275040 |
44 | [1,1,1,2,1,1,1] | 225n2-251n+70 |
45 | [1,2,2,2,1] | 144n2-127n+28 |
46 | [1,3,1,1,2,6,2,1,1,3,1] | 321843n2-6412537n+3194147 |
47 | [1,5,1] | 49n2-2n |
48 | [1] | f3(5) |
49 | n/a | f1(7) |
50 | [] | f2(7) |
51 | [7] | 49n2+2n |
52 | [4,1,2,1,4] | 2025n2-3401n+1428 |
53 | [3,1,1,3] | 625n2-886n+314 |
54 | [2,1,6,1,2] | 1089n2-1693n+658 |
55 | [2,2,2] | 36n2+17n+2 |
56 | [2] | f6(7) |
57 | [1,1,4,1,1] | 100n2-49n+6 |
58 | [1,1,1,1,1,1] | 169n2-140n+29 |
59 | [1,2,7,2,1] | 4761n2-8462n+3760 |
60 | [1,2,1] | f14(3) |
61 | [1,4,3,1,2,2,1,3,4,1] | 14478025n2-28896614n+14418650 |
62 | [1,6,1] | 16n2+31n+15 |
63 | [1] | f3(7) |
64 | n/a | f1(8) |
65 | [] | f2(8) |
66 | [8] | 16n2+33n+17 |
67 | [5,2,1,1,7,1,1,2,5] | 35605089n2-71112494n+35507472 |
68 | [4] | f18(3) |
69 | [3,3,1,4,1,3,3] | 219024n2-430273n+211318 |
70 | [2,1,2,1,2] | 225n2-199n+44 |
71 | [2,2,1,7,1,2,2] | 170569n2-334178n+163680 |
72 | [2] | f6(7) |
73 | [1,1,5,5,1,1] | 15625n2-29114n+13562 |
74 | [1,1,1,1] | f13(2) |
75 | [1,1,1] | f7(3) |
76 | [1,2,1,1,5,4,5,1,1,2,1] | 10989225n2-21920651n+10931502 |
77 | [1,3,2,3,1] | 400n2-449n+126 |
78 | [1,4,1] | f34(2) |
79 | [1,7,1] | 81n2-2n |
80 | [1] | f3(8) |
81 | n/a | f1(9) |
82 | [] | f2(9) |
83 | [9] | 81n2+2n |
84 | [6] | f38(2) |
85 | [4,1,1,4] | 1681n2-2606n+1010 |
86 | [3,1,1,1,8,1,1,1,3] | 314721n2-619037n+304402 |
87 | [3] | f11(3) |
88 | [2,1,1,1,2] | 441n2-488n+135 |
89 | [2,3,3,2] | 2809n2-4618n+1898 |
90 | [2] | f6(8) |
91 | [1,1,5,1,5,1,1] | 27225n2-51302n+24168 |
92 | [1,1,2,4,2,1,1] | 3600n2-6049n+2541 |
93 | [1,1,1,4,6,4,1,1,1] | 396900n2-781649n+384842 |
94 | [1,2,3,1,1,5,1,8,1,5,1,1,3,2,1] | 12217323024n2-24432502753n+12215179823 |
95 | [1,2,1] | f14(4) |
96 | [1,3,1] | f23(2) |
97 | [1,5,1,1,1,1,1,1,5,1] | 323761n2-636314n+312650 |
98 | [1,8,1] | 25n2+49n+24 |
99 | [1] | f3(9) |
100 | n/a | f1(10) |
Example 1: Row 98 says that the simple continued fraction expansion of the square root of 98 is [9,1,8,1,18,1,8,1,18,1,8,1,18,...]. It also says that, for instance, f98(2)=25(2)2+49(2)+24=222 will have the same palindrome in its square root. In fact, the square root of 222 is [14,1,8,1,28,1,8,1,28,1,8,1,28,...]. Another consequence of Euler-Muir is that equipalindromic q0's are in a linear sequence. In this case, this tells us that the next square root of an integer with palindrome 1,8,1 will be [19,1,8,1,38,1,8,1,38,...]. If we provide any other value for q0, the resulting continued fraction will represent the square root of a non-integral rational number.
Example 2: Row 95 says that 95 is the fourth smallest natural number whose square root has palindrome 1,2,1 (the smallest being 14). In fact, the square root of 95 is [9,1,2,1,18,1,2,1,18,...].