Problem 5 - Solution

After combing over my code, trying to figure out where the small logic error in it was, I got a small idea to change the location of one of the if statements, putting it inside one of the while loop above it. I then tested this to find the Least Common Denominator for all numbers from 1 to 10, and it worked!

So I made the same changes in the code to make it find the Least Common Denominator for all integers from 1 to 20, and set it running. Of course, it still took a long time, but this time it worked, and I got the right answer!

Here is my final code:
PasteBin Link


public class Problem_5
{
public static void main(String[] args)
{
// num is what will look for answer
// answer will be set to num when found
// n is for recursively dividing
int count = 20, ans = 0, n = 2;

// while the answer has not been found
// continue searching
while (ans == 0)
{
//System.out.println("Entered loop");
n = 2;
// set dividor back to 2 and start again
while (n <= 20) 
 { 
 if ((count%n) == 0) 
 { System.out.println("" + count + " " + n); n++; 
 } 
 else n = 21; 
 // if num can be modded by 20 
 // and if n gets to 20 
 // then this must be the answer 
 // otherwise the while loop 
 // would have stopped 
 if ((count % 20 == 0) && (n == 20)) 
 { 
 ans = count; 
 System.out.println("The answer is: " + ans); 
 } 
 } 
 count++; 
 } } }


Now comes optimization. Since the answer has to be divisible by 2 (even), I could modify the counter to add 2 rather than 1. Also, I could test for divisibility by the number of 10 through 20, or maybe 5 through 20, which will take some of the steps out of it, but I do not think this would be mathematically rigorous, though it may still work.

Problem 5 - Second Attempt (revisit)

So I decided to sift through my logic for Problem 5 and made some minor corrections, changed some of the variables, and added a few println's so that I could make sure the program was going into the necessary loops and so that I can see if the output is coming along nicely, which it seems to be doing well. 


I have the program running in the background right now, and it certainly does not conform to the 1-minute rule, meaning it should be able to run in one minute, but if I get the correct answer, I will be happy. I will paste the code below, before I got over how I think I can get it to run faster.
PasteBin Link 


public class Problem_5
{

public static void main(String[] args)
{
// num is what will look for answer
// answer will be set to num when found
// n is for recursively dividing
int count = 20, ans = 0, n = 2;

// while the answer has not been found
// continue searching
while (ans == 0)
{
//System.out.println("Entered loop");
n = 2;
// set dividor back to 2 and start again
while (n <= 20) 
{ 
if ((count%n) == 0) 
{ 
System.out.println("" + count + " " + n); 
n++; 
} 
else 
n = 21; } 
// if num can be modded by 20 
// and if n gets to 20 
// then this must be the answer 
// otherwise the while loop 
// would have stopped 
if ((count % 20 == 0) && (n == 20)) 
{ 
ans = count; 
System.out.println("The answer is: " + ans); 
} 
count++; 
} } }


All of the possible answers are even, therefore I could just add two for the counter, and that may cut the run time by roughly half, but I know that will not be enough because I started the program 14 minutes ago, and it is still running

Problem 5 - Second Attempt

Put down a rough outline for a better solution to problem 5. As you can see, this program is more compact, however, the logic is not as easy to follow, and I trip up myself plenty why typing it out. Hopefully it works when I let it run overnight though!

PasteBin Link

public class Problem_5
{


public static void main(String[] args)
{
// num is what will look for answer
// answer will be set to num when found
// n is for recursively dividing
int num = 20, answer = 0, n = 1;

// while the answer has not been found
// continue searching
while (answer == 0)
{
n = 1;
// set dividor back to 1 and start again
while (n <= 20) 
{
if ((num % n) == 0) 
 n++;
}
if ((num % 20 == 0) && (n == 20)) 
{
answer = num; 
System.out.print("The answer is: " + answer); } num++; 
}
}
}


If it doesn't work, I will probably have to make some logic adjustments. Have not tried this in Mathematica yet, the if statements and while loops are very different syntactically from Java.

Problem 5 - First Attempt

Did not feel like doing thinking about problems 2 through 4, so I skipped straight to problem 5, and am trying a brute force approach with Java, and I think this might come back to bite me in the ass. 


As you can see from the problem, you have to find a number that is evenly divisible by every number from 1 to 20. This number is presumably quite large, because the question says that 2520 is the first number evenly divisible by the number 1 through 10.

Problem 1 - Solved

Ah, my first post. Well, this blog will chronicle my experience with Project Euler, a website which posts interesting math problems which you then solve, using logic, programming, or whatever means you can find that don't include just looking up the answer. I came across the site a while ago, but just now starting trying to solve some of the problems by using my new found skills in Java programming. I also know some Mathematica and will use that as well.