Project Euler #5 - Java

Question:

2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.

What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Answer:

I'll admit I had to spend some serious time thinking about the best way to tackle this one. Then, it just sort of came to me. The answer is practically hidden within the question! One important fact is given: 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder. What this means is that the number we are looking for MUST be a multiple of 2520! So all we have to do, is check each and every multiple of 2520 to see if the integers 11-20 divide it evenly. If they all divide in, we found the number! 

With that in mind, I believe the code speaks for itself and does not require further explanation. 

public class euler_05 
{
    final static int multiple = 2520;
    
    public static void main(String[] args) 
    {
            
        int smallest = 2520; 
        boolean done = false;     
        
        while (!done)
        {
            for (int i = 11; i <= 20; i++)
            {
                if ( smallest % i > 0 )
                {
                    smallest += multiple; 
                    break;
                }
                
                if ( i == 20 )
                    done = true;
            }
        }
           
        System.out.printf("The smallest multiple divisible by 1-20 is %d\n",  smallest);
    }
}

Project Euler #4 - Java

Question:

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91  99.

Find the largest palindrome made from the product of two 3-digit numbers.

Solution:

So, a there are two basic facts about this problem to keep in mind. One, any two 3-digit numbers will have a 6 digit product. Second, a 6-digit palindrome will be in the form ijkkji, where j and k are integers from 0-9 and i is an integer from 1-9. We know that i cannot be zero because of the fact that the product must be a 6-digit number. If i were 0, the product would only contain 5 digits (ie: leading zeroes do not count). 

So with this in mind, this problem is simple. Since we are looking for the largest palindrome with two 3-digit products, begin at 999999 and check whether this number is the product of two 3 digit numbers. If it is not, we must decrement our palindrome from the inside out. In other words, our loop is structured as i -> j -> k. We decrement k, then j, then i as we loop through our possible palindromes. 

Lets put these ideas in concrete with some code. 

public class euler_04 {


    final static int MIN3 = 100;
    final static int MAX3 = 999;
    
    public static void main (String args[])
    {
        int i, j, k, m;
        int subj; 


        for (i = 9; i > 0; i--)
        {
            for (j = 9; j >= 0; j--)
            {
                for (k = 9; k >= 0; k--)
                {
                    subj = k*1100 + j*10010 + i*100001; // create our test subject
                    
                    for (m = MAX3; m >= MIN3 ; m--) 
                    {
                        if ( (subj % m) > 0) // if the number is not divisible go to the next value of m
                            continue;
     
                        int div = subj / m; 
                        if (div >= 100 && div <= 999) // we found our subject!
                        {
                            System.out.printf("Largest palindrome with 3 digit multipliers is %d\n", subj);
                            System.exit(1);
                        }
                    }
                }
            }
        }  
    }
}

Project Euler #3 - Java

Question:

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

Solution:

We are going to assume that a list of prime numbers is NOT available to solve this problem. Still, this question is simple as long as you know one basic law of mathematics: all composite numbers can be written as a product of primes. I'm going to omit the proof (by contradiction) and ask you to just trust me on this. For example,

8 = 2*2*2 

9 = 3*3 

10 = 2*5 

147 = 3*7*7

So now with that little nugget tucked away we can tackle this problem. The solution is to loop through 2 and every odd integer and check whether the integer divides evenly into our subject number. If it does, divide the subject by that integer repeatedly until a remainder is found. Once a remainder is found, continue on to the next integer. Finally, we stop looking for a new integer when our subject equals 1. 

You might be thinking, "wait, does that really work?" I assure you, it does. Let's look at our previous examples.

Subject: 8

Integer: 2

Iteration 1: Does 2 divide 8? Yes, so divide 8 by 2.

Iteration 2: Does 2 divide 4? Yes, so divide 4 by 2. 

Iteration 3: Does 2 divide 2? Yes, so divide by 2. 

Iteration 4: Does 2 divide 1? Nope!... subject equals 1. 

Highest prime that divides 8 is 2.  

   

Subject: 147

Integer: 2

Iteration 1: Does 2 divide 147? No, increase Integer. 

Iteration 2: Does 3 divide 147? Yes, so divide by 3. 

Iteration 3: Does 3 divide 49? No, increase Integer.

Iteration 5: Does 5 divide 49? No, increase Integer. 

Iteration 7: Does 7 divide 49? Yes, so divide by 7. 

Iteration 8: Does 7 divide 7? Yes, so divide by 7.

Iteration 9: Does 7 divide 1? No. Subject equals 1. 

Highest prime that divides 147 is 7. 

