• C++ Programming for Financial Engineering
    Highly recommended by thousands of MFE students. Covers essential C++ topics with applications to financial engineering. Learn more Join!
    Python for Finance with Intro to Data Science
    Gain practical understanding of Python to read, understand, and write professional Python code for your first day on the job. Learn more Join!
    An Intuition-Based Options Primer for FE
    Ideal for entry level positions interviews and graduate studies, specializing in options trading arbitrage and options valuation models. Learn more Join!

QuantNet Coding Project

Joined
5/2/06
Messages
11,750
Points
273
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
symbol_times.gif
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?
 
I already broke the rule and did it in Java. Two methods, I'm fairly certain second method would be correct

C++:
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...

C++:
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).
 
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
C++:
>>> 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.
 
Here is the first problem

Problem 1

language : Python
C++:
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
 
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?
 
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.
 

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

C++:
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
 
This is my attempt at the Fibonacci problem in C++. Keep in mind, I am a C++ noob.

C++:
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?
 
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
 
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:

C++:
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) ) );
}
 
Nice!

We get the same output, but yours is exponentially more efficient.
 
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
 
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. =)
 
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:

C++:
import time

start_time = time.time()
...
...
#your code here
foo = bar()
...
...
print time.time() - start_time, 'seconds'
 
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
 
Back
Top