• About

j.matthew.turner

~ Director. Videographer. Editor. Geek.

Tag Archives: programming

Project Euler #6: Sum Square Difference

15 Saturday Nov 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ 1 Comment

Tags

c++, programming, projecteuler, python

From ProjectEuler.net:

The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 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.

C++ SolutionI’m just going to say it: I really don’t get why this one is even here. It has to be the easiest of all the first six problems. I usually feel like each ProjectEuler problem is cleverly designed to teach some new concept or syntax, or reveal a flaw in earlier code – but I don’t see it with this one.

Anyhoo, I used just a single loop, in which I summed all the squares, and also kept track of the sum. After that, I just squared the sum, subtracted, and there you are.

Project Euler #6 Solution

C++ Output

 

C++ code:

#include <iostream>

using namespace std;

int main()
{
    long sumOfSquares = 0;
    long sum = 0;
    long squareOfSums = 0;

    for (int i = 1; i < 101; i++){sumOfSquares += i*i; sum += i;}
    squareOfSums = sum*sum;
    cout << endl << "The difference between the sum of the squares and the square of the sums of the first 100 natural numbers is: " << abs(squareOfSums-sumOfSquares) << "." << endl;
    return 0;
}

Python:

import math

sumOfSquares = 0
sumz = 0
squareOfSumz = 0

for i in range(1, 101):
    sumOfSquares += i*i
    sumz += i

print "The difference between the sum of the squares and the square of the sums of the first 100 natural numbers is: " + str(abs(sumOfSquares-(sumz*sumz))) + "."

Project Euler #5: Smallest Multiple

29 Wednesday Oct 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ Leave a comment

Tags

c++, programming, projecteuler, python, smallestmultiple

From ProjectEuler.org:

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?

Image of C++ CodePretty straightforward: a nested loop that checks for divisibility inside another loop that counts up by 20 until the answer is found. Just a couple things I’ll say about this:

  • In constructing the inner loop, I counted down from 20 (instead of up from 1) because I figure fewer numbers are divisible by 20 and 19 than by 1 and 2. This way the first false condition is found sooner than later, and no time is wasted.
  • Further, every integer from 1 to 10 divides evenly into some integer from 11 to 20. Therefore it’s not necessary to check 1-10; 11-20 is enough.
  • I constructed my loop using a boolean flag, isDivisble, that is reset every time we increase the outer loop by 20. The flag allows me to break out of the inner loop as soon as I find a number that is not divisible, so no time is wasted.
  • Although my compiler allows me to use an int and still come up with the correct answer, the C++ standard only requires an int to hold 16 bits, or ~65,000 unique values (positive and negative). Since the answer is greater than 65,000/2, an int on some compilers may not produce the correct answer. A long is guaranteed to hold at least 32 bits, or over 4 billion unique values, so I used a long in my solution just as a best practice. With only that change, it takes twice as long to run. Efficiency is priority #1, people!
Project Euler #5 Solution

Project Euler #5 C++ Solution

C++ Code:

#include <iostream>

using namespace std;

bool isDivisible;

int main()
{
    for (long i = 2520; ; i += 20){
        isDivisible = true;
        for (int j = 20; j > 10; j--){
            if (!(i%j == 0)){isDivisible = false; break;}
        }
        if (isDivisible){cout << endl << "The smallest number evenly divisible by all integers between 1 and 20 is: " << i << "." << endl << endl; break;}
    }
    return 0;
}

Python won’t allow an indefinite range in a for loop, so I had to rewrite it to use a while loop. Same basic structure, though:

i = 2520

while True:
    isDivisible = True;
    for j in range(20, 10, -1):
        if i%j is not 0:
            isDivisible = False
            break
    if isDivisible:
        print ""
        print "The smallest number that is evenly divisible by all integers between 1 and 20 is " + str(i) + "."
        break
    else:
        i += 20

Setting up Boost C++ Libraries for Large Integers in Code::Blocks on OS X

21 Tuesday Oct 2014

Posted by jmatthewturner in C++, Geekery, Mac, Programming

≈ 1 Comment

Tags

BigInts, boost, c++, code::blocks, mac, programming, projecteuler