This algorithm works for ALL numbers. So without further adieu, my solution. With all this in mind, I do not believe my code needs any further explanation.

import java.math.BigInteger;


public class euler_03
{
    public static void main(String[] args)
    {
        BigInteger dividend = new BigInteger("600851475143");
        BigInteger divisor = new BigInteger("3"); // Skip 2 since this is an odd number
        int high = 3;
       
        while(true)
        {
            // Continually divide until no remainder
            while (dividend.remainder(divisor).equals(BigInteger.ZERO))
            {
                dividend = dividend.divide(divisor);
                high = divisor.intValue();
            }
           
            divisor = divisor.add(BigInteger.valueOf(2));
           
            if (dividend.equals(BigInteger.ONE))
                break;
        }
       
        System.out.printf("The highest prime factor is %d\n", high);
    }
}

Project Euler #2 - Java

I believe this is probably the most straightforward problem I have encountered on PE thus far. 

Question:

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution:

The one thing NOT  to do is to try to solve this recursively. Your stack will get gigantic and your program will probably crash. Luckily, this is an easy one to solve using a simple for loop.

public class euler_02 {
   
    public static void main (String args[])
    {
        int num1 = 1;
int num2 = 2;
int num3 = 0;
int sum = 2;


while (true)
{
num3 = num1+num2;
if (num3 > 4000000)
break;


if ((num3 & 0x1) == 0x0) // checks if number is even
{
sum += num3;
}


num1 = num2;
num2 = num3;
}
System.out.printf ("Sum of even fibonacci numbers less than 4,000,000 is %d\n", sum);
    }
}

Like I said, pretty straightforward. The variables num1 and num2 hold the prior two values used to computenum3, the next fibonacci number. Then, break out of the loop when num3 exceeds 4,000,000. The only trick I use here is the way I find out whether num3 is even. Rather than going with the obvious  

num3 % 2

and checking if there is a remainder, deciding whether a number is even or odd can be done much quicker by simply checking whether the LSB (least significant bit) is 1. Since the LSB = 2^0 = 1, this number will ONLY be odd when the LSB == 1. Thus, 

(num3 & 0x1) == 0x0

evaluates to 1 when the num3 is even and 0 when num3 is odd. 

Compile, and voila! The answer is before your eyes.

Project Euler #1 - Java

Question: 

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

Solution:

The simple way to complete this is to run two loops that accumulate a shared sum: one that sums the multiples of 3 and another than sums the multiples of 5. But that is too easy... lets add some complexity by completing both sums inside one loop. Again... there is any easy way, and there is a hard way. We could go through a loop 333 times and do each multiple of 3 individually, or we could do it all in 199 iterations for each multiple of 5 and simultaneously sum all multiples of 3. But, 3 * 199 = 597... so that means that we are missing all multiples of 3 over 597. We know that we want to count the numbers 999, 996, 993, 990, ... , 603, 600. Well, 600 / 3 = 200 which is out of the scope of our loop, and 999 / 3 = 333 which is also out of the scope. So lets try dividing by 6. 600 / 6 = 100... good. 999 / 6 = 166 r 3. CRAP! We cant get to 999! So what to do? Add two consecutive multiples in each iteration. That is, we want 

2i * 3 + (2i + 1) * 3

=(2i + 2i + 1) * 3 (by simple factorization)

=(4i + 1) * 3

Finally, Here is my solution written in Java. 

public class euler_01 {

    

    public static void main( String args[] )

    {

            int sum = 0;

        

            for (int i = 199; i > 0; i--)

            {

                if ( (i < 167) && (i > 99) )

                {

                    sum += (( (i << 2) + 1) * 3);

                }

                

                if ( i <= 66 )

                    sum -= 15*i;

                

                sum += (i << 3);

            }

            

            System.out.printf("Sum is %d\n", sum);   

    }

}

So now for an explanation of the lines inside the loop. 

if ( i <= 166 && i >= 100)

sum += ( (i<<2) + 1) * 3;

This line is what calculates our multiples between 600 and 999. For the newbies out there, 

(i<<2) == 4*i

One thing that slipped my mind was that many numbers between 0 and 1000 are multiples of both 3 AND 5... namely, all multiples of 15. Thus, these numbers are counted twice and we need to subtract them. There are exactly 66 multiples of 15 less than 1000, so 

if ( i <= 66 )

sum -= 15*i;

takes care of that problem. 

Finally, we need our multiples of 3 and multiples of 5. Or, 3*i + 5*i... well, thats 8*i ! 8 = 2^3... so, 

                sum += (i<<3);

And thats it! Compile, and see the solution before your eyes!

DFA Problem #3

Problem:

