Project Euler Problem 10 Solution using MATLAB and Octave

 Coding  No Responses »
Apr 132011
 

The following is Problem 10 from Project Euler. As of this posting, it has been solved 62,312 times.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
Find the sum of all the primes below two million.

MATLAB and Octave have a function called “primes” which takes any number as an argument and returns an array of all the prime numbers below that number.

For example, calling primes(10) would return an array of [2 3 5 7].

So solving this problem in MATLAB feels like cheating. The below code executed in just a few milliseconds.

% ProjectEuler.net problem #010
% The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
 
% Find the sum of all the primes below two million.
 
tic();
 
format long
final_answer = sum(primes(2e6))
 
exec_time = toc()

I suppose I could write an algorithm to find the primes and brute-force it with an IF or WHILE loop, but I think I’d rather move on to the next problem. So there you have it. Happy coding!

 Posted by Matt at 4:27 am  Tagged with: , ,

Project Euler Problem 9 Solution using MATLAB and Octave

 Coding  No Responses »
Mar 292011
 

The following is problem 9 of Project Euler. As of this posting, it has been solved 67,769 times.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a^2 + b^2 = c^2

For example, 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product a*b*c.

The following is a MATLAB and Octave solution. There may be no way around using nested FOR loops in this one. By using routine algebra to come up with the statement in the IF conditional, the program doesn’t have to loop through as many times. The following code executes in about 1.7 seconds.

% ProjectEuler.net problem #009
% A Pythagorean triplet where a<b<c, for which, a^2 + b^2 = c^2
% There exists exactly one for which a+b+c=1000. Find the product abc.
% Below code executes in 1.70 seconds.
 
clear
tic();
a=1; b=1;n=1000;
 
for a = 1:n
	for b = 1:1000-a
		if 1e6 - (2000)*(a+b) + 2*a*b == 0
			triplet(1:3) = [a b 1000-a-b];
		end
	end
end
 
triplet
final_answer = prod(triplet)
 
exec_time = toc()

There you have it. Good luck and happy coding!

 Posted by Matt at 9:11 pm  Tagged with: , ,

Simple PHP Script to pull data from a MySQL database and display in HTML

 Coding  No Responses »
Mar 202011
 

In the last PHP tutorial, I showed how you could create an HTML form that would use PHP to write data into a MySQL database. In this tutorial, I’ll show you how you can use PHP to pull that data from the database and display it in your HTML. If you need the previous tutorial, you can find it here:

Simple PHP Script to Input Data to MySQL Database from HTML Form

If you recall, in our last example we have a database called “bozo” and a table called “famous_clowns.” In this table we have five fields. You can think of these as columns since we’ll be displaying them in an HTML table anyway. The data fields were: seed, name, country, rating and comments.

The below script is going to be called displayclowns.php. There’s nothing wrong with mixing your HTML with PHP calls, but the document needs to end with the .php extension so your server will know that it contains calls to PHP. Continue reading »

 Posted by Matt at 7:27 am  Tagged with: ,

Project Euler Problem 8 Solution using MATLAB and Octave

 Coding  No Responses »
Mar 162011
 

The following is problem 8 of Project Euler. To date, it has been solved 66,993 times.

Find the greatest product of five consecutive digits in the 1000-digit number.

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

The following is the Octave/MATLAB code that will solve it. The below executed in 1.502 seconds.

% ProjectEuler.net problem #008
% Find the greatest product of five consecutive digits in the 1000-digit number.
 
clear
t = clock;
 
% First, we'll treat the huge number as a string.
% Note, the code will need the whole number pasted here.
 
n = "7316717....3450";
 
for a = 1:996;
 
% Find the five numbers to multiply, convert from string to number.
for j=a:a+4
	five_nums(j-a+1) = str2num(n(j));
end
 
colm(a, 1:2) = [a, prod(five_nums)];
 
end
 
fin_answer = max(colm(1:996,2))
 
exec_time = etime(clock, t)
 
% It doesn't ask which numbers give this product, but by
% manually looking through colm, we see that they were
% the 365th - 369th digits, or 9,9,8,7,9.
 
the_digits = n(365:369)

There you have it. Happy coding!

 Posted by Matt at 2:23 am  Tagged with: , ,

Project Euler Problem 7 Solution using MATLAB and Octave

 Coding  No Responses »
Mar 132011
 

The following is problem 7 of Project Euler. As of this posting, it has been solved 74,865 times.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

As MATLAB and Octave already have an optimized function for returning prime numbers, this simple solution almost feels like cheating. Maybe I’ll go back later and try a brute force approach with a couple of loops. Or maybe I’ll just live with the below and move on to the next one.

% ProjectEuler.net problem #007
% By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we 
% can see that the 6th prime is 13.
% What is the 10,001st prime number?
% answer should be 104,743, exec time 0.01036.
 
clear
tic();
 
which_prime = 10001; % This is the prime we're looking for.
 