Having trouble getting integers larger than 64 bits to work in C++? So was I. Here’s how I fixed it:

  1. You’ll want to use the data type cpp_int provided by Boost C++ Libraries.
    1. Go here and download the zip: http://sourceforge.net/projects/boost/files/boost/1.56.0/
    2. Unzip into a forever home. (You’ll probably want this again sometime, so don’t just stick it in your project folder and forget about it.)
  2. Code::BlocksCode::Blocks needs some priming before you can use Boost:
    1. With your project open, choose: Project->Build Options….
    2. Select the Search Directories tab.
    3. Use the Add button at the bottom to add the path to your new Boost directory. This needs to be the directory that was created when you extracted the zip file. (In my case, I added /Users/jmatthewturner/C++/Boost/boost_1_56_0.)
  3. And your project file needs some special code:
    1. Add an #include for the cpp_int.hpp file that is inside boost/multiprecision/. Mine looks like this:
      #include "/Users/jmatthewturner/C++/Boost/boost_1_56_0/boost/multiprecision/cpp_int.hpp"

Now you can use the data type cpp_int, which is an arbitrarily large integer, limited only by the memory available on your machine. It is part of the namespace boost::multiprecision, so always refer to it like this:

boost::multiprecision::cpp_int myBigInteger;

or define a namespace to make your life a little easier:

using namespace std;
namespace mp = boost::multiprecision;
mp::cpp_int myBigInteger;
mp::cpp_int myFunction(mp::cpp_int x);

…etc, etc. And that should do it. I used cpp_int to help solve Project Euler #20; I’ll post the source code when I get around to writing up the problem.

Project Euler #4: Palindromic Numbers

12 Sunday Oct 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ Leave a comment

Tags

c++, programming, python

Project Euler #4 finds the largest palindrome that is the sum of two 3-digit numbers:

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.

My solution uses 3 chunks of code:

  1. a nested for loop that finds products of all 3-digit factor pairs
  2. a function that converts a product into a string
  3. a function that determines if a string is a palindrome

As usual, I wrote the solution in C++ first, but this is really the first Project Euler problem that may have been easier in Python. It certainly is easier to read in Python – the language’s string syntax is much more straightforward than C++. The solutions are functionally identical, but I think the isPalindrome() code in Python is really much more readable.

Here it is in C++:

#include <iostream>
#include <string>

using namespace std;

// the function isPalindrome returns true if a given string is a palindrome
bool isPalindrome(string x){
    if (x.length() == 1){return true;}
    if (x.length() == 2){if (x[0] == x[1]) {return true;} return false;}
    if (x[0] == x[x.length()-1]){return isPalindrome(x.substr(1,x.length()-2));}
    return false;
}

// the function isPalindromeHelper converts an int into a string
// and returns the result of isPalindrome(<string>)
bool isPalindromeHelper(int x){
    string numString = to_string(x);
    return isPalindrome(numString);
}

int main()
{
    int highestPalindrome = 0;
    int highesti = 0;
    int highestj = 0;
    for (int i = 999; i > 99; i--){
        for (int j = 999; j > 99; j--){
            if (isPalindromeHelper(i*j)){
                if (highestPalindrome < i*j){highestPalindrome=i*j; highesti=i; highestj=j;}
            }
        }
    }
    cout << endl << "The largest palindrome that is the product of two 3-digit numbers is: " << highestPalindrome << " (" << highesti << " x " << highestj << ")." << endl;
    return 0;
}

And in Python:

def isPalindrome(x):
    if (len(x) is 1): return True
    if (len(x) is 2): 
        if (x[0] is x[1]): return True
        else: return False
    if (x[0] is x[-1]): return isPalindrome(x[1:-1])

def isPalindromeHelper(x):
    numString = str(x)
    return isPalindrome(numString)
    
highestPalindrome = 0
highesti = 0
highestj = 0
for i in range(100, 1000, 1):
    for j in range(100, 1000, 1):
        temp = i*j
        if isPalindromeHelper(temp):
            if (temp > highestPalindrome):
                highestPalindrome = temp
                highesti = i
                highestj = j
print ""
print "The largest palindrome that is the product of two 3-digit numbers is " + str(highestPalindrome) + " (" + str(highesti) + "x" + str(highestj) + ")."
C++ Output

C++ Output

Project Euler #3: Largest Prime Factor

05 Sunday Oct 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ 1 Comment

Tags

c++, programming, projecteuler, python

Project Euler #3 looks for the largest prime factor of 400 billion and something. It is a straightforward problem, but it can be a study in efficiency. The trouble is that the given number is so large that the usual brute force method of counting up from 1 and checking every number would take WAY too long. Like it would still be running, and I wrote it weeks ago. Here’s the problem, as posited by projecteuler.net:

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

What is the largest prime factor of the number 600851475143 ?

