Tuesday 21 April 2009

PROJECT EULER #64

Link to Project Euler problem 64

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

√N = a_(0) +
1


a_(1) +
1



a_(2) +
1




a_(3) + ...

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:

a_(0) = 4,
1

√23—4
=
√23+4

7
= 1 +
√23—3

7
a_(1) = 1,
7

√23—3
=
7(√23+3)

14
= 3 +
√23—3

2
a_(2) = 3,
2

√23—3
=
2(√23+3)

14
= 1 +
√23—4

7
a_(3) = 1,
7

√23—4
=
7(√23+4)

7
= 8 + √23—4
a_(4) = 8,
1

√23—4
=
√23+4

7
= 1 +
√23—3

7
a_(5) = 1,
7

√23—3
=
7(√23+3)

14
= 3 +
√23—3

2
a_(6) = 3,
2

√23—3
=
2(√23+3)

14
= 1 +
√23—4

7
a_(7) = 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?

This was certainly an education in continued fractions. Having understood them the trick is to find a way to calculate the salient numbers for the next iteration. 62.5 ms. Uncomment the foreach loop to print the series.


using System;
using System.Collections.Generic;

namespace project_euler
{
class Program
{
static void Main()
{
//Problem 64
DateTime start = DateTime.Now;
Dictionary<int, List<int>> numbers = new Dictionary<int, List<int>>();
for (int number = 2; number <= 10000; number++)
{
bool repeat = false;
int a = (int)Math.Sqrt(number);
List<int> sequence = new List<int> { a };
numbers.Add(number, sequence);
int x = 1;
do
{
if (Math.Sqrt(number) - (int)Math.Sqrt(number) == 0) break;
int b = number - a * a;
int integerPart = x * ((int)Math.Sqrt(number) + a) / b;
numbers[number].Add(integerPart);
a = -(a - integerPart * (b / x));
x = (b / x);
if (integerPart == 2 * numbers[number][0]) repeat = true;
} while (!repeat);
}
int oddSequence=0;
foreach (KeyValuePair<int, List<int>> pair in numbers)
{
if ((pair.Value.Count - 1)%2 != 0)
oddSequence++;
//Console.Write(pair.Key + ": ");
//foreach (int sequence in pair.Value)
// Console.Write(sequence + ", ");
//Console.WriteLine();
}
Console.WriteLine(oddSequence);
TimeSpan time = DateTime.Now - start;
Console.WriteLine("This took {0}", time);
Console.ReadKey();
}
}
}

No comments: