Matt

 

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!

 

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!

 

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!

 

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.

 

Often you’ll have a need for recording the data your programs generate. MATLAB and Octave have a few ways to do this. We can best show this with a quick example.

The following code will generate a matrix 10,000 by 6. On my current hardware this takes about 2 seconds to execute.

% Sample code to generate a large matrix
clear 
 
for i = 1:10000
	a = sin(i*pi/180);
	b = cos(i*pi/180);
	c = tan(i*pi/180);
	temparray(i, 1:6) = [a, b, c, a^2, b^2, c^2];
end

In MATLAB and Octave, the process of outputting data to files is called “exporting.” Reading data in is likewise called “importing.”

The easiest way to save the above output to a file is to use the save function and add it directly to the code. Adding the following line just below the for loop would do the trick.

save test.txt temparray -ascii

The format is: save filename variable -format. The above will result in a text file called test.txt which will contain the variable “temparray.” You can open or view this in any text editor. The default delimiter is a space but if you’d like to save it as tab-delimited data, you would simply change the line to the following:

save test.txt temparray -ascii -tabs

If you do not specify the variable, all variables in the current workspace will be saved to the file. The above could also be executed from the command line, as long as you had recently run the code and the variable “temparray” was still assigned the value you need. Worth noting is that within Octave or MATLAB, if you save without using the -ascii tag, the default will be to save the data in a proprietary binary format and you will have something like the below text at the top of your document:

# Created by Octave 3.2.4, Thu Mar 10 00:24:15 2011 EST
# name: temparray
# type: matrix
# rows: 10 000
# columns: 6
1.7452e-02   9.9985e-01   1.7455e-02   3.0459e-04   9.9970e-01   3.0468e-04
3.4899e-02   9.9939e-01   3.4921e-02   1.2180e-03   9.9878e-01   1.2195e-03
5.2336e-02   9.9863e-01   5.2408e-02   2.7391e-03   9.9726e-01   2.7466e-03
...

This may be inconvenient for your purposes (for example, if you are using the data with an external program), but if you are going to use the “load” command (described later) to import this file, it doesn’t matter that this header information is present. If it is a hindrance, you can always save the data using the -ascii tag.

Other ways to export data to a file is with the fwrite, csvwrite and dlmwrite commands. Both programs have detailed help files on these commands but in short, they are for appending to files (fwrite), saving as comma-separated-values (csvwrite) and using specific delimiters (dlmwrite).

 

The following is the 4th problem in the Project Euler series. To date, it has been solved 77,499 times.

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.

The following is a MATLAB/Octave solution.

% ProjectEuler.net problem #004
% Find the largest palindromic number that
% is a product of two three digit numbers
% Below code executed in 0.46925 seconds.
 
clear
tic();
 
% First, assume the answer will be two numbers between 900 and 999.
% If this doesn't find one, you could start at 800, then 700, etc.
% Make an array of all these multiples. Will be 10,000 elements
 
i=1;
for a = 900:999
	for b = 900:999
		new(i,1)=a*b;
		i=i+1;
	end
end
 
len = length(new)
 
temp = num2str(new);	% convert elements to strings
temprev = fliplr(temp);	% flip each element
 
index = temp == temprev; % compare the normal string to flipped string
 
% index is now an array, 10,000 x 6, of zeros and ones.
% Where all six in a row are ones, this number is the
% same forwards and backwards (temp = temprev).
% This will be the palindrome, ie., the answer.
 
for j = 1:len
	if index(j,1:6) == ones(1,6)
		max_index = j;
	end
end
 
max_element = max_index
final_answer = temp(max_index, 1:6)
exec_time = toc()

There you have it. Probably not the most efficient way to find the answer but it still executed in less than half a second.

 

This is the simplest problem yet and can be solved in MATLAB/Octave with one line of code. As of this writing, 83,275 people have solved this one. The problem states:

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

What is the largest prime factor of the number 600851475143 ?

The below code returned the answer in 0.028778 seconds:

% ProjectEuler.net problem #003
% Find the largest prime factor of 600,851,475,143
% this is trivial in Matlab or Octave
% Below code executes in 0.028778 seconds.
 
clear
t = clock;
maximum = max(factor(600851475143))
exec_time = etime(clock, t)

There you have it. The built-in function factor returns a vector of all the factors of the argument. Of course max just plucks the maximum value out of that vector.

 

Problem 2 of Project Euler follows. As of this posting, there have been 113,666 correct answers posted.

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.

Here’s the MATLAB/Octave code I used to solve the problem. This executed in 0.010 seconds on my computer.

% ProjectEuler.net problem #002
% sum all even Fibonacci numbers below 4 million
 
clear
t = cputime;
 
% create array of Fibonacci numbers
a=0; b=1; c=0; i=1; j=0; newsum=0;
 
while c < 4e6
	c=a+b;
	a=b;
	b=c; 
	fib(i,1) = c;
	i=i+1;
end
 
disp('=================');
len = length(fib)
second_to_last = fib(len-1,1)
last = fib(len,1)
sum_of_fib = sum(fib)
disp('=================');
 
% parse the even numbers out of the array
 
for j = 1:len-1
	if rem(fib(j,1),2) == 0
		newsum(j,1) = fib(j,1);
	else
		newsum(j,1) = 0;
	end
end
 
sum_of_even = sum(newsum) # This outputs the answer.
exec_time = cputime-t # This is how long it takes to execute.

I typically try to avoid too many loops in my coding, but in this problem it didn’t slow it down much at all. Probably because there are only 33 numbers in the Fibonacci sequence that are below 4 million. I ran the code again for the sum of all even Fibonacci numbers below 4 Billion and there was no change at all in the execution time. This is actually intuitive when you realize that there are still only 47 Fibonacci numbers in the sequence below 4 billion – so the code only had to loop an extra 14 times.

What about summing all the numbers less than 4 Trillion?? Still only 61 numbers to loop through. Execute time was still 0.01 seconds. Here’s a quick table showing the results of running this code with three different upper limits. Note, the last digits are approximations.

Upper Limit, Fibonacci Numbers, Sum of all Even
4,000,000           33            4,613,000
4,000,000,000       47        1,485,600,000
4,000,000,000,000   61    2,026,400,000,000

There you have it. Happy coding!

© 2012 mattoneal.com Suffusion theme by Sayontan Sinha