Project Euler #2 – Fun With Fibonacci

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.

Do you remember those standardized tests you used to take in school, the ones that were supposed to tell you what kinds of things you were meant to do for a living? (Of course, that’s not how they were presented but effectively that’s what these tests were about, slotting you into a particular career path. For the record, I scored high on math, verbal, abstract visualization, etc., but absolutely sucked rocks on ‘clerical speed and accuracy’. Well, there goes my dream of working for the IRS…. [NOTE TO THE IRS: You folks are doing the Lord’s work and I thank you for your service. Please don’t audit me.])

Anyway, at some point in those tests you’d get a question like this:

What is the next number in the following sequence?:
1,2,3,4,5…?

That’s sort of the story behind the Fibonacci sequence, kind of. Originally described by Indian scholars, this number sequence really hit popular culture (as it were) in the 13th century when Leonardo Fibonacci published a math book that introduced them to good, God-fearing, Western European white folk. (Otherwise it would be known as the Aryabhata sequence or the Brahmagupta sequence or the Bhaskara sequence or other foreign-sounding names like that when we have a perfectly good down-home name like Fibonacci that we already know how to pronounce.)

The cool thing about Fibonacci numbers is that once you find out about them, you start seeing them everywhere – trees, artichokes, pineapples, honeybees, even in the growth pattern of mollusc shells. They have tons of practical uses as well – generating random numbers, searching, sorting, data compression and encryption. Some stock traders even use them to predict future share prices.

In fact, if you’ve ever been in a gym that uses weight circuit machines you’ve probably seen ones where the cams (the bit that the pulley belt runs over) aren’t circular but rather look kind of like a dented oval or a kidney bean. This shape is based on the Fibonacci sequence and is specially designed to distribute the weight so that your muscles are putting out a consistent level of effort. In other words, more weight is applied where your muscles are stronger.

At any rate, we’re back again with more from Project Euler. We’re moving on to problem 2, which deals with even-valued Fibonacci numbers. Now that we know what’s special about Fibonacci numbers, what’s so special about the even ones? Well, if we write out the sequence for a bit:

0 1 1 2 3 5 8 13 21 34 55 89 144

We notice that a pattern shows up pretty quickly:

odd odd even odd odd even odd odd even….

(NOTE: 0 is technically neither odd nor even.)

So every even Fibonacci number is two Fibonacci numbers away from every other even Fibonacci number. Okay, what about the sums? It turns out that the sum of even valued terms up to any specified number (like 4,000,000 in the problem at the start of this post) will always be 1 more than the sum of the odd valued terms up to that same number. (At this point, all the math nerds are holding their cigarette lighters up in the air, or more probably, smartphones with a photo of a cigarette lighter on the screen.)

Alright, time for the rubber to meet the road. Here’s how we’re going to solve this, pseudo-code style:

Let A = 1
Let B = 2
Let SUM = 2
{Keep doing this next bit until I tell you to stop}
Let X = A + B
Let A = B
Let B = X
Is B greater then 4000000?
Yes: stop and print “The sum of the even Fibonacci numbers less than 4000000 is SUM”
No: keep going
Is X even?
Yes: Let SUM = SUM + X
No: keep going

That seems pretty straightforward. Let’s do it for real:

#!/bin/bash
# Euler02 - Based on problem 2 at Project Euler
# Find the sum of even Fibonacci numbers less then 4,000,000
#
# Pseudocode:
# Let A = 1
# Let B = 2
# Let SUM = 2
# {Keep doing this next bit until I tell you to stop}
# Let X = A + B
# Let A = B
# Let B = X
# Is B greater then 4000000?
# 	Yes: stop and print “The sum of the even Fibonacci numbers less than 4000000 is SUM”
# 	No: keep going
# Is X even?
# 	Yes: Let SUM = SUM + X
# 	No: keep going

A=1
B=2
SUM=2
#X=0

while true
do
{
	let "X=A+B"
	A=$B
	B=$X
	if [ "$B" -gt 4000000 ]
	then
		break
	fi

	# is X even?
	if !(( "$X" % 2 ))
	then
		let "SUM+=X"
	fi	
}
done

echo The sum of all even Fibonacci numbers less than 4,000,000 is $SUM.

The output of this code is:

The sum of all even Fibonacci numbers less than 4,000,000 is 4613732.