Construct dfa that accept strings on {0, 1} if and only if the value of the string,
interpreted as a binary representation of an integer, is zero modulo five. For example,
0101 and 1111, representing the integers 5 and 15, respectively are to be expected.


Solution:
There are two keys to solving this problem: 1) Labelling the states and 2) Knowing how binary arithmetic works. It is absolutely essential that you know what happens to a binary number as its digits are shifted left. If you do not, it is simple... each shift left multiplies the current value by 2. Then, if the new digit is a 1, you add 1. 


Example:
1010₂ = 10₁₀ 


Treating '1010' as a string, the next input can either be a 1 or a 0. Remembering that as the digits are shifted, the value doubled:

10100₂ = 20₁₀ 
and therefore 
10101₂ = 21₁₀ 


So, lets call the original string 'n'. Then shifting n left by one place, the potential values are either
2n 
OR 
2n + 1 


Notice that the same treatment may be applied to the modulus (remainder). 


Now, lets get into the problem. There are 5 potential remainders when dividing by 5 and we can use these remainders as the labels for our nodes: {0,1,2,3,4}. The equation states that the accept state is 0. So, 

The order and layout will be apparent once we start connecting the dots. 

Lets assume starting that we start with an empty string... obviously, the first input will either be a 1 or a 0 and therefore the modulus will either be a 1 or a 0. So, it is safe to have node 'q0' be the initial state as well as the final state. After this has been figured out, it is simple to connect the dots! All that needs to be done is to apply the binary shift arithmetic to each modulus indicated at the node. Two lines will be drawn from each node, a 1 or a 0 (obviously) which correspond to the equations 2n + 1 and 2n respectively, where n is the modulus at the given state. 

First, lets do all of the 0s. 

d(q0,0) = q0

d(q1,0) = q2 

d(q2,0) = q4

d(q3,0) = q1

d(q4,0) = q3

In case you didn't follow, take the number next to the 'q' on the left side of the equation, multiply it by 2, and then divide the result by 5. Take the remainder, and that is the node it should be connected to. 

Now lets do the same for an input of 1 at each node. Same process of before, but instead of just multiplying by 2, we also add 1 before dividing by 5. 

d(q0,1) = q1

d(q1,1) = q3

d(q2,1) = q0

d(q3,1) = q2

d(q4,1) = q4

Once those lines are inserted, the solution is complete! If you did not follow this, review binary multiplication a couple of times and it should become clear. 

DFA Problem # 2

Problem:
A run in string is a substring of length at least two, as long as possible and consisting
entirely of the same symbol. For instance, the string abbbaab contains a run of of b’s of
length three and run of a’s of length two. Find dfa for the following language on {a, b}.
L = {w: w contains no runs of length less than four}


Solution:
This one is a bit more fun. It sounds simple, but once you start playing with it a bit you notice that there are a couple of pitfalls. If you just start placing nodes on the canvas and trying to plug in arrows, you will have a bit of a problem. The easiest way to do this one is to start from the beginning: either an 'a' or a 'b'.

The problem is to accept strings of arbitrary length where each character is repeated a MINIMUM of 4 times in succession. All other strings fail. So lets start with just setting accept states for 'aaaa...' and 'bbbb...'.

Next, lets introduce the trap. Strings like, 'ab...', 'aab...', 'aaab...' will NEVER be accepted assuming that the leading character in these situations is in fact the a and that no a's precede these strings. In other words, once these strings are encountered fall into an unrecoverable trap. The two traps in the diagram could logically be combined into one, but I left them separate for easy of reading the diagram (crossing lines gets hard to read).

Almost done! All that is left to do is to solve 

d(q5, a) = ?

d(q8, b) = ? 

Easy! 

If the state is q5 and an 'a' is encountered, start looking for 4 consecutive a's. 

If the state is q8 and a 'b' is encountered, start looking for 4 consecutive b's. 

DONE!

DFA Problem # 1

Problem:
Find dfa for the following language on Σ = {a, b}
L = {ab⁴wb²: w ∈ {a, b}* }


Solution:
This is pretty straight forward. The first part of this language, ab⁴ ,I do not believe requires any explanation. Look for the sequence, "abbbb" and the order is not correct, trap the remaining input in a non-accept state:

Now its time to tackle "wb²". This basically reads, "any combination of a's and b's or no a's and b's at all followed by 'bb'." At this stage, valid input should have a state of 'q5'. It is known that input should end with 2 b's so lets add those now and then connect the dots. 

However, since there are still aspects missing. Namely,

let 'l' = lambda

d(a, q5) = 

d(l, q5)  = 

d(a, q6) = 

