# Continued fractions

## The MathBlog tools collection updated

Just wanted to make a bit of advertisement for the tool section of the website which have been updated and new tools added.

Bjarki has been busy and developed several new tools which might come in handy for you when trying to see if a hypothesis could lead to a solution for the problem you are sitting with.

## Updated tools

First of all the Prime factorization tool has been updated.  So now it gives you a little more than just the factorization. It gives you the number of distinct factors, the number of divisors and not least the value of Euler’s totient function. Yep that’s right, so head over and check it out. Continue reading →

Posted by Kristian in Other, 2 comments

## Project Euler 66: Investigate the Diophantine equation x^2 − Dy^2 = 1.

Based on the problem description for Problem 66 of Project Euler I thought we had left the continued fractions for a while. Once I started reading up on the maths behind it and trying to solve the problem I got quite a lot wiser. But let’s start from the beginning and look at the problem description which reads

Consider quadratic Diophantine equations of the form:

x2 – Dy2 = 1

For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 1.

It can be assumed that there are no solutions in positive integers when D is square.

By finding minimal solutions in x for D = {2, 3, 5, 6, 7}, we obtain the following:

32 – 2×22 = 1
22 – 3×12 = 1
92 – 5×42 = 1
52 – 6×22 = 1
82 – 7×32 = 1

Hence, by considering minimal solutions in x for D ≤ 7, the largest x is obtained when D=5.

Find the value of D ≤ 1000 in minimal solutions of x for which the largest value of x is obtained.

Posted by Kristian in Project Euler, 12 comments

## Project Euler 65: Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

They really went crazy with the whole continued fractions theme. Project Euler‘s problem 65 as this one is about the continued fraction of e. The problem reads

The square root of 2 can be written as an infinite continued fraction.

 √2 = 1 + 1 2 + 1 2 + 1 2 + 1 2 + …

The infinite continued fraction can be written, √2 = [1;(2)], (2) indicates that 2 repeats ad infinitum. In a similar way, √23 = [4;(1,3,1,8)].

It turns out that the sequence of partial values of continued fractions for square roots provide the best rational approximations. Let us consider the convergents for √2.

 1 + 1 = 3/2 2
 1 + 1 = 7/5 2 + 1 2
 1 + 1 = 17/12 2 + 1 2 + 1 2
 1 + 1 = 41/29 2 + 1 2 + 1 2 + 1 2

Hence the sequence of the first ten convergents for √2 are:

1, 3/2, 7/5, 17/12, 41/29, 99/70, 239/169, 577/408, 1393/985, 3363/2378, …

What is most surprising is that the important mathematical constant,
e = [2; 1,2,1, 1,4,1, 1,6,1 , … , 1,2k,1, …].

The first ten terms in the sequence of convergents for e are:

2, 3, 8/3, 11/4, 19/7, 87/32, 106/39, 193/71, 1264/465, 1457/536, …

The sum of digits in the numerator of the 10th convergent is 1+4+5+7=17.

Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

Posted by Kristian in Project Euler, 2 comments

## Project Euler 64:How many continued fractions for N ≤ 10000 have an odd period?

Problem 57 was all about continued fractions, and in Problem 64 of Project Euler we are visiting that subject again. The problem reads

All square roots are periodic when written as continued fractions and can be written in the form:

 √N = a0 + 1 a1 + 1 a2 + 1 a3 + …

For example, let us consider √23:

 √23 = 4 + √23 — 4 = 4 + 1 = 4 + 1 1 √23—4 1 + √23 – 3 7

If we continue we would get the following expansion:

 √23 = 4 + 1 1 + 1 3 + 1 1 + 1 8 + …

The process can be summarised as follows:

 a0 = 4, 1 √23—4 = √23+4 7 = 1 + √23—3 7 a1 = 1, 7 √23—3 = 7(√23+3) 14 = 3 + √23—3 2 a2 = 3, 2 √23—3 = 2(√23+3) 14 = 1 + √23—4 7 a3 = 1, 7 √23—4 = 7(√23+4) 7 = 8 + √23—4 a4 = 8, 1 √23—4 = √23+4 7 = 1 + √23—3 7 a5 = 1, 7 √23—3 = 7(√23+3) 14 = 3 + √23—3 2 a6 = 3, 2 √23—3 = 2(√23+3) 14 = 1 + √23—4 7 a7 = 1, 7 √23—4 = 7(√23+4) 7 = 8 + √23—4

It can be seen that the sequence is repeating. For conciseness, we use the notation √23 = [4;(1,3,1,8)], to indicate that the block (1,3,1,8) repeats indefinitely.

The first ten continued fraction representations of (irrational) square roots are:

√2=[1;(2)], period=1

√3=[1;(1,2)], period=2

√5=[2;(4)], period=1

√6=[2;(2,4)], period=2

√7=[2;(1,1,1,4)], period=4

√8=[2;(1,4)], period=2

√10=[3;(6)], period=1

√11=[3;(3,6)], period=2

√12= [3;(2,6)], period=2

√13=[3;(1,1,1,1,6)], period=5

Exactly four continued fractions, for N ≤ 13, have an odd period.

How many continued fractions for N ≤ 10000 have an odd period?

I shall be the first person here to admit that all I got from the problem description was the question, the helping text didn’t help me at all. So I had to ask uncle wiki how to solve this problem, and it returned me an algorithm which I could use. Continue reading →

Posted by Kristian in Project Euler, 13 comments