PG Calculator 1.5a serial key or number

PG Calculator 1.5a serial key or number

PG Calculator 1.5a serial key or number

PG Calculator 1.5a serial key or number

Continued fractions are just another way of writing fractions. They have some interesting connections with a jigsaw-puzzle problem about splitting a rectangle into squares and also with one of the oldest algorithms known to Greek mathematicians of 300 BC - Euclid's Algorithm - for computing the greatest divisor common to two numbers (gcd).
An online Combined Continued Fraction Calculator is available in a separate window where you see Combined CF
It is now updated to be a BigNumber Calculator that can handle very long whole numbers! (Jan 2018)
The calculators on this page require JavaScript but you appear to have switched JavaScript off (it is disabled). Please go to the Preferences for this browser and enable it if you want to use the calculators, then Reload this page.
The icon means there is a You do the maths... section of questions to start your own investigations. The calculator icon indicates that there is a live interactive calculator in that section.

Introducing the Continued Fraction...

Here we show 2 ways to "discover" the continued fraction:
  • Making a rectangular jigsaw puzzle using only square pieces. This is a very nice and simple visual way to introduce continued fractions
  • Seeing Euclid's algorithm in a different light, which provides us with a method (algorithm) for finding continued fractions.

A jigsaw puzzle: splitting rectangles into squares