Lets solve from top to bottom. The language says that any string finishing in 'bb' should be accepted. At q5, this indicates that input of 'a' or 'l' should loop in place until a 'b' is encountered. Once this 'b' is encountered, the state will change to q6. But to get to an accepting state, we need consecutive b's. So if an 'a' is encountered while in state q6, it is safe to move back to q5 and begin the search for 'bb' over again. 

d(a, q5) = q5

d(l, q5)  = q5

d(a, q6) = q5

But this isn't finished! This just finds two consecutive b's. This is a DFA so all nodes must have an equation for all input. Namely, 

d(a, q7) =

d(b, q7) = 

must have a solution. Obviously, if another b is encountered, the state should not change. If this isn't obvious, notice that 'bb' and 'bbb' and 'bbbbbbbb' all end in 'bb'. But what if an 'a' is encountered? Well, then its back to looking for two consecutive b's. So,

d(a, q7) = q5

d(b, q7) = q7

Finally, the solution:

Project Euler #16 - C

Question:

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 2¹⁰⁰⁰?

Solution:
I'm sure many beginning programmers get stumped on this one. "I used the pow function but I just cant get the right answer." Well, the problem is a that 2^1000 wont fit in a 2^32 word. So, I will use a method I have used for a couple of previous PE problems... it is something that may be a bit advanced for some of you: multiplication and addition.

The way to go about this is to imagine these numbers as one huge number, but rather as an array of digits between 0 and 9. Then, proceed like you were taught in elementary school... multiply -> carry -> multiply -> add -> carry... and repeat. Example:

    19
x   3


First, 3 x 9 = 27. We bring the 7 down, carry the 2. Then, 3 x 1 = 3 + 2 (carry) = 5. So, 3 x 19 = 57.

This is the exact process used to solve this problem. First, create an empty array and set the first element to 1 (digits[0] = 1). We will want to multiply successive products by 2.
2 x 2 = 4
2 x 4 = 8
2 x 8 = 16
etc. But rather than saving as an individual product, you save the digits in the array.

This requires two loops: an outer loop that loops from 1 - 1000, and an inner loop which multiplies each individual member of the array by 2 using the process described above.

Upon completion of the outer loop, the array should contain the number 2^1000.
Simply sum the digits, and you are done.
Here is the C code. I use a placeholder of the highest use index to reduce the number of loop iterations but it is optional.

#include <stdio.h>
#define SIZE  500
#define POWER  1000


int main (void)
{
int digits[SIZE] = {0};
int high_order = 0;
int i = 1;
int sum = 0;


/* 
Could start from the maximum 64 bit integer to save 
some calculations but I do not do so here.
*/


digits[0] = 1;


for (i = 1; i <= POWER; i++)
{
int j;
int carry = 0;
int product = 1;


for (j = 0;  j <= high_order; j++)
{
product = (digits[j] << 1) + carry; 
digits[j] = product % 10;
carry = product / 10; 


if ( ( carry != 0 ) && ( j == high_order ) )
high_order++;
}
}


for (i = 0; i <= high_order; i++)
sum += digits[i];


printf("Sum is %d\n", sum);
return 1;
}

Project Euler #15 - Math

Question:

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

Solution:

I spent a LONG time trying to figure out how this 2x2 grid has 6 unique routes fact was relevant to the solution of this problem. I sat down, drew the diagram out on a piece of paper, and racked my brain for a good hour trying to find some link between 2x2 = 6 and 20x20 = ? 


Then, I walked away, had lunch, and then sat back down to tackle this problem again. Then a fact just jumped out at me: THIS IS EASY! I spent an hour looking in the wrong direction when this is really just a simple math problem. In fact, I didn't even code a solution. 


There is one important fact to realize: It takes 20 moves to the right, and 20 moves down to get to the end point no matter which route you decide to take. So really the only thing that matters is when you decide to make a right turn and when you decide to make a down turn. All in all, there are 40 moves required to get to the end point no matter which route you chose (again... 20 right, 20 down). So this is just a combinations problem! 


Picture it like this:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
(40 blank spaces)


How many ways are there to place 20 "D"s in the 40 blank spaces. 


Once the 20 "D"s are placed, the rest of the blank spaces get filled with "R"s and you achieve a sequence of "R"s and "D"s that will lead to the end point every time (doubt me? try it!). 


Mathematically, this is represented as "n  choose k", where n is the number of spaces and 
k the number of "D"s. The equation is: 


n!/( n! * (n-k)! )


Substituting in the values 40 for n, and 20 for k:


40! / (20! * 20!)


Now, factor and get the answer! ... or just use your calculator!