My first thought was to simply start at 3, count up by 2’s (thus eliminating wasted time spent testing even numbers, which obviously aren’t prime), and test every odd number to see if it is a) prime, and b) a factor of 400 billion whatever. This method actually finds the answer very quickly, but it doesn’t KNOW it has found the correct answer until it tests a bajillion more numbers to prove that they AREN’T prime factors.

So I had to rethink my strategy. And what I came up with was to work backward, using reciprocals. Like this:

  1. Start a loop as described above, starting at 3 and counting up by 2’s (a note on where you need to count up to in a moment).
  2. On each loop iteration, check the current (odd) number ONLY to see if it’s a factor of 600 bizizzle. If it isn’t, move on.
  3. If it is, then we have actually found a really LARGE factor, in the reciprocal. i.e., 600,851,475,143 / 71 = 8,462,696,833. So, by counting up from 3, we quickly find that 71 is a factor; but we also have found that 8,462,696,833 is a factor, too. And not just any factor, but the largest factor.
  4. Next, check that reciprocal to see if it happens to be prime. If not, keep going.
  5. If it is, then stop and deliver the answer. Because with this method, the very first prime that we come across will necessarily be the largest prime factor.

In other words, this algorithm identifies factors of 600 billionzy, in decreasing order, starting with the largest. My implementation printed them as it went, so the output (spoiler alert) looks like this:

Screenshot 2014-10-02 14.55.13

Project Euler #3: Largest Prime Factor (~1s method)

Thing is, this still isn’t the most efficient method. Because in my zeal for working backwards, I completely discarded the smaller factors that I found. (i.e., I tested 8,462,696,833, but ignored 71.)

The unconscious assumption was that the largest prime factor would be among the largest 50% of all factors. But it isn’t.

Another rewrite follows the same algorithm as above, except instead of only looking at the large factors and assuming the first prime it finds will be the largest, it tests the smaller factors on the way up, as well, and keeps track of the largest prime it has found at all times. So when it finds 71, and determines its reciprocal of 8,462,696,833, it tests both for primality before moving on to the next pair.

Project Euler #3: Largest Prime Factor (0.007s method)

Project Euler #3: Largest Prime Factor (0.007s method)

That change took the execution time from ~1 second to 0.007 seconds.

Now, regarding the loop controls. A big question I had when I started was “how far up do I have to count before I know I’ve found all the factors?” Because 400 billion is big. And I had essentially the same question for the boolean function isPrime() (which checks for primality): “how far up do I have to count before I know the number is prime?”

