QuantNet Coding Project

[Andy Nguyen]

As a follow up from the Python learning thread and from Sanket's suggestion of the Project Eucler we are going to use this thread to solve fun, interesting math problems in Python (preferred) or any programming language of you choosing (C++, C#, Matlab, R, VBA, etc)

So here is how we plan to do this.
1) We will post the problems from Project Eucler, starting from the easiest ones (ID 1, 2, etc)

We will work through each one, everyone is welcome to submit their code snippet in different languages or optimization/generalization of the previously submitted code.

2) Once a problem is thoroughly solved, we will move to the next set of problem or so.

3) You are encouraged to sign up on the Eucler page and solve problems at your own choice.

Here is the first problem

Problem 1

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.

Problem 2

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, ...​

Find the sum of all the even-valued terms in the sequence which do not exceed four million.

Problem 3

The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Problem 4

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.

Problem 5

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 number that is evenly divisible by all of the numbers from 1 to 20?

 

[yzia]

I already broke the rule and did it in Java. Two methods, I'm fairly certain second method would be correct

public class Program {
       public static void main(String[] args) {
               int sum = 0;
               for (int i = 3; i < 1000; i++) {
                    if (i % 3 == 0 || i % 5 == 0) {
                          sum += i;
                    }
               }
               System.out.println(sum);
       }
}

Output: 233168
or...

public class Program {
       public static void main(String[] args) {
               int sum = 0;
               int counter = 0;

               for (int i = 0; i < 100; i++) {
                    if counter == 0
                       sum += 23 + 10*5*i
                    if counter == 1
                       sum += 15 + 10*4*i
                    if counter == 2
                       sum += 17 + 10*5*i
                    counter++;
                    if counter == 3
                        counter = 0;
               }
               System.out.println(sum);
       }
}

Output 233168

In the second one here, I'm going by the basis that each of the totals for every third set of 10 (i.e. the 10's, the 20's, the 30's, etc) are equal in sum if you normalize it. Then, to get the actual numbers, you add 10*5*i (or 10*4*i because one of the numbers is equal).

 

[Andy Nguyen]

Post the output of each of your method.

---------- Post added at 01:33 AM ---------- Previous post was at 01:28 AM ----------

And here is the one line of code and output in Python

>>> sum([x for x in range(1,1000) if x % 3 == 0 or x % 5 == 0])
233168

 

[yzia]

Post the output of each of your method.

---------- Post added at 01:33 AM ---------- Previous post was at 01:28 AM ----------

And here is the one line of code and output in Python

>>> sum([x for x in range(1,1000) if x % 3 == 0 or x % 5 == 0])
233168

Updated. And I lose, I like the python response better.

 

[atreides]

Here is the first problem

Problem 1

language : Python

t_sum = 0

for x in range(1, 1000):
    if x % 3 == 0 or x % 5 == 0:
        t_sum = t_sum + x
   
print(t_sum)

>>> ================================ RESTART ================================
>>>
233168
>>>
time to run
(0.021638154983520508, 'seconds')


---------- Post added at 12:53 AM ---------- Previous post was at 12:47 AM ----------

As a follow up from the Python learning thread and from Sanket's suggestion of the Project Eucler we are going to use this thread to solve fun, interesting math problems in Python (preferred) or any programming language of you choosing (C++, C#, Matlab, R, VBA, etc)

Once a problem has been solved and posted there is little or no push to solve it again if the answer is already there. Can you modify visibility of posted answers/code and maybe publish them after a few minutes/hours

 

[Andy Nguyen]

I worked it out with pen and paper first to have a sense of the problem. It's a mathematical problem after all.

We have a formula to find sum from 1 to n.
1+2+...+n = n(n+1)/2

So the sum of multiples of 3 and 5 will be
3+6+...+999 = 3(1+2+...+333)= 3*333*334/2 (A)
+
5+10+995=5(1+2+199)=5*199*200/2 (B)

since these sum will count 15,30,45 twice which is multiple of 15, i just subtract it from the sum
15+30+...+990=15(1+2+...+66)=15*66*67/2 (C)

A+B-C is the total I'm looking for. Obviously, there are things the computer do better than us.

---------- Post added at 02:01 AM ---------- Previous post was at 01:55 AM ----------

Once a problem has been solved and posted there is little or no push to solve it again if the answer is already there. Can you modify visibility of posted answers/code and maybe publish them after a few minutes/hours

Yes. I think the setup of Project Eucler is good. We have to keep submitting answer until we got the right number. Only then you can see the code.
I'm trying to think of something like this. Maybe we should not post result, only code snippet. And the correct answer hidden in the first post, only revealed when we do something?

Ideas?

 

[yzia]

Once a problem has been solved and posted there is little or no push to solve it again if the answer is already there. Can you modify visibility of posted answers/code and maybe publish them after a few minutes/hours

I think the goal then should be, how can you do it differently?


What would be really cool is down the road, we get problems where optimization is key and we look at which one has the faster code.

 

[atreides]

Problem 3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?

Quick and dirty..

language : python

def is_a_prime(i):
    for x in range(2, int(i**0.5)+1):
        if i % x == 0:
            return False
    return True

num = 600851475143
for x in range(1, num):
    if num % x == 0 and is_a_prime(x):
        print (x)

---------- Post added at 01:37 AM ---------- Previous post was at 01:20 AM ----------