Let's take an example to introduce you to a continued fraction. We'll convert the ordinary fraction 45/16 into a continued fraction.
We will make extensive use of a picture analogy (from Clark Kimberling of Evansville University, USA, but also mentioned by N N Vorob'ev in 1951 - see references below). For our example fraction of 45/16 we will use a rectangle of 45 units by 16 to show visually what is happening with the mathematics.

Looking at the rectangle the other way, its sides are in the ratio 16/45. We shall use this change of view when expressing 45/16 as a continued fraction. 45/16 suggests that we convert it to a whole number quotient (since 45 is bigger than 16) plus a proper fraction (what is left over after we've taken away multiples of 16 from 45).
45/16 is 2 lots of 16, with 13 left over, or, in terms of ordinary fractions:

45
16
=
16 + 16 + 13
16
= 2 +
13
16
In terms of the picture, we have just cut off squares from the rectangle until we have another rectangular bit remaining. There are 2 squares (of side 16) and a 13 by 16 rectangle left over. The final rectangle is taller than it is wide, so no more 16x16 squares can be taken from it.

Now, suppose we do the same with the 13-by-16 rectangle, viewing it the other way round, so it is 16 by 13 (so we are expressing 16/13 as a whole number part plus a fraction left over). In terms of the mathematical notation we have:

Repeating what we did above but on 16/13 now, we see that there is just 1 square of side 13 to cut off, with a 3-by-13 rectangle left over. Writing the same thing mathematically expresses 13/3 as a whole-number-plus-fraction like this:
Notice how we have continued to use fractions and how the maths ties up with the picture.
You will have guessed what to do now: we do the same thing on the left-over 3-by-13 rectangle, but looking at it as a 13-by-3 rectangle. There will be 4 squares (of side 3) and a rectangle 1-by-3 left over:

But now we have ended up with an exact number of squares in a rectangle, with nothing left over so we cannot split it down any more.

This expression relates directly to the geometry of the rectangle-as-squares jigsaw as follows:
  • 2 orange squares (16 x 16)
  • 1 blue square (13 x 13)
  • 4 red squares (3 x 3)
  • 3 yellow squares (1 x 1)
Since the numbers always reduce, that is, the size of the remaining rectangle left over will always have one side smaller than the starting rectangle, then the process will always stop with a final n-by-1 rectangle.

Using Euclid's GCD algorithm to make a continued fraction

One of the often studied algorithms in computing science is Euclid's Algorithm for finding the greatest common divisor (gcd) of two numbers. The greatest common divisor (often just abbreviated to gcd) is also called the highest common factor (or just hcf). It is intimately related to continued fractions, but this is hardly ever mentioned in computing science text books. Here we try to show you the link and introduce a visual way of seeing the algorithm at work as well as giving an alternative look into continued fractions.

So let's look again at the calculations we did above for 45/16.

45=2 ×16+13: 45 is a multiple of 16 with 13 left over
16=1 ×13+ 3: 16 is a multiple of 13 with  3 left over
13=4 × 3+ 1: 13 is a multiple of  3 with  1 left over
3=3 × 1+ 0:  3 is a multiple of  1 e×actly.
L= S+ R 
The bold figures ( N ) are our continued fraction numbers. The L column is the Longest side of each rectangle that we encountered with S the Shortest side and R being the Remainder.
The method shown here is
  • precise, and
  • works for any two numbers in place of 45 and 16, and
  • it always terminates since each time L, R and S are reduced until eventually S is 1 and R is 0.
These are the three conditions necessary for an algorithm - a method that a computer can carry out automatically and which eventually stops.

Euclid (a Greek mathematicians and philosopher of about 300 BC) describes this algorithm in Propositions 1, 2 and 3 of Book 7 of The Elements, although it was probably known to the Babylonian and Egyptian mathematicians of 3000-4000 BC also.
If we try it with other numbers, the final non-zero remainder is the greatest number that is an exact divisor of both our original numbers (the greatest common divisor) - here it is 1.

Given any two numbers, they each have 1 as a divisor so there will always be a greatest common divisor of any two (positive) numbers and it will be at least 1.

Using Lists of Divisors to find the GCD

Here are the divisors of 45 and of 16:

45 has divisors 1, 3, 5, 9, 15 and 45 16 has divisors 1, 2, 4, 8 and 16 So the largest number in both of these lists is just 1.

Let's take a fraction such as 168/720. It is not in its lowest terms because we can find an equivalent fraction which uses simpler numbers. Since both 168 and 720 are even, then 168/720 is the same (size) as 84/360. This fraction too can be reduced, and perhaps the new one will be reducible too. So can we find the largest number to divide into both numerator 168 and denominator 720 and get to the simplest form immediately?
However, first, let's try to find the largest number to divide into both 168 and 720 directly:
Find the lists of the divisors of 168 and of 720 and pick the largest number in both lists:

168 has divisors 1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84 and 168 720 has divisors 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360 and 720 Phew! - that took some work!
Now we just need to find the largest number in both lists. A bit of careful searching soon reveals that it is 24. So 24 is the greatest common divisor (gcd) of 168 and 720. You will often see statements such as this written as follows:
Another term often used for greatest common divisor is highest common factor (hcf).

The importance of the gcd of a and b is that it tells us how to put the fraction a/b into its simplest form by giving the number to divide the top and the bottom by. The resulting fraction will be the simplest form possible. So

Euclid's algorithm is here applied to 720 and 168: Just keep dividing and noting remainders so that the larger number 720 is 4 lots of the smaller number 168 with 48 left over. Now repeat on the smaller number (168) and the remainder (48) and so on:

720 = 4 × 168 + 48 168 = 3 × 48 + 24 48 = 2 × 24 + 0 so the last multiple before we reach the zero is 24, just as we found above but with rather less effort this time!

Here is a rectangle 720 by 168 split up into squares, as above where the numbers in the squares are the length of their sides. Note how the quotients 4, 3 and 2 are shown in the picture and also that the gcd is 24 (the side of the smallest squares):
And here is 720/168 expressed as a continued fraction:

720= 4 + 48= 4 + 1= 4 + 1= 4 + 1
168168168/483 + 243 + 1
482
If we simplify the continued fraction starting at the lowest part we will find 720/168 in its lowest form:
720 = 4 + 1 = 4 + 1 = 4 + 2 = 28 + 2 = 30
1683 +17/2777
2

The List Notation for Continued Fractions

Writing continued fractions (CFs) in the usual way takes up a lots of space so there is a convenient shorthand: make a list of the initial integer part (which may be 0) and the numbers in the denominators (the numerators are always 1).
For example
30= 4 + 1is written as [4; 3, 2]
73 +1
2
We can write down any continued fraction such as P/Q = a + 1/(b + 1/(c + 1/(d + ...))) just as a list of the numbers a; b, c, ... . The first number, a, is special as it is the whole number part of the value. The rest is written as a list with comma separators (,) like this: P/Q = [a; b, c, d, ...] None of the values will be zero, except possibly the first - the one before the semicolon (;) - if the value of the fraction is less than 1.

In some mathematical books and articles you will see one other form of notation which saved space :

P  =  
Q
a + 1
b + 1
c + 1
d + ...
 
  =  a+1/(b+1/(c+1/(d+...)))  =  

The second form is normal mathematical notation but has lots of necessary brackets, making it harder to read and also must easier to miss a bracket.
In the final form note that the + is written below the fraction-line to show that the rest of the expression is also meant to be there too.
On this page and others at this site, we will use the much more convenient list notation[ a; b, c, d, ... ].

You do the maths...

There is another simple way to find gcd's which takes more work than Euclid's method but is quicker than enumerating all the divisors. It involves expressing the two numbers as powers of prime factors, for instance: 720 = 24 x 32 x 51 and 168 = 23 x 31 x 71
First re-write these so that the same prime numbers appear in both lists, using a-prime-to-the-power-of-0 if necessary.
For instance, there are no 7's in the primes product for 720, so, since 70=1, we introduce an extra factor of x70. In the same way we can introduce x50 into the product for 168.
Now both lists contains exactly the same primes: 2, 3, 5 and 7: 720 = 24 x 32 x 51 x 70 and 168 = 23 x 31 x 50 x 71
Since there must be 2's in the gcd of 720 and 168, how many twos do we need for the greatest factor which divides both?
What about the number of 3's? and 5's? and 7's?
So the greatest common divisor has the form:
  1. What numbers stand in place of the letters?
  2. What is the general principle for computing the gcd given two numbers expressed as powers of the same primes?
  3. What is the greatest common divisor of 24 and 18 (call it G)? What is the gcd of 24, 18 and 30? How is it related to the gcd of G and 30? [This is Propositions 3 of Euclid's The Elements, Book 7.]
  4. The gcd is useful in simplifying a fraction. But when adding fractions we find equivalents with the same denominator. This time we need the smallest number into which both denominators will divide exactly, ot the lowest common multiple (lcm).
    Using the prime-powers decomposition of two denominators, how can we find the lcm? Use 168 and 720 as an example.
  5. What is the relationship beween gcd(a,b), lcm(a,b) and a×b?

You can check your answers using the Euclid's Algorithm CF Calculator in the next section or....
The greatest common divisor has the same primes as a and b but the power of each prime is the smaller of its powers in a and b.
720 = 24 × 32 × 51 × 70
168 = 23 × 31 × 50 × 71
GCD(720,168) = 23 × 31 × 50 × 70 = 24
The lowest common multiple of a and b has the same primes as in a and b with each raised to to the larger of its powers in each number. So
720 = 24 × 32 × 51 × 70
168 = 23 × 31 × 50 × 71
LCM(720,168) = 24 × 32 x 51 x 71 = 5040

When we multiply gcd(a,b) by lcm(a,b) we are using each prime power in both a and b. Therefore
gcd(a,b) × lcm(a,b) = a × b

A Euclid's Algorithm CF Calculator

This Calculator shows
  • Eucild's Algorithm for finding the GCD of two numbers a and b;
  • the list of the divisors of a and b with the greatest highlighted;
  • how Euclid's algorithm relates to the CF of a/b, for example for 45/16:

    This shows that 45/16 = [2; 1, 4, 3] as a continued fraction (CF).
  • a stylised picture of the "jigsaw of squares" for a/b where the sizes of the squares are shown followed by the number and direction of the repetitions.
    For the example above we have: An accurate picture of the squares-jigaw is also shown as on the left above.
    If the fraction is in its lowest terms this uses the same sizes as shown the stylised diagram.
    If the fraction can be reduced, the sizes of squares for the simplified fraction are shown together with the expansion factor needed (the gcd) to give the original numbers.
  • Given a list of the number of squares in a squares-jigaw rectangle (the CF) the Calculator can find the size of rectangle (the fraction) that gives that pattern.
    Note that if the list of squares ends with 1 then that square must be the same size as the previous squares so we would then just have one extra square of the previous size.
    For example: [.; ...,3,1] means there would have been 4 = 3 + 1 squares at the end: [.; ...,4]

The General form of a Simple Continued Fraction

  • If the numerators of the fractions are all 1, then the continued fraction is called a simple continued fraction. This is what we will mean when we use the term "continued fraction" - we will often abbreviate it to just CF - on this page.
  • A more general form of continued fraction has numerators which are not one but we only touch on this topic later on this page.
  • Usually all the numbers in a continued fraction (general or simple) will be positive although alternative forms are possible where negative whole numbers are allowed and we examine this kind later on this page.

Any and every fraction, P/Q where P and Q are whole, positive numbers can be written in the form of a continued fraction as shown above using Euclid's Algortihm in any of the various forms above. We know that any proper fraction can be expressed using a finite number of terms in its continued fraction.

We can write down any continued fraction such as

P/Q = a + 1/(b + 1/(c + 1/(d + ...))) just as a list of the numbers [a; b, c, ... ] . The first number, a, is special as it is the whole number part of the value. The rest is written as a list with comma separators (,) like this: P/Q = [a; b, c, d, ...] None of the values will be zero except possibly the first, the one before the semicolon (;).If the first is zero it means the value of the continued fraction is less than 1.

The first number in the list

For the continued fraction examples above, we can now write them as: 45/16 = [ 2; 1, 4, 3 ] 7/30 = [ 0; 4, 3, 2 ] = [ 0; 4, 3, 1, 1 ] (*)
If the first number in the list is 0, then the fraction it represents is less than 1.

An easy method of inverting a fraction

To take the reciprocal of an ordinary fraction, we just turn it upside-down.
For example, the reciprocal of   is or .

There is also a simple way to find the reciprocal of a continued fraction.
16/45, the reciprocal of 45/16 is just 0 + 1/(45/16), so we just insert a 0 at the front of the continued fraction in list form:
45/16 = [ 2; 1, 4, 3 ] and 16/45 = [0; 2, 1, 4, 3 ]
If the continued-fraction list already begins with a zero, as in 1/2 = [0; 2] then its reciprocal is found by removing the 0 from the front of the list:
2 = [  0 ; 2 ] = [ 2; ]
2/3 = [  0 ; 1, 2 ] = [ 1; 2 ] = 3/2
So all whole numbers n have the continued fraction form [ n ; ].

The last number in the list

One half is: 1/2 = [ 0; 2 ]which we can also write as 0+ 1/(1 + 1/1) = [ 0; 1, 1 ] In fact the last fraction in a continued fraction: 1/n can always be written as 1/( (n−1) + 1/1) so an ending [ ..., n ] = [ ... , n−1, 1] provided that n > 1.

There are two forms for the fraction 7/30 namely [0; 4, 3, 2] and [0; 4, 3, 1, 1]
This is true for all continued fractions. We can always write the last number, n, as (n-1) + 1/1 and so change the n to n − 1 and continue the fraction by one more number, 1, provided n > 1. Alternatively, if the last number is 1, we can remove it by adding it to the number before in the lost; So we have the general rule:

Every finite continued fraction ending with n>1 has two forms:
  • a CF ending with n > 1 i.e. [ ..... , n ]
  • a CF ending 1 i.e. replace the final n by (n-1) + 1/1 i.e. [ ..... , n-1 , 1 ]

You do the maths...

You might find the Combined Continued Fraction Calculator useful in this section.
  1. Express the following as continued fractions:
    1. 41/13 = [3; 6, 2] = [3; 6, 1, 1]
    2. 124/37 = [3; 2, 1, 5, 2] = [3; 2, 1, 5, 1, 1]
    3. 5/12 = [0; 2, 2, 2] = [0; 2, 2, 1, 1]
  2. The three rectangles in the picture are split into squares.
    Assuming that the smallest sized square has sides of length 1, what is the ratio of the two sides of each of the three rectangles?
    1+1/4 =5/4,
    2 + 1/(1 + 1/4) =2 + 4/5=14/5,
    1 + 5/14 = 19/14

  3. In the continued fraction for 45/16 = [ 2; 1, 4, 3 ], let's see what happens when we change the final 3 to another number.
    What fractions correspond to the following continued fractions (in list form)? Can you spot the pattern?
    1. [ 2; 1, 4, 4 ] 59/21 = 2.8095238095238093
    2. [ 2; 1, 4, 5 ] 73/26 = 2.80769230769231
    3. [ 2; 1, 4, 6 ] 87/31 = 2.80645161290323
    4. [ 2; 1, 4, 7 ] 101/36 = 2.8055555555555554
    5. [ 2; 1, 4, n ] (3+14n)/(1+5n)

    How is your pattern related to the proper fraction for [ 2; 1, 4 ] ?
    [2; 1, 4] = 14/5 and the fractions above approach this as n gets larger
    the numerators increasing by 14 and the denominators by 5
  4. This time we take the square numbers:
    1, 22=4, 32=9, 42=16, 52=25, 62=36, 49, 64, 81, 100, 121, 144, ...
    and form fractions from neighbouring squares.

    First let's look at this sequence of fractions formed from neighbouring square numbers in the list above. Change each of these fractions into a continued fraction.
    1. 25/16 = [1; 1, 1, 3, 2]
    2. 49/36 = [1; 2, 1, 3, 3]
    3. 81/64 = [1; 3, 1, 3, 4]
    4. 121/100 = [1; 4, 1, 3, 5]

    Can you spot the pattern for ?
    (2n+1)2 / (2n)2 = [1; n-1, 1, 3, n ]

    With thanks to Anthony Shaw who first brought these patterns to my attention.
  5. Here is another sequence of fractions formed from successive square numbers.
    Convert each of these fractions to a continued fraction.
    1. 36/25 = [1; 2, 3, 1, 2]
    2. 64/49 = [1; 3, 3, 1, 3]
    3. 100/81 = [1; 4, 3, 1, 4]
    4. 144/121 = [1; 5, 3, 1, 5]

    What is the pattern this time?
    (2n)2 / (2n - 1)2 = [1; n-1, 3, 1, n-1 ]

  6. Here is the Fibonacci Spiral from the Fibonacci Numbers in Nature page:
    If the smallest squares have sides of length 1, what continued fraction does it correspond to?
    What proper fraction is this?


  7. Convert the successive Fibonacci number ratios into continued fractions. What pattern do your answers show?
    1. 1/1 = [1; ]
    2. 2/1 = [2; ]
    3. 3/2 = [1; 1, 1] = [1; 2]
    4. 5/3 = [1; 1, 1, 1] = [1; 1, 2]
    5. 8/5 = [1; 1, 1, 1, 1] = [1; 1, 1, 2]

    If the ratio of consecutive Fibonacci numbers gets closer and closer to Phi, what do you think the continued fraction might be for Phi=1·618034... which is what the above fractions are tending towards?
  8. The last question made fractions from neighbouring Fibonacci numbers. Suppose we take next-but-one pairs for our fractions:
     5 8 13 21
     2 3 5 8
    Convert each of these to continued fractions, expressing them in the list form. What pattern do you notice?
    2 = [2;]
    3 = [3;]= [2; 1]
    5/2 = [2; 2] = [2; 1, 1]
    8/3 = [2; 1, 2] = [2; 1, 1, 1]
    13/5 = [2; 1, 1, 2] = [2; 1, 1, 1, 1]
    The ratios tend towards Phi2 = 1 + Phi = [2; 1]

Converting a Continued Fraction to an ordinary Fraction

By "unfolding" the CF from the right

The natural way is just to "fold" the continued fraction from the right-hand end, simplifying each part in turn:
[ 2; 1, 3, 4 ] = = = = = =
A short-cut is to notice that
[ ... , a, b ] = [ ... , a + 1/b ]
and we can keep using this rule to reduce the CF all the way down to a single fraction:
  [ 2; 1, 3, 4 ]
= [ 2; 1, 3 + 1/4 ] = [ 2; 1, 13/4 ]
= [ 2; 1 + 4/13 ] = [ 2; 17/13 ]
= [ 2 + 13/17; ] = [47/17; ]
= 47/17
Later we see a simpler method that works from left to right.

Surprising results about the REVERSE of the CF list

Here is a table of the CFs for all the sevenths fractions between 1/7 and 7/7. Each fraction is given to several decimal places, in its CF list form and, using the previous section, with its alternative CF list ending:
1/7 = 0.142857 142857 142857 …= [ 0; 7 ]= [ 0; 6, 1 ]
2/7 = 0.285714 285714 285714 …= [ 0; 3, 2 ]= [ 0; 3, 1, 1 ]
3/7 = 0.428571 428571 428571 …= [ 0; 2, 3 ]= [ 0; 2, 2, 1 ]
4/7 = 0.571428 571428 571428 …= [ 0; 1, 1, 3 ]= [ 0; 1, 1, 2, 1 ]
5/7 = 0.714285 714285 714285 …= [ 0; 1, 2, 2 ]= [ 0; 1, 2, 1, 1 ]
6/7 = 0.857142 857142 857185 …= [ 0; 1, 6 ]= [ 0; 1, 5, 1 ]
You may have noticed the following patterns in the table:
  • The decimal fractions are made up of the same set of repeating digits: ...142857... in a cycle: ... 142185142857142857 ...
  • Each decimal fraction begins at a different place in the cycle:  
  • These decimal fractions never end.
  • Each CF begins with 0 because all the fractions are less than 1
  • Each CF is finite
  • After the initial zero, every CF list also appears in the table in reverse.
It is the last property that we will investigate in this section.
Are all the above properties coincidences? Let's try another fraction:
1/8 = 0.125 = [ 0; 8 ]= [ 0; 7, 1 ]
2/8 = 0.25 = [ 0; 4 ]= [ 0; 3, 1 ]
3/8 = 0.375 = [ 0; 2, 1, 2 ]= [ 0; 2, 1, 1, 1 ]
4/8 = 0.5 = [ 0; 2 ]= [ 0; 1, 1 ]
5/8 = 0.625 = [ 0; 1, 1, 1, 2 ]= [ 0; 1, 1, 1, 1, 1 ]
6/8 = 0.75 = [ 0; 1, 3 ]= [ 0; 1, 2, 1 ]
7/8 = 0.875 = [ 0; 1, 7 ]= [ 0; 1, 6, 1 ]
This time the decimal fractions do not share the same repeating cycle and are not infinitely long but the final property - that all the CF lists after the initial zero appear in the table in reverse order - is still true!

So there are two "surprising results" and we can see examples of both in the tables at the start of this section.

Reversing a CF list will give a fraction with the same numerator

When we reverse the CF list of a fraction the new fraction will have the same numerator.
If we let [ a0; a1, ... , an−1, an ] be A/B > 1 which means that a0 > 0 and also
if we let [ a0; a1, ... , an−1 ] be C/D
then reversing the CF for A/B gives
[ an; an−1, ... , a0 ] which is A/C
For example: [1;1,1,2] = 8/5 = A/B and [1;1,1] = 3/2 = C/D so [2;1,1,1] = 8/3 = A/C

This result was known to Euler (see references below).

The first number can be transformed to produce the 1-complement of the fraction

We saw above that a finite CF's value is unchanged if we change the final term as follows:
if the last term X is 1, add it to the previous term: [1;2,3,1] = [1;2,4];
if the last term is bigger than 1, subtract one from it and append the 1 as a new final term.
We can do the same things to the first term after the integer part, but we obtain a different value:
If the value of [0; a, B] = x with a>1 and B the (value of the) rest of the list of CF terms, then the value of [0 ;1, a − 1,B] is 1 − x;
Since x⇒1−x is its own inverse operation, then the result applies transforming the second CF back to the first also.
If the integer term is not 0, then [A; a, B] = A + x ⇒ [A; 1, a−1, B] = A + (1−x)

This is very easily established by simple algebra since
[0; a,B] = 0+1/ (a+1/B) = B/(1+aB) whereas [0;1,a-1,B] = 1/(1+1(a-1+1/B)) = 1 − B/(1+aB)

The CF reversal result is proved in an amazing way by Harvey Mudd College's Professor of Mathematics: Art Benjamin in the first of these references:

  • Counting on Continued Fractions Arthur T Benjamin, F E Su, J J Quinn Maths Mag vol 73 (2000), pages 98-104
    also on Art's list of papers, preprints and books where there is a link to a PDF version to view.
  • De Fractionibus Continuis Dissertatio written in 1737 but only published in 1744. It has been translated into English by M F Wyman and B F Wyman in An Essay on Continued Fractions, Math Systems Theory vol 18 (1985, Springer-Verlag) pages 295-328 PDF
  • A T Benjamin, J J Quinn, W Watkins, Proofs That Really Count published by The Mathematical Association of America (Aug 2003), 208 pages.
    This is a wonderful book on using counting methods in proofs by induction to prove many results in combinatorics and number theory which includes many Fibonacci number formulae. The authors make the proofs both easy to understand and fun too!

Euler showed that the CFs [ a1; a2, ... an] and its reversal [ an; an-1, ... a1 ] have the same numerators but we must note that the first and last terms in both CFs are non-zero: see Davenport's book in the References section at the foot of this page.

The Stern-Brocot Fraction tree and CFs

On another page we looked at making a simple tree of all the fractions. If we restrict fractions to mean pure fractions, positive but less than 1, then, starting from 0/1 and 1/1 as our starting row we can keep making new rows by copying the old row and between every fraction inserting a new one:
oldNEWold
aa + bb
pp + qq
Level 10/11/1
Level 20/11/21/1
Level 30/11/31/22/31/1
Level 40/11/41/32/51/23/52/33/41/1
Level 50/11/51/42/71/33/82/53/71/24/73/55/82/35/73/44/51/1
If we now find the CFs for each of these, a pleasant surprise is that the CFs of level L's new fractions are all the ways writing L as a sum of smaller numbers! These are called compositions of L and include the number L as a composition too.
For the difference between a partition of a number and a composition of a number see the same link as above.
Remember that any CF can be written both as a list of terms that end in 1 or else end in a number greater than 1 so every fraction has two CFs.
For instance
  • level 3 introduces 1/3=[0;3]=[0;2,1] and 2/3=[0;1,2]=[0;1,1,1] and we have four compositions of 3: 3 = 2 + 1 = 1 + 2 = 1 + 1 + 1 are all the ways to write 3 as a sum where the order of the numbers matters (since [0;1,2] is not the same as [0;2,1]). These are called compositions of 3.
    So 3 has just four compositions.
  • Similarly on level 4, the new fraction's CF's are 1/4=[0;4]=[0;3,1], 2/5=[0;2,2]=[0;2,1,1], 3/5=[0;1,1,2]=[0;1,1,1,1], 3/4=[0;1,3]=[0;1,2,1] and these are the 8 compositions of 4.
The same applies to every row.

See The Stern-Brocot Tree on the Fractions in the Farey Series and the Stern-Brocot Tree page at this site.

A Fraction ↔ CF Calculator

The and buttons will convert a Fraction to a CF and vice-versa and the converted value is shown in the or boxes too. Note a CF is input as and any following numbers are separated by commas: . Here are some investigations for you to do:

You do the maths...

Use the Calculator above.
  1. Make a list of the CF lists for all the fractions less than 1 with
    1. a denominator of 5 (1/5, 2/5, 3/5, 4/5)
    2. a denominator of 6
    3. denominators 7 and 8 are above in this section
    4. a denominator of 9
    The calculator link above is useful as it keeps the results in a window so you can use cut-and-paste. Use your results to answer the following questions.
    CFs for N/D:
    ↓DN→12345678
    5 [0; 5]
    [0; 4, 1]
    [0; 2, 2]
    [0; 2, 1, 1]
    [0; 1, 1, 2]
    [0; 1, 1, 1, 1]
    [0; 1, 4]
    [0; 1, 3, 1]
    6 [0; 6]
    [0; 5, 1]
    [0; 3]
    [0; 2, 1]
    [0; 2]
    [0; 1, 1]
    [0; 1, 2]
    [0; 1, 1, 1]
    [0; 1, 5]
    [0; 1, 4, 1]
    7 [0; 7]
    [0; 6, 1]
    [0; 3, 2]
    [0; 3, 1, 1]
    [0; 2, 3]
    [0; 2, 2, 1]
    [0; 1, 1, 3]
    [0; 1, 1, 2, 1]
    [0; 1, 2, 2]
    [0; 1, 2, 1, 1]
    [0; 1, 6]
    [0; 1, 5, 1]
    8 [0; 8]
    [0; 7, 1]
    [0; 4]
    [0; 3, 1]
    [0; 2, 1, 2]
    [0; 2, 1, 1, 1]
    [0; 2]
    [0; 1, 1]
    [0; 1, 1, 1, 2]
    [0; 1, 1, 1, 1, 1]
    [0; 1, 3]
    [0; 1, 2, 1]
    [0; 1, 7]
    [0; 1, 6, 1]
    9 [0; 9]
    [0; 8, 1]
    [0; 4, 2]
    [0; 4, 1, 1]
    [0; 3]
    [0; 2, 1]
    [0; 2, 4]
    [0; 2, 3, 1]
    [0; 1, 1, 4]
    [0; 1, 1, 3, 1]
    [0; 1, 2]
    [0; 1, 1, 1]
    [0; 1, 3, 2]
    [0; 1, 3, 1, 1]
    [0; 1, 8]
    [0; 1, 7, 1]
  2. A composition of N is a sequence (list) of 1 or more positive (non-zero) numbers that sum to L.
    Numbers can be repeated (so the lists are not always sets) and the order of the numbers in the list matters so that {1,1,2}, {1,2,1} and {2,1,1} are classed as different partitions of 4.
    1. Prove that there are 2N−1 paritions of N.
    2. Prove that exactly half of partitions of N end in 1 (and exactly half do not).
    3. Prove that there are 2L−2 new fractions on level L of the Stern-Brocot Fraction tree.
  3. Some fractions have a CF which, after the initial 0 is the same when reversed:
    e.g.
    1/6 = [0; 6]
    6/7 = [0; 1, 5, 1]
    5/8 = [0; 1, 1, 1, 1, 1 ]
    Such sequences are called palindromes or palindromic sequences.
    Find the fractions which do not have a palindromic CF in the table above.
    2/7, 3/7, 4/7, 5/7
    2/9, 4/9, 5/9, 7/9

Continued Fractions for decimal fractions?

If we look at irrational numbers (numbers which cannot be written exactly as a fraction) we will find no pattern in their decimal fractions. For instance, here is √2 to 200 decimal places (read as text, left to right, line by line):
41421 35623 73095 04880 16887 24209 69807 85696 71875 37694
80731 76679 73799 07324 78462 10703 88503 87534 32764 15727
35013 84623 09122 97024 92483 60558 50737 21264 41214 97099
93583 14132 22665 92750 55927 55799 95050 11527 82060 57147
...
Indeed, it is not too difficult to show that, if any decimal fraction ever repeats, then it must be a proper fraction, that is a rational number - see the references section at the foot of this page.
The converse is also true, i.e. that every rational number has a decimal fraction that either stops or eventually repeats the same cycle of digits over and over again for ever.

There is a pleasant surprise here since every square-root has a repeating pattern in its continued fraction.

But what about continued fractions for numbers which we only have in the form of a decimal? There are two methods of converting them into continued fractions: using the decimal itself or finding a proper fraction for the decimal number. Both methods are explained here.

Direct conversion of a decimal to a CF

If we look again at the jigsaw-squares method at the top of this page or further down at Euclid's algorithm then both use the whole number of times one number goes into another. Really all we are using in that case is the whole number part of the value. With decimal numbers, we already have that part - it is just the part before the decimal point!

The method is very easy on a calculator when you use the subtract button and the 1/x or x-1 button only!

Input the decimal number.

  1. Write down the whole number part (before the decimal point) as the next value in the CF list.
    For an input value less than 1, this will be 0.
  2. Subtract it from the display to get a value less than 1.
  3. If 0 is showing, stop
    otherwise press the 1/x button
  4. Start again with the new number which is bigger than 1 in the display.
You can try this on √2, e, π or any computed value but be careful as rounding errors will eventually build up and then the CF terms are meaningless.

For example, 2·875.

  • has a whole part of 2 so write that down to begin its continued fraction:
    2·875 = [2; ...
  • Subtract the 2 to get 0.875
  • Press 1/x to get 1.14285714285714
  • Starting again: write down the whole number part: 1, so the CF is now
    2·875 = [2; 1, ...
  • Subtract the 1 to get 0.14285714285714
  • Press 1/x to get 7.00000000000014
  • Start again: write down 7 so the CF is now
    2·875 = [2; 1, 7
  • Subtract the 7 to get 0.00000000000014
  • This is practically 0 so we stop here allowing for rounding errors.

2.875 = [2; 1, 7]
Checking shows that when we expand [2; 1, 7] we have 23/8 which is 2 + 7/8 = 2.875 exactly.

You do the maths...

You might find the Combined Continued Fraction Calculator useful in this section.
  1. Convert 64/29 into a decimal fraction and approximate it by rounding it off to 3 dps.
    Now convert that decimal fraction to a CF using the method of the last section.
    Was it easy to see when to stop if the real value of our decimal was 64/29?
    64/29 = 2.206896551724138 = 2.207 to 3 dps
    • write down 2 and subtract it: 0.207
    • 1/x gives 4.83091787439614
    • write down 4, subtract it: 0.83091787439614
    • 1/x gives 1.20348837209302
    • write down 1, subtract it: 0.20348837209302
    • 1/x gives 4.91428571428579
    • write down 4, subtract it: 0.91428571428579
    • 1/x gives 1.09374999999991
    • write down 1, subtract it: 0.09374999999991
    • 1/x gives 10.66666666667691
    • write down 10, subtract it: 0.66666666667691
    • 1/x gives 1.49999999997695
    • write down 1, subtract it: 0.49999999997695
    • 1/x gives 2.0000000000922
    • write down 2, subtract it: 0.0000000000922
    The displayed number is now almost 0 so stop.
    2.207 = [2; 4, 1, 4, 1, 10, 1, 2 ]
    Converting the CF to a fraction gives 2207/1000 = 2.207 so the CF is correct and we were right to stop when we did discarding the residual value as rounding error.

Converting a Decimal to a Fraction

If we have a number in the form of decimal fraction, such as 2·875 then we can always represent it as an exact proper fraction by using a denominator which is a big enough power of 10:
  • The number of places we have to move the decimal place to the right until it comes after all the decimal digits
  • is the power of ten that appears in the denominator and
  • is also the number of 0's in the power of ten in the denominator.
For instance,
  • 1·2 means moving the decimal point 1 place to the right so 1·2 is just 12/10
  • Similarly 2·875 is 2875/1000
  • and 0.00075 is 75/100000.
Since all the example decimals are all now fractions, we can now use Euclid's algorithm from earlier on this page to express them as continued fractions.
There is no need to reduce the proper fractions to their lowest forms - Euclid's algorithm will still give the correct CF.

This time, when we convert 2·875 to an equivalent fraction we get 2875/1000 and Euclid's algorithm gives:

2875 = 2 ×1000 + 875
1000 = 1 × 875 + 125
875 = 7 × 125
so 2875/1000 = [2; 1, 7] exactly.
If 2·875 was an exact value then its CF is exactly [2; 1, 7]; if it was only an approximation then [2; 1, 7] is as accurate as we can get as a CF. So, provided we have a finite number of decimal places, we can get a CF equivalent to that decimal value. But suppose we know a number exactly as a decimal and that decimal value does not end? An example is 0.3333.... which we might spot is exactly 1/3.

A CF Calculator for Expressions

The following Calculator might help.
The calculations are from the evaluated numerical value of the input expression which is limited to about 16 places of decimals. Eventually the CF terms will be solely due to rounding error. This is detected and the CF terms shown are correct (except for the final term sometimes), with ... indicating the limit of the conversion.
Since the Calculator uses your Browser's Javascript capability, the expressions you type in needs to use JavaScript syntax:
Expression → CF C A L C U L A T O R

Proper Fractions and Continued Fraction Patterns

Before we branch out into infinite continued fractions in the following sections, let's pause to look at some patterns in (proper) fractions first.

CFs of ( 1 + 1/n )2

To start off your investigations, what patterns can you spot in this table:
n(1+1/n)2 = CF
1(1+1/1)2[ 4; ]
3(1+1/3)2[ 1; 1,3,1,1 ]
5(1+1/5)2[ 1; 2,3,1,2 ]
7(1+1/7)2[ 1; 3,3,1,3 ]
9(1+1/9)2[ 1; 4,3,1,4 ]
11(1+1/11)2[ 1; 5,3,1,5 ]
13(1+1/13)2[ 1; 6,3,1,6 ]
15(1+1/15)2[ 1; 7,3,1,7 ]
n(1+1/n)2 = CF
2(1+1/2)2[ 2; 4 ]
4(1+1/4)2[ 1; 1,1,3,2 ]
6(1+1/6)2[ 1; 2,1,3,3 ]
8(1+1/8)2[ 1; 3,1,3,4 ]
10(1+1/10)2[ 1; 4,1,3,5 ]
12(1+1/12)2[ 1; 5,1,3,6 ]
14(1+1/14)2[ 1; 6,1,3,7 ]
16(1+1/16)2[ 1; 7,1,3,8 ]
It seems there are two patterns here, one for even n and one for odd.

CFs of ( 1 + 1/n )3

Extending the fractions to cubes, we have the following table:
CFs for (1+1/n)3
 1=[ 8; ]
 7=[ 1; 2,33,1,4 ]
13=[ 1; 4,60,1,3,2 ]
19=[ 1; 6,87,1,3,3 ]
 2=[ 3; 2,1,2 ]
 8=[ 1; 2,2,1,3,1,1,2,3 ]
14=[ 1; 4,2,1,6,1,1,2,2,2 ]
20=[ 1; 6,2,1,9,1,1,2,2,3 ]
 3=[ 2; 2,1,2,3 ]
 9=[ 1; 2,1,2,4,2,2,1,2 ]
15=[ 1; 4,1,2,7,2,2,1,1,2 ]
21=[ 1; 6,1,2,10,2,2,1,1,3 ]
 4=[ 1; 1,20,3 ]
10=[ 1; 3,47,3,2 ]
16=[ 1; 5,74,3,1,2 ]
22=[ 1; 7,101,3,1,3 ]
 5=[ 1; 1,2,1,2,11 ]
11=[ 1; 3,2,1,5,11,2 ]
17=[ 1; 5,2,1,8,11,1,2 ]
23=[ 1; 7,2,1,11,11,1,3 ]
 6=[ 1; 1,1,2,2,1,12 ]
12=[ 1; 3,1,2,5,1,11,2 ]
18=[ 1; 5,1,2,8,1,11,3 ]
24=[ 1; 7,1,2,11,1,11,4 ]
Patterns here are certainly harder to spot but they seem to go in sixes this time.
David Terr wrote to me in October 2013 with the following patterns in the cubes:
Mod 6 formCF
(1+1/(6n+1))3: [ 1; 2n, 27n+6, 1, 3, n ]
(1+1/(6n+2))3: [ 1; 2n, 2, 1, 3n, 1, 1, 2, 2, n ]
(1+1/(6n+3))3: [ 1; 2n, 1, 2, 3n+1, 2, 2, 1, 1, n ]
(1+1/(6n+4))3: [ 1; 2n+1, 27n+20, 3, 1, n ]
(1+1/(6n+5))3: [ 1; 2n+1, 2, 1, 3n+2, 11, 1, n ]
(1+1/(6n))3: [ 1; 2n−1, 1, 2, 3n−1, 1, 11, n ]
These patterns are indeed true and his discovery suggests many similar questions to ask about powers of finite fractions and the form of their continued fraction.

But now we turn our attention to some infinite continued fractions which, maybe surprisingly, have some very simple forms.

Continued fractions for square-roots

A Simple Way to find √n

Here is another way to introduce or "discover" continued fractions based on finding the square-root of a number. This method differs from those earlier at the top of the page in that it gives us an infinitely long continued fraction, but this turns out to have some very useful properties.

Take, for example, √5. The nearest square below 5 is 4, so we know √5 begins with 2. Let's write:

√5 = 2 + x
5 = (2 + x)2
   = 4 + 4x + x2
   = 4 + x( 4 + x)
If we rearrange the last line we have
5 − 4 = x(4 + x)
1 = x(4 + x)
Now we have a formula for x, we can use it on the right-hand side and get:
x  →  1  →  1  →  ...
4 + x4 +
 
When we repeat this, we get a continued fractionwhich never ends!
If we put x back in the original line: √5 = 2 + x
√5 = 2 + 1 = 2 + 1 = 2 + 1
4 + x4 + 14 + 1
4 + x4 + 1
4 + x
Here is another example for √6.
√6 = 2 + x
6 = (2 + x)2 = 4 + 4x + x2
2 = 4x + x2 = x(4 + x)
x = 2 = 2
4 + x4 + 2
4 + x
This time, we can do some careful simplification by dividing top and bottom by 2:
x = 2 = 2 = 1
4 + x4 + 22 + 1
4 + x4 + x
So this time our infinite continued fraction for √6 is
√6 = 2 + 1
2 + 1
4 + 1
2 + 1
4 + ...
This is our first example of a general continued fraction since the numerators of the fractions are not 1. It happens that each of the above simplify to give a simple CF. Can we do this in general?

Suppose n is not a perfect square and that √n = a + x where a2 is any square number less than n. Using the method above, what is the general formula for √n as a continued fraction without reducing the numerators to 1?

√n = a + x
Square both sides:
n = a2 + 2ax + x2
Rearranging to make x a factor:
n − a2 = x ( 2a + x)

Substituting for x in the top equation:
√n = a + x = a + n − a2 = a + n − a2 = ...
2a + x2a + n − a2
2a + x

You do the maths...


What use is an infinite continued fraction?

Is there any advantage in this infinitely long fractional representation? Yes!
We can stop the continued fraction at any point and then reduce the shortened form to an ordinary fraction (see below). Each time the fraction is a better approximation to the actual square-root than if we stopped it at any earlier point.
In fact, the approximations found by this method are the best approximations possible when the numerators are 1.

A variation with numerators that are always 1

Sometimes with the simple way to find √n as a CF, we get numerators which are 1, as with √5 above, but not always.
Sometimes it is not too difficult to divide numerators and denominators to reduce the numerator to one as in the √6 example, but in other cases it is much more complicated.

There is a method which will find the exact CF for any (whole-number) square-root and the numerators are always 1. It is not quite as simple as the method above, but it only uses the mathematics and algebra of secondary school.
We will need this useful technique:

Eliminating Square-roots from denominators

The important part uses a special algebraic method that applies only to square roots. It changes a fraction with a square-root in the denominator to a fraction with a square root on top.

If we have a fraction with (√A + B) in the denominator then the secret is to multiply top and bottom by (√A − B), that is, keep the numbers the same but just change the sign between them. If we had √A − B in the denominator then we would use √A + B instead. If you are good at algebra you will recognise that x+y and x−y are the two factors of x2 − y2. You can multiply out the brackets to check this.
For our denominator, we now have (√A + B)(√A − B) which expands to (A − B2) and, since A and B are integers, this is a whole number!

Here is a worked example:

So we have transformed a fraction with a square-root term in the denominator to one with a square root term in the numerator.

An algorithm to find a simple CF for any square-root

In the following we assume n is not an exact square number.
The steps in the algorithm for finding a simple CF for √n are:
Step 1:
Find the nearest square number less than n
Let's call it m2, so that m2<n and n<(m+1)2.
Remember this value as you will need it when you repeat this step!
For example, if n=14 and we are trying to find a CF for √14 then here are two quick ways to find this number
  • 9 = 32 is the nearest square below 14, so m = 3 and m2=9 < n < (m+1)2=16
  • use your calculator:
    and just ignore the part after the decimal point! The number showing is m.
    For our example, √14 is 3.741... so the number we want initially is 3
This whole number part starts off our list of numbers for the continued fractionand is used whenever we return to this step. For instance, the next time we do this step in our example is with (√14 + 3)/5. Since the nearest whole number below √14 is 3, then we look at (3+3)/5= 6/5 and now the integer part is 1.

Now, √n = m + 1/x where n and m are whole numbers.

Step 2:
Rearrange the equation of Step 1 into a form involving the square root which will appear as the denominator of a fraction: x = 1 / (√n - m)
Step 3:
We now have a fraction with a square-root in the denominator. Use the method above to eliminate the square-root from the denominator.
In this case, multiply top and bottom by (√ n + m) and simplify.
either Step 4A:
stop if this expression is the square root plus the original first integer.
or Step 4B:
otherwise start again from Step 1 but using the expression at the end of Step 3
The square root as a continued fraction is the initial whole number from Step 1 and the period is all the numbers but adding the final integer of Step 4 to the initial integer to form the period.

We will take √14 and see how we find the continued fraction [ 3; 1,2,1,6, 1,2,1,6, 1,2,1,6, ... ] = [ 3; 1,2,1,6 ] using the algorithm above:

In order to distinguish the x's at each stage repeating the steps of the method, we will use subscripts to distinguish the different x's as x changes: x1, then x2, x3 and so on:

Источник: [https://torrent-igruha.org/3551-portal.html]
, PG Calculator 1.5a serial key or number

It enhances speed and performance of your PC. It detect and remove all those virus, Trojans, hacktools and  online threats. strongemppimg src"https:prosoft4free. files. wordpress.

PG Calculator 1.5a serial key or number

Com, the most comprehensive source for safe, trusted, and spyware-free downloads on the Web. Download Snaptube What will happen when you click Free Download. This file will be downloaded from an external source. Snaptube : Video amp; MP3 Download.

.

What’s New in the PG Calculator 1.5a serial key or number?

Screen Shot

System Requirements for PG Calculator 1.5a serial key or number

Add a Comment

Your email address will not be published. Required fields are marked *