Project Euler Problem 1

Project Euler (http://projecteuler.net) is an interesting site for folks like me who like to explore math on our own terms. It’s basically a listing of a set of math problems. Each problem explains the basic concept that you’ll be using and then challenges you to push yourself a bit further. The problems are listed in order of complexity and some problems give you tools that will help you to solve problems later in the list. You can register a login at the site for free and that will let you track your progress and compare it to other users.

The first problem is stated as follows:

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.

Obviously, doing this by hand is awkward and prone to error not to mention boring so why not have a computer do it? Unfortunately computers are quite stupid so we’ll have to re-word the problem so that even the poor dumb thing can understand.

Let SUM equal our final answer and set it to 23 to start.

Let CURR equal the number we’re looking at now and start that at 11.
Does CURR divide evenly by 3?
Yes? – Add to SUM
No? – Keep going
Does CURR divide evenly by 5?
Yes? – Add to SUM
No? – Keep going
Add 1 to CURR
Keep checking.

Hmmmm…we can make this cleaner.  And by cleaner, I mean dumber.

Let SUM equal our final answer and set it to 23 to start.
Let CURR equal the number we’re looking at now and start that at 11.
Does CURR divide evenly by 3 OR by 5?
then
add to SUM
Add 1 to CURR
Is CURR equal to 1000?
then stop checking.
Test new value of CURR

So is there a point to this problem? According to the Project Euler About page:

The problems range in difficulty and for many the experience is inductive chain learning. That is, by solving one problem it will expose you to a new concept that allows you to undertake a previously inaccessible problem. So the determined participant will slowly but surely work his/her way through every problem.

So it looks like the thinking we employ here might pay off down the line. But that’s not good enough for me. What’s so special about 3 and 5?

Well, 3 is one of those ‘magical numbers’ that keep popping up wherever you look — 3 wishes, 3 Wise Men, 3 Blind Mice, etc., etc. 5 is one of those as well – five fingers on the human hand, 5 limbs on a starfish. (And don’t even get me started on the sinister significance of the number 23 )

But this is all numerological horse-hockey. I’m a man of SCIENCE!

Okay, starting again. Both 3 and 5 are primes. We live in 3 dimensions (arguably 4, though.) Also 3 is the only prime followed by a square as well as the only number that is the sum of all the natural numbers that are less than it. There are 5 Platonic Solids. 5 is also a palindromic prime as well as a twin prime.

Okay, nothing springs out to my attention here but clearly there are a lot of interesting mathematical properties for both 3 and 5 (and I included links to some sites where you can explore some more on your own). So let’s go ahead and solve the problem.

First we translate our pseudo-code to something that the computer actually understands. I have a number of choices as far as this goes. I’m quite comfortable with the bash scripting language and I’m doing this on a Mac, so here’s what I’ve got:

#!/bin/bash 
# Solution code for Project Euler problem 1
# Problem: 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.

# Set up our variables
SUM=23  
CURR=11

#Check to see if CURR is less than 1000. If it is, then quit.
while [ "$CURR" -lt 1000 ]
do
	if   !(( "$CURR" % 3 )) || !(( "$CURR" % 5 )) 
	then
		#echo $CURR is divisible by 3 or 5 # a little test code
		let "SUM+=$CURR"
	else
		# Do nothing
		echo > /dev/null
	fi
	# add 1 to the value of CURR
	let "CURR += 1"
done
echo The sum of all multiples of 3 or 5 that are below 1000 is $SUM.

The output I got when I ran this was:

The sum of all multiples of 3 or 5 that are below 1000 is 233158.

So is there anything special about this number? Let’s plug it into Wolfram Alpha (kind of like Google but for math) and see:

In binary (base 2), it’s

111000111011000110

This is kind of interesting. If we split this binary number in half, we get

111000111

and

011000110

both of which are palindromes. (They read the same backwards and forwards.) Recall 5 is also a palindrome. The first binary chunk (111000111) converts to 455 in decimal and is divisible by 5 but not 3. The second half (011000110) converts to 198 in decimal and is divisible by 3 but not 5. Okay, color me reasonably impressed.

It’s the product of two primes, 2 and 116579.

In fact, these are the only two factors of this number, despite it being an even number.

I could probably do some graphing as well but at this point I’m reasonably convinced that there’s something interesting going on here and it may come in handy as I continue down the list of Project Euler problems.

Did you find anything interesting in this exercise? Have you participated in Project Euler? Let me know in the comments!

Advertisements

One thought on “Project Euler Problem 1

  1. OMG! I love it! I have no idea who your audience is, but you are funny, wonderfully relaxed and playful, and thoroughly knowledgeable about your subject — how fun! More, please!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s