Skip to content

Instantly share code, notes, and snippets.

@doskir
Created August 12, 2011 18:26
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save doskir/1142633 to your computer and use it in GitHub Desktop.
Save doskir/1142633 to your computer and use it in GitHub Desktop.
Solution for project euler problem 65
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Numerics;
using System.Text;
namespace Problem_65
{
class Program
{
static void Main(string[] args)
{
Stopwatch sw = new Stopwatch();
sw.Start();
StringBuilder eFractionString = new StringBuilder();
eFractionString.Append("2;1");
for (int i = 2; i <= 66; i+=2)
eFractionString.Append("," + i + ",1,1");
List<Convergent> convergents = ConvergentsFromString(eFractionString.ToString());
BigInteger sumOf100th = 0;
BigInteger numeratorOf100th = convergents[99].Numerator;
while (numeratorOf100th >= 10)
{
sumOf100th += numeratorOf100th%10;
numeratorOf100th /= 10;
}
sumOf100th += numeratorOf100th;
sw.Stop();
Console.WriteLine(sumOf100th);
Console.WriteLine("Took {0} ms.", sw.ElapsedMilliseconds);
Console.ReadLine();
}
static List<Convergent> ConvergentsFromString(string s)
{
//accepts the format 2;1,2,3,4,5,6,7,8,9
//dummy convergent to help in the calculation
var convergents = new List<Convergent> {new Convergent {Numerator = 1, Denominator = 0}};
BigInteger firstNumber = Int32.Parse(s.Substring(0, s.IndexOf(";")));
convergents.Add(new Convergent {Numerator = firstNumber, Denominator = 1});
s = s.Remove(0, s.IndexOf(";")+1);
string[] parts = s.Split(new string[] {","}, StringSplitOptions.RemoveEmptyEntries);
long[] multipliers = new long[parts.Length + 1];
for (int i = 0; i < parts.Length; i++)
multipliers[i + 1] = Int32.Parse(parts[i]);
for (int i = 2; i <= multipliers.Length; i++)
{
BigInteger numerator = convergents[i - 1].Numerator*multipliers[i - 1] + convergents[i - 2].Numerator;
BigInteger denominator = convergents[i - 1].Denominator*multipliers[i - 1] + convergents[i - 2].Denominator;
convergents.Add(new Convergent {Numerator = numerator, Denominator = denominator});
}
convergents.RemoveAt(0);
return convergents;
}
struct Convergent
{
public BigInteger Numerator;
public BigInteger Denominator;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment