Project Euler Problem 57

Problem 57

Solved a simple problem from Euler again.You can have a look at the problem statement below.

Problem statement:

It is possible to show that the square root of two can be expressed as an infinite continued fraction.

 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5

1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?

Approach:

If you look at the fractional progressions below(same given on the question as well),you will find that there is a clear arithmetical pattern to it.

3/2 , 7/5 , 17/12 , 41/29

you can clearly see that the denominator on every fraction is the summing of both nominator and denominator of the previous fraction.

for (e.g) take the fraction 3/2

3 (nom) / 2 (denom) => 3+2 = 5 (which is the denom for the next fraction 7/5)

similarly  for the next fraction 7/5

7+5= 12 (which is the denominator for the next fraction 17/12)

You will also see that the numerator on every successive fraction is the sum of previous fraction's numerator and the corresponding denominator multiplied with 2.

Lets take the first fraction on our list again which is 3/2

Numerator=3

Denominator=2

Next Numerator = (denominator x 2) + numerator

           7             =         (2 x 2)          +      3

as we have seen already the new denominator for the next fraction,would be Numerator + denominator of previous fraction(3/2)

3+2=5.

and we get the next fraction as 7/5

So to reiterate again the formula that is used to calculate the next fractions.

Next Denominator= Current Numerator + Current Denominator

Next numerator = Current Numerator+(Current Denominator X 2)

C# Code

C# with its primitive data type cannot really handle the kind of number crunching that is required for this program.As you will see the numbers can get really big before the program can complete.The basic reason is c# never was designed to do such calculations in the first place.But still framework in its release 4.5 has introduced a new datatype called BigInteger that saves the day for this challenge.BigInteger "Represents an arbitrarily large signed integer."-MSDN

This Euler challenge was basically to generate all fractions up to 1000 times and then see out of all those fractions,how many of them have their numerator's digit count greater than the denomintor's digit count.

Here is the code.Download

Not sharing my output as it would be a spoiler. Still what i would like to share is the numerator part of the fraction that got generated on the 1000th iteration.

72016336943533875056131468444247239328723197628440751797201898063588088312700201943482948477109536203740206649612702729920170001354454107173480483962605519493117789821758457767858986227019805650639002566946496865364666543562826303377877700877266135276209125278037204443042487153089226849544681245300260167141025277156482737568934079466850318276966893735585103845471745828701580706481

Yes that's a number and thanks to BigInteger :)

happy coding !!!
Polybius

Click here for other Topics

Contents at a Glance

1. Radix Sort - Part-I
2. Radix Sort - Part-II
3. Run length encoding
4. Sieve of Eratosthenes
5. Pascal's Triangle
6. Project Euler Problem 112 - Bouncing Numbers
7. Ulam Spiral
8. Project Euler Problem 57 
9. Project Euler Problem 98

Ulam Spiral

• How it works?
• C# Code

Prime spiral

Ulam spiral is a mathematical structure where numbers are written in a spiral form starting from 1.It is said that this spiral came into existence during a boring meeting,which Ulam was attending.During the meet he got bored and started doodling on his paper a number spiral with 1 at the center and the next numbers following it in a spiral fashion.What surprised Ulam was not the spiral but the placements of the prime numbers on the spiral.As you can see in the second image(right),the prime numbers have aligned themselves in a diagonal fashion.The Ulam spiral is used for understanding the tendencies and behaviors of prime numbers.This post will show you how to generate Ulam spirals and in my next post i will use it to solve a Project Euler problem.

A Ulam spiral on the left and the right spiral with prime numbers marked
courtesy wiki

The above image is a matrix of dimension 7 x 7 with N 49.

Lets take a small matrix of dimension 4 x 4 and see how we can work out.(Max number :16)

A 4 x 4 Matrix with two cycles( Cycle 1- Gray,Cycle 2 -Red) 

Since matrix is a four sided representation every cycle will have 4 iterations(top,left,bottom,right).The gray and red marks in the above image represents two different cycles.

A cycle will be deemed complete when all the cells for that cycle is filled.To work out the number of cells per cycle do (dimension -1) * 4

if we apply this for both the cycles we get

Cycle 1    4-1 * 4 =12

Cycle 2    2-1 * 4= 4 (dimension of red block is 2)

So we have a total of 16 cells to fill ,with 12 cells to fill in cycle 1 and 4 cells to complete in cycle 2.

We will start filling the numbers from the top right corner of matrix,moving left with the placement of every number and cycle in a anticlockwise movement filling all the four sides of every cycle.

By changing the row index and column index of our array ,we can easily move in the direction we want.The direction information will be stored in a small array which would instruct the program to go in a certain direction.{E,S,W,N} E- East,S-South,W-West,N-North.

On first iteration of cycle 1 we would move East and during the second iteration Move South.

On third move West and on the final iteration move North(which is what the direction array {E,S,W,N} tells that in a programmatic fashion) .But how do we know when to stop and change the direction.Simple ,stop after filling (dimension -1) cells on every iteration,then move by one cell in the direction you were moving.Finally change the direction with the help of direction array.

So in our example we need to fill (4-1)=3 cells in every iteration of Cycle 1

For the second cycle we need to fill just one cell on every side.as(2-1)=1

The same procedure will have to be repeated on every cycle until all the cells are filled.

There is one more question to answer how would you move from one cycle to other(gray to red) inside of a matrix.Its simple again subtract your current cycle's dimension by 2 you get the dimension of the enclosed matrix.

for e.g 
Cycle 1 dimension  = 4 
Cycle 2 dimentsion =Cycle 1 dimension  - 2 =  2 (refer second image for clarity).

C# Code

Download Code

Console Output

Ulam spiral for 10 x 10 Matrix

Project Euler Problem 112 - Bouncing Numbers

Problem statement from ProjectEuler.net

Working from left-to-right if no digit is exceeded by the digit to its left it is called an increasing number; for example, 134468.

Similarly if no digit is exceeded by the digit to its right it is called a decreasing number; for example, 66420.

We shall call a positive integer that is neither increasing nor decreasing a "bouncy" number; for example, 155349.

Clearly there cannot be any bouncy numbers below one-hundred, but just over half of the numbers below one-thousand (525) are bouncy.

In fact, the least number for which the proportion of bouncy numbers first reaches 50% is 538.Surprisingly, bouncy numbers become more and more common and by the time we reach 21780 the proportion of bouncy numbers is equal to 90%.

Find the least number for which the proportion of bouncy numbers is exactly 99%.

Solution in C#

Console output :

Console output generating bouncy numbers

Click here for other Topics

Pascal's Triangle

 Download Code

Pascal triangle is a well known mathematical structure formed out of numbers.To be specific this structure is triangular in shape.The structure was invented by a french mathematician Blaise Pascal.Various patterns on this triangle gives out to triangular numbers,polygonal numbers,squared, Fibonacci and can be used for binomial expansions.

A simple pascal triangle with 6 rows look like below

pascal triangle

The numbers will be have to be generated in rows.

On the first row just place 1 and both its left hand side and right hand side is occupied by zeroes,though not showed in the above image.Every row in the triangle should have it's starting and ending number as zero.so our first row will be exactly like below.

0    1     0

to generate the numbers on the second row

   1.  write down the first zero from row 1 as it is. 0

  =  1

 2.  next from the first row,add the first number with second number 

               =  1

 3.  and then add the second number with the third number 

   4.  Finally write down the last zero as it is which gives us the numbers for the second row as below                                                                                          

                                      

   5.  for generating the third row,we will have to execute the same steps that we followed earlier.

                                    
                                     
                                     
        which would result in following numbers for row 3.
        0   1   2   1  0.

You can keep repeating this and generate as many rows you want in your triangle.

C# Implementation

Here goes the C# Implementation.

Console Output

Console window generating the Pascal triangle for 10 rows

Click here for other Topics

Sieve of Eratosthenes

• The Sieve
• C# Code
• Console output

Prime numbers are notably the most discussed and revered topic in mathematics. And rightly so we can find its application in myriad of fields. So what is a prime number?.Any number that is divisible by 1 and itself is a prime number(2,3,5,7.....).Prime number's appliance is far reaching and its application can be found on number theory,encryption to name a few. Here is the wiki link on Prime Numbers that gives an exhaustive information.

For centuries prime numbers captivated the minds of mathematicians. A Greek mathematician named Euclid asserted that ,there are "infinitely many prime numbers".Over the centuries, many mathetimatcians invented ways to extract prime numbers upto a given number N.The process of extracting all the prime numbers up to a given number n is formally termed as "SIEVING".One of the earliest form of sieving was invented by a mathematician named Eratosthenes.A Polymath from Greece and the  first man to calculate the circumference of earth. Let us look at the simple method advised by Eratosthenes to extract all the primes up to a Number N.

Lets say to extract all primes up to 20 (N)

Write down all the numbers from 2 to 20 (1 is not a prime number so u have to exclude them everywhere)

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

First number in the List is  2;strike out every 2nd number in the list after it(all multiples of 2).

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next on the list after 2 is 3;now cross out every 3rd number on the list(all multiples of 3).

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next on list is 5;cross out every 5th number.A number could have been crossed out on a previous iteration ,which should not be a problem.As you can see below 10 was striked on the first iteration itself and would also be a candidate for 5.

2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

Next is 7
2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20.(no changes to the list)

Next is 11.
Now you can stop as 11+11 =22 which is greater than your Max number N (20).So no use in proceeding further and can stop.

Now if we read out all the numbers that are not striked,we get the primes.

2  3  5  7  11  13  17  19

C# Implementation

I am using an array to initialize and strike out the numbers.
A StopWatch class to see how much time the program takes to complete the sieving.
A Parallel class to improve the performance a bit.

The following code can sieve only up to  100 Million numbers(100000000).This is due to the fact that ,the array size is limited by system's virtual memory.I am running a AMD A8 4500 with 4GB RAM and this is the max i can go up to.We can still notch up the higher limit by replacing array with a List<T>.But i am not taking that route right now,may be ill improvise on this in future.

Without further ado,here goes the code.

namespace EratosthenesPrimeSieve
{
class Program
{
static int[] numbers = new int[100000000];
static int maxNumber;

static void Main(string[] args)
{
    Console.WriteLine("Please enter a max number ");
    maxNumber = int.Parse(Console.ReadLine());
    Stopwatch sw = new Stopwatch();

    sw.Start();
    for (int num = 2; num < maxNumber + 1; num++)
        numbers[num - 2] = num;
    sw.Stop();
    Console.WriteLine("Array fill complete. Time elapsed :" +
        (double)sw.ElapsedMilliseconds / 1000);

    sw.Restart();
    for (int idx = 0; idx < maxNumber - 3; idx++)
    {
        int num = numbers[idx];
        if (num != 0)
        {
            while (num + idx < maxNumber)
            {
                numbers[idx + num] = '\0';
                num += numbers[idx];
            }
        }
    }
    sw.Stop();
    Console.WriteLine("Removed all non primes from the array. Time elapsed :" +
                        (double)sw.ElapsedMilliseconds / 1000 + "\n" +
                        "Press enter to display all the primes upto " + maxNumber);

    IEnumerable result = numbers.Where(num => num != 0);
    Console.WriteLine("Primes found :" + result.Count());
    Console.ReadLine();
    Parallel.ForEach(result, p => Console.Write(p + ","));

    Console.ReadLine();

}
}
}