I think the goal then should be, how can you do it differently?


What would be really cool is down the road, we get problems where optimization is key and we look at which one has the faster code.

Maybe ask folks to submit code and solutions worked out by hand / Induction / whatever math technique.

There is so much more to learn like elegance of solution, learn a few properties of numbers in the process, proofs, combinatorics, etc than just getting the right answer. I guess this will push it away from the python focus

 

[Andy Nguyen]

I think it would be helpful to preface your code bit with the mathematical thought process and explain how you work out the problem first on paper. The implementation bit is much easier understood once we got the math part down pat.

For example, I first worked out Problem 1 on paper like post #6

 

[DanM]

This is my attempt at the Fibonacci problem in C++. Keep in mind, I am a C++ noob.

int Fibonacci(int n);
 
int main( )
{
    int _sum = 0;
    int term;
    int bound = 4000000;
    int j = 1;
 
    do
    {
    term = Fibonacci(j); 
    if (term % 2 == 0 && term <= bound)
       _sum += term;
 
    j++;
    }while (term <= bound);
 
    cout << _sum << endl;
 
    return 0;
}
 
int Fibonacci(int n)
{
    int sum;
    int prevOne = 0;
    int prevTwo = 1;
    int tmp;
    int i;
 
    for (i = 0; i < n; i++)
    {
         sum = prevOne + prevTwo; 
         tmp = prevOne;
         prevOne = prevTwo;
         prevTwo = prevTwo + tmp;
    }
 
 
    return sum;
}

The output is 4613732.

---------- Post added at 11:36 PM ---------- Previous post was at 11:28 PM ----------

My interpretation of the Fibonacci problem was that the terms should not exceed 4,000,000, not the sum. Is this correct?

 

[dearappu]

Suggestion:

If am right, you are calculating the fibonacci series all over again for calculating each term -> not elegant
also observe the series and find out the pattern of the even numbers rather than checking if each term is even

 

[koupparis]

1) Fib numbers have a closed form.
2) Every 3rd fib number starting from fib(0) = 0 is even, (i.e. 0, 1, 1, 2, 3, 5, 8 etc)

So:

int fib(int n);

void main(){
	int sum=0;
	int n=0;

	while(fib(n) < 4000000){
		sum+=fib(n);
		n+=3;
	}
	cout<<sum<<endl;

}

int fib(int n){
	double f = .5*(1+sqrt(5.));
	return ( pow(5,-.5)*(pow(f,n)-pow(1-f,n) ) );
}

 

[DanM]

Nice!

We get the same output, but yours is exponentially more efficient.

 

[TomJeffries]

Solutions 1 and 2 in R

Problem 1:
x <- seq(1:1000)
y <- x[ x%%3 == 0 | x%%5 == 0 ] # numbers divisible by 5 or 3
sum( y[ y < 1000 ] ) # sum of divisors < 1000

Solution: 233168

Problem2:
fib = numeric()
fib[1] = 1
fib[2] = 1
i = 2
while (fib < 4000000) { # generate fibs < 4000000
i = i + 1
fib = fib[i-1] + fib[i-2]
}
sum( fib[ fib%%2 == 0] ) # sum even fibs

Solution: 4613732

 

[bwc]

in C++

In C++:

#include <iostream>

int main( int argc, char** argv )
{
int sum = 0;
for ( int i = 3; i < 1000; ++ i ) sum = ( ! (i % 3) || ! (i % 5) ) ? sum + i : sum;
std::cout << "total : " << sum << std::endl;
return 0;
}

Note the core calculation can also be in one line IF there is no need to print out the answer, which then made it pointless. Obviously, it's a bit inefficient.. but just trying to reduce source code. =)

 

[John Jurcevic]

And here is the one line of code and output in Python

>>> sum([x for x in range(1,1000) if x % 3 == 0 or x % 5 == 0])
233168

Same code using C#

Console.WriteLine(
    Enumerable.Range(1, 999).Where(x => x%3 == 0 || x%5 == 0).Sum()
);

 

[Andy Nguyen]

Problem 5 is simply finding lcm(1,2,...,20)
To avoid calculating gcd to find lcm, we can use prime factorization.
This page has an algorithm to find lcm of n numbers
http://www.cut-the-knot.org/Curriculum/Arithmetic/LCM.shtml

 

[Sanket Patel]

Speed Comparison

It would be interesting to see how the various methods and languages everyone is using compare in speed. To that end, for those interested, I suggest measuring the time it take for your code to run.

For those using Python, you can measure execution time as follows:

import time

start_time = time.time()
...
...
#your code here
foo = bar()
...
...
print time.time() - start_time, 'seconds'

 

[koupparis]

Answer for 5 is 232792560.

 

[goodstudent]

Answer for 5 is 232792560.

I thought so too, but it is actually 21162960.

It's a weird... Here is what I did

It is basically a question of lcm(11,12,...20). So find prime factorization:
11: 11
12: 2*2*3
13: 13
14: 2*7
15: 3*5
16: 2*2*2*2
17: 17
18: 2*3*3
19: 19
20: 2*2*5

So LCM SHOULD be 2^4 * 3^2 * 5 * 7 * 11 * 13 * 17 * 19 which is 232792560. HOWEVER.

232792560 a multiple of 11^2. So the LCM is 232792560/11, which is 21162960