% We can start our counter pretty high since we know
% that there are not 10k prime numbers below 100,000.
a = 100000;
 
while length(primes(a)) < which_prime
	a = a + 10000;
end
 
get_primes = primes(a);
 
final_answer = get_primes(which_prime)'
 
exec_time = toc()

You could easily do this with one line of code and it would still execute in about a tenth of a second. You’d just have to guess the upper limit. Maybe guess that there are at least 10,000 prime numbers below, say 2 million, and you could execute the following line:

a = primes(2e6)(10001)

There you have it. Happy coding!

 Posted by Matt at 5:59 am  Tagged with: , ,

Project Euler Problem 6 Solution using MATLAB and Octave

 Coding  No Responses »
Mar 122011
 

The following is problem 6 of Project Euler. As of this posting, it has been solved 89,315 times.

The sum of the squares of the first ten natural numbers is,
1^2 + 2^2 + … + 10^2 = 385

The square of the sum of the first ten natural numbers is,
(1 + 2 + … + 10)^2 = 55^2 = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 – 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

This one is fairly simple. Create an array from 1 to 100, sum it, then square it. Then create another array and take the sum of each individual element squared. It could probably be done in one line, but the below makes it a little clearer. And it still executes in less than a thousandth of a second.

% ProjectEuler.net problem #006
% Find the difference between the sum of the squares 
% of the first one hundred natural numbers and the square of the sum.
% Below script executes in 0.000366 seconds.
 
clear
t = clock;
 
a = (sum(1:100))^2;
b = [1:100];
c = sum(b.^2);
 
diff = a-c
exec_time = etime(clock, t)

There you have it. Happy coding!

 Posted by Matt at 3:40 am  Tagged with: , ,

How to speed up MATLAB and Octave by Vectorization

 Coding  No Responses »
Mar 112011
 

One way to speed up the executing times of your coding projects is to use MATLAB and Octave’s native vectorization capabilities. In short, this is one of the significant advantages of using a vector- or matrix-based programming language over the more popular object oriented languages. What do I mean by vectorization? I’ll show you with a quick example.

Maybe you need to sum all the numbers from 1 to 1,000,000. A simple for loop will do the trick.

clear
tic();
 
x = 0;
 
for n = 1:1e6
	x = x + n;
end
x
exec_time = toc()

On my computer the above took 1.249 seconds to execute. Not a tremendous amount of time, but how can we make it faster? By not using a loop, and operating directly on vectors. Try the below…

clear
tic();
 
s = sum(1:1e6);
 
exec_time = toc()

This code executed in 0.0192 seconds, which is more than 50 times faster. The difference between a second and 0.019 seconds may not seem like much, but what if you had to run something like the above within another loop for a hundred or more iterations? Now the difference becomes code that could execute in about 3 seconds compared to 3 minutes. The more complex your coding gets, the more important it is to try to use MATLAB and Octave’s inherent strengths whenever possible.

Now, it may be impossible to eliminate loops from your coding all together, but ask yourself whenever you’re writing a for or while loop, are you doing it to create another vector? If you’re using it with an embedded conditional (IF/ELSE), chances are you may be stuck with it. But if you are looping through a vector to create another vector, chances are you could speed it up by performing the operation directly on the initial vector.

And so it goes. Happy coding!

 Posted by Matt at 3:42 am  Tagged with: ,

Project Euler Problem 5 Solution using MATLAB and Octave

 Coding  No Responses »
Mar 102011
 

The following is problem 5 of Project Euler. To date, it has been solved 87,591 times.

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?

The following is a MATLAB/Octave solution.

% ProjectEuler.net problem #005
% What is the smallest positive number that is evenly divisible
% by all of the numbers from 1 to 20?
% Given, the answer for 1 to 10 is 2520. All answers will be an increment of this.
% Below code took 9.5974 seconds to execute.
 
clear
tic();
a = 1;
b = 2520; % Increment by this, since we know all answers will be.
start = 11; % don't bother checking 1 to 10, since I'm checking multiples of 2520
stop = 20; % this is the top end of what we're polling
d=0;
 
while a == 1 % This just keeps it in a run loop.
c = start;
b = b + 2520;
 
while c <= stop
	if rem(b,c) ~= 0 % c is not a factor, end loop
		break
	else
		c = c + 1; % c IS a factor, try next higher, cycling 11 through 20
		d = d + 1; % d counts all factors. If d = num tries, we have answer
	end
end
 
if d == stop-start+1	% got answer, kick out of loop
	a = 2;
else			% did not get answer, reset counter and try again
	d = 0;
end
 
end % end "while a" loop. When we have answer, a is 2 and script ends.
 
final_answer = b
exec_time = toc()

Almost 10 seconds to execute is probably a bit much and I’m sure this could be optimized, but I’ll leave that for another exercise.

 Posted by Matt at 2:18 pm  Tagged with: , ,
 Older Entries
© 2012 mattoneal.com Suffusion theme by Sayontan Sinha