At first, I had isPrime(x) testing every number up to x/2 looking for factors. (ie, if I called isPrime(17), my original implementation tried to divide {1, 2, 3, … 8} into 17 before it gave up and determined that 17 is prime.

But what I figured out was that you only need to check up to the square root of the number – again, because of reciprocals.

For example, 100 is divisible by 2, 4, 5, 10, 20, 25 and 50. Notice anything? Look at those same numbers like this:

{2,     4,     5,    10}
{50,   25,    20,    10}

If I Divide 100 by 2, I get 50. So I know that it’s divisible not just by 2, but by BOTH of those numbers. Similarly, testing 4 yields both 4 and 25 as factors, testing 5 yields both 5 and 20 as factors, and testing 10 reveals 10 as the square root. In terms of our isPrime() algorithm, what that means is that once I test a given number up to its square root, I have effectively tested everything after the square root, as well. Because reciprocals. Make sense?

In any case, that applies to the main function, as well – once you’ve reached the square root, you’ve identified all the factors.

So I started with a perfectly correct solution that would have taken just over 13 days to complete (really – I checked), then found another that takes just under 1 second, and finally arrived at one that takes 0.007 seconds. All valid solutions, but what a difference in efficiency.

Here’s the final code in C++:

#include <iostream>
#include <math.h>

using namespace std;

bool isPrime(long long x){
    if ((x == 2) || (x == 3)){return true;}
    if ((x == 1) || (x%2 == 0)) {return false;}
    for (long long i = 3; i <= sqrt(x); i+=2){
        if (x%i == 0){return false;}
    }
    return true;
}

int main()
{
    long long number = 600851475143;
    long long largestFactor = 1;

    for (long long i = 3; i < sqrt(number); i+=2){
        if (number%i == 0){
            cout << endl << "Factor: " << i;
            if (isPrime(i)){
                cout << " ---------- Prime";
                if (i > largestFactor) {largestFactor = i;}
            }
            cout << endl << "Factor: " << number/i;
            if (isPrime(number/i)){
                cout << " ---------- Prime";
                if (number/i > largestFactor) {largestFactor = number/i;}
            }
        }
    }

    cout << endl << endl << "The largest prime factor of 600,851,475,143 is " << largestFactor << "." << endl << endl;
    return 0;
}

And here it is in Python:

import math

def isPrime(x):
   if (x is 2) or (x is 3):
       return True
   if (x is 1) or (x%2 is 0):
       return False
   for i in range(3,int(math.sqrt(x)+1),2):
       if (x%i is 0):
           return False
   return True

number = 600851475143
largestFactor = 1

for i in range(3,int(math.sqrt(number)),2):
    if (number%i is 0):
        print "Factor: " + str(i)
        if isPrime(i):
            print "        ^^^^ Prime"
            if (i > largestFactor):
                largestFactor = i
        print "Factor: " + str(number/i)
        if (isPrime(number/i)):
            largestFactor = number/i
            print "        ^^^^ Prime"
            
print "The largest prime factor of 600,851,475,143 is " + str(largestFactor) + "."

Project Euler #2: Even Fibonacci Numbers

30 Tuesday Sep 2014

Posted by jmatthewturner in C++, Geekery, Programming, Project Euler, Python

≈ Leave a comment

Tags

c++, programming, projecteuler, python

The second Project Euler problem isn’t much more difficult than the first. The problem goes thusly:

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.

The solution is pretty straightforward: count up the Fibonacci numbers from 1 to 4,000,000, check for even ones, and add them up along the way.

Here it is in C++:

#include <iostream>
using namespace std;

int main()
{
     int a = 1, b = 2, fib = 0, answer = 2;
     while (a+b < 4000000){
          fib = a+b;
          if (fib % 2 == 0) {answer += fib;}
          a = b;
          b = fib;
     }
     cout << endl << "The sum of the even Fibonacci numbers less than 4,000,000 is " << answer << endl;
     return 0;
}

The algorithm rests on two ideas:

  1. We will always keep track of four numbers: the rolling sum which will ultimately be the answer when the loop terminates (answer), the current Fibonacci number (fib) and the previous two (a, b).
  2. We will use a while loop to control our iteration, exiting before we reach 4,000,000.

I started at the first even Fibonacci number (answer = 2), and added up from there. The loop checks to see if the next number in sequence will exceed 4,000,000, and then executes. Inside the loop, we just calculate the next number in the sequence, check to see if it’s even, add it to our rolling sum if it is, then increment a and b so that we’re ready for the next iteration of the loop. When we reach a point where the next Fibonacci number would exceed 4,000,000, we exit the loop before we get to it.

I left in a debugging line (cout << fib << endl;), because it is fascinating to me how fast we reach 4,000,000.

Here is the same algorithm in Python:

a = 1
b = 2
fib = 0
answer = 2

while (a+b < 4000000):
    fib = a+b
    if (fib%2==0):
        answer += fib
    a = b
    b = fib
    print fib

print "The sum of the even Fibonacci numbers less than 4,000,000 is " + str(answer)

Recent Posts

  • Premiere Pro’s Project Manager Can’t Handle Double-Nests
  • Encrypt Your Dropbox Files with VeraCrypt
  • Mortal Kombat and Enter the Dragon Are the Same Movie
  • 16×9 Linux VMs Inside VirtualBox
  • Adobe Releases Creative Cloud 2015

Categories

  • Advertising
  • Apple
  • C++
  • Creative Cloud
  • Editing
  • Film
  • Geekery
  • Linux
  • Mac
  • Marketing
  • Organization
  • Panasonic
  • Premiere Pro
  • Programming
  • Project Euler
  • Python
  • SEO
  • Shooting
  • Uncategorized
  • Yosemite

Recent Comments

Miquel Parejo on Premiere Pro’s Project M…
Meny on Premiere Pro’s Project M…
dnn on Project Euler #6: Sum Square…
jmatthewturner on Premiere Pro Audio Synching Pi…
Kalyan on Premiere Pro Audio Synching Pi…

Archives

  • June 2017
  • July 2016
  • July 2015
  • June 2015
  • April 2015
  • February 2015
  • January 2015
  • December 2014
  • November 2014
  • October 2014
  • September 2014
  • May 2014
  • September 2013

Meta

  • Register
  • Log in
  • Entries feed
  • Comments feed
  • WordPress.com

Blog at WordPress.com.

Cancel

 
Loading Comments...
Comment
    ×
    Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
    To find out more, including how to control cookies, see here: Cookie Policy