Now it just takes a quick tweak to add up all of the odd Fibonacci numbers and when we do we get the result:

The sum of all odd Fibonacci numbers less than 4,000,000 is 4613731.

So it looks like our rule about Fibonacci sums works!

Consider this an open thread.

Advertisements

But When Will We Ever Use This Stuff?

If you remember my previous post on why students hate math, I pointed out one particular statement from the article I was referencing :

“In fact, for the majority of jobs, math is not included in the top five qualities that employers seek in their workers.”

I said I’d deal with it later and as it turns out, later is now.

There is so much wrong with this statement that I don’t entirely know where to start. So, in no particular order:

1. I’m sure that employers don’t ask if employees can tie their own shoes or wipe their butts, either. There are certain skills that employers simply assume are there, and that includes math. Even if math is not specified as part of the job requirements, studies show that the very process of learning math causes physical changes that improve brain function.
2. Why should the primary purpose of our public education system be to churn out good worker bees? Thomas Jefferson (you know, the guy who founded the first public university in this country) had quite a few things to say about the value of a good public education system so I won’t quote them all here but will leave you with one of the better ones:

“No one more sincerely wishes the spread of information among mankind than I do, and none has greater confidence in it’s effect towards supporting free & good government.”

3. Since when is there a conflict between being a well-educated citizen of this land (As Our Founders Intended[™]) and being a good employee? Unless, of course, you’re a really, really bad employer.

Anyway, end of rant. Please feel free to sound off in the comments.

 

The Urn of Destiny Part 2

Destiny is for people who are too lazy to create alternate timelines.
R. Stevens, Diesel Sweeties, 10-05-11

Okay, kids, if you remember from last time when we had that whole bean counting thing? Here’s where we break down the play-by-play and figure out just what was going on there.
So, our goal today is to PROVE that the last bean will always be white and along the way we’ll be able to figure out just what’s going on with that urn.
Remember the rules?

An urn is filled with 75 white beans and 150 black ones. Next to the urn is a large pile of black beans. The beans are removed from the urn according to certain rules.
Remove two beans from the urn at random.
If at least one of the beans is black, place it on the pile and drop the other bean, whether white or black, back into the urn.
But if both of the removed beans are white, discard both of them and take one black bean from the pile and drop it into the urn.

So we can summarize the rules like so, one for each possible pair of beans:

black black -> remove one black bean
white white -> remove two white beans
black white -> remove one black bean
white black -> remove one black bean

Do you see it yet?

The only way we can remove white beans is two at a time. Since there are an odd number of white beans (75), the last bean will ALWAYS be a white bean.
This is what math nerds call a rewrite system. A rewrite system consists of one or more objects (in this case, the beans and the urn) with a set of rewrite rules which take the object(s) from one state to the next. Eventually we will stop with one bean left, so this system is classified as terminating.

How many of you got it right?

 

 

Why We Hate Math I

I know that there are people who do not love their fellow man, and I hate people like that!
Tom Lehrer (1928 – )

This is the first in a planned ongoing series of posts where I try to figure out what problem(s) people have with math. Here’s the drill:
1. I search on the phrase “hate math”
2. I pick the top result (assuming it’s not this blog or one that I’ve picked before).
3. I present their argument and try (if I can) to answer it.

So today’s top link is an article from USA Today News from 07/09/12, written by Patrick Welsh (a high school teacher in Alexandria, VA) entitled “Column: Why Our Kids Hate Math

Here is his primary argument:

“I worry that we’re pushing many kids to grasp math at higher levels before they are ready. When they struggle, they begin to dread math, and eventually we lose thousands of students who could be the scientists and engineers of tomorrow. If we held back and took more time to ground them in the basics, we could turn them on to math.”

Further down, he makes a second claim:
“In fact, for the majority of jobs, math is not included in the top five qualities that employers seek in their workers.”

I feel this second point requires a larger discussion, so I’ll take it up in a separate post. For now, let’s just address the initial claim that kids are being pushed into math too early. The basis of this argument is that eighth-graders can’t handle the abstraction of subjects like algebra. His colleague Sally Miller represents this view pretty eloquently in the same article:

‘Miller, like every math teacher I talked to, says schools are pushing too many middle-school kids into algebra. “Many of the concepts in algebra are abstract,” Miller says, “and if children are not developmentally ready to deal with abstraction, you can turn them off to math forever. Even the best students who can pull off A’s in eighth-grade algebra by just memorizing eventually end up realizing they did not really learn it.”’

I do agree that math requires abstract thinking but I have two issues with this statement. First, though I’m not a psychologist, Piaget’s work on cognitive development indicates that once they reach the age of twelve children are capable of grasping abstract concepts. Unless they’re starting children in school at a different age then when I was a kid, eighth-graders should be thirteen or fourteen. Now I’m not ignoring the differences between individual children but in theory they should be able to manage algebra by the eighth grade.
My second issue is that she points out the problem in her statement without realizing it. We introduce students to math by way of arithmetic. Granted, arithmetic is the foundational toolkit for mathematics but it’s also a topic that doesn’t play to our strengths as humans. Thus we have students memorizing multiplication tables and lists of rules, properties, theorems and lemmas just so they can get through the class. Arithmetic as currently presented is as intellectually stimulating as clerical work. (No offense to clerks who love their jobs.)
So it’s no surprise that, without having had any practice dealing with abstraction, students tackle algebra using the same tools that they developed for arithmetic — memorization, memorization, memorization. (And the answers to the odd numbered problems are in the back of the book, kids!)
Humans are pattern seekers. Millions of years of evolution have developed this ability in us to a high degree. The proto-hominid who couldn’t tell whether that flicker of light and shadow in the bushes was predator or prey (and figure it out pretty damn quickly) didn’t survive to breed. Mathematics is about deriving patterns from the universe around us so it fits beautifully with our native skill-set. Numbers are our palette and arithmetic gives us our brushes, knives and canvas.
Mathematics should be a delight but instead it’s this source of terror and doubt and the problem starts with the way we teach arithmetic.

The Urn of Destiny Part 1

Not without a shudder may the human hand reach into the mysterious urn of destiny.
Friedrich Schiller
Here’s the situation:
An urn is filled with 75 white beans and 150 black ones. Next to the urn is a large pile of black beans. The beans are removed from the urn according to certain rules.
Remove two beans from the urn at random.
If at least one of the beans is black, place it on the pile and drop the other bean, whether white or black, back into the urn.
But if both of the removed beans are white, discard both of them and take one black bean from the pile and drop it into the urn.
(From Dewdney, A. K. (1993). The Tinkertoy computer and other machinations. New York: W.H. Freeman.)
If you read the rules carefully, you’ll notice that the urn loses one bean for each turn. Eventually you will reach the point where you only have one bean left. The question is, what color is that bean?
Since I don’t have an urn handy and the only beans I have are canned, I’m going to see if I can simulate this problem using my computer and find out the color of the last bean. Just like last time, I’ll sketch out the problem using pseudo code to get it into a form that my stupid computer can understand. (Note that although computers are not smart, it turns out that being stupid really, really quickly simulates smartness.)
First we set up our urn.
Bean_wht=75
Bean_blk=150

Now the next bit may seem a little strange for those of you who don’t program computers. However, it turns out that programmers have to dumb down the problem in order to get the computer to understand it, so the code can get a little..metaphorical. Programmers put a lot of time and effort to pick the right metaphor for a particular problem.
(As a side note, computers don’t really do randomness but they can fake it. The explanation is a bit obscure but suffice it to say that if computers were truly random devices then we couldn’t get any real work done on them.)
# Pick two beans at random
Let bean1 = random(black,white)
If (bean1 = white)
then decrement Bean_wht by one
else decrement Bean_blk by one
# (The bean has to be either black or white, right?)
Let bean2 = random(black,white)
If (bean2 = white)
then decrement Bean_wht by one
else decrement Bean_blk by one
# if bean1 is black, put bean2 back in the urn. If bean2 is black, put bean1 back.
If (bean1 = bean2)
then increment Bean_blk by one
If we still have more than one bean left, go pick another pair of beans ->>
if (bean1=black)
then increment Bean_wht by one
else increment Bean_blk by one
If we still have more than one bean left, go pick another pair of beans ->>

# In short, if bean1 and bean2 are both the same color, add a black bean to the urn.
# If we have one bean left, stop picking beans and report the color of the last bean.
if (URN=1)
then if (Bean_wht)
print “the last bean is white”
else print “the last bean is black”
Okay, let me take a few moments to plug this in (or something like it) and see what I get. The metaphor (or paradigm) I’m using is “There is NO urn”. I just count beans. Yes, I’m literally a bean-counter. Anyway, this is what I’ve got:

#!/bin/bash

# Beans.sh - a script to simulate the Grecian Urn problem from A.K. Dewdney's 'The 
# Tinkertoy Computer"

# An urn has 150 black beans and 75 white beans. You pick two beans at random and then
# follow these rules:

# If at least one of the beans is black, place it on the pile and drop the other bean, 
# whether white or black, back into the urn.

# But if both of the removed beans are white, discard both of them and 
# take one black bean from the pile and drop it into the urn.

# Setup

export BEAN_BLK=150
export BEAN_WHT=75
URN=$((BEAN_BLK+BEAN_WHT)) # Total number of beans in the URN

# Let's out-source our bean picking to its own chunk of code
# This is actually a bit subtle, as my initial assumption is 
# that I'm equally likely to pick a black bean as a white bean
# But we know that's not true, don't we, boys and girls?

pick_bean ()
{
	# First, check to see if we've run out of white or black beans
	if [ $BEAN_BLK -eq 0 ] # no black beans left
	then 
	{
		echo "white"
		return
	}
	fi

	if [ $BEAN_WHT -eq 0 ] # no white beans left
	then 
	{
		echo "black"
		return
	}
	fi

	RANGE=`expr $BEAN_BLK + $BEAN_WHT`
	number=$RANDOM

	let "number %= $RANGE" # pick a number from 0 to the number of beans

	if [ "$number" -lt $BEAN_WHT ]
	then
		{
		echo "white"
		}
	else
		{
		echo "black"
		}
	fi

}

#Another function to tell me how many beans I have left.
beans_remaining ()
{
echo Black beans left: $BEAN_BLK
echo White beans left: $BEAN_WHT
}

# Setup our beans
BEAN1=
BEAN2=

while [ `expr $BEAN_BLK + $BEAN_WHT` -gt 1 ]
do
{
	BEAN1=`pick_bean`
	BEAN2=`pick_bean`

	if [ "$BEAN1" == white ]
	then let "BEAN_WHT -= 1" # decrement white beans
	else let "BEAN_BLK -= 1" # decrement black beans
	fi

	if [ "$BEAN2" == white ]
		then let "BEAN_WHT -= 1"
		else let "BEAN_BLK -= 1"
	fi

	if [ "$BEAN1" == "$BEAN2" ]
		then 
		{
			let "BEAN_BLK += 1"
			continue
		}
	fi

	if [ "$BEAN1" = black ]
	then
		{
		let "BEAN_WHT += 1"
		continue
		}
	fi

	if [ "$BEAN1" = white ]
	then
		{
		let "BEAN_WHT += 1"
		continue
		}
	fi

#URN=$((BEAN_BLK+BEAN_WHT))

}
done # End of while loop

beans_remaining

When I run it, here’s my output:

isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1
isaac7:WeHateMath tsinclair$ ./Beans.sh 
Black beans left: 0
White beans left: 1

I ran it several times and it looks like the last bean left is in fact white, just as Dewdney claims. Of course, the plural of anecdote is NOT data. If I ran it an infinite number of times, would it always come out the same?

For part 2 of this post, I’d like to see if I can explain why this is and prove, if possible, that it will always work out with one white bean left. If any of you have an answer or even just speculation, feel free to post it in the comments. For you advanced types, can you tell me if it makes a difference starting with equal amounts of white and black beans?

Stupid Wolfram Alpha Tricks I

I’ve mentioned Wolfram Alpha before and I have to admit it’s my favorite math tool. There’s just something about taking that massive computational engine and bending it to my will. That being said, I recently wondered what would be the dumbest/silliest/weirdest thing I could get Wolfram Alpha to do for me.

That’s the basis of this series of posts.  That’s it. Me, being stupid, with a ginormous (yes, it’s a word, shut up) state-of-the-art, multi-million dollar piece of technology.

So let’s get started, courtesy of ScienceBlogs :

I type the following into Wolfram Alpha:

60499999499/490050000000

The result?

0.123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657…

Finally, something that takes away the sheer mindless drudgery of counting on my fingers….

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!