Patterns in Number Sequences

Oct 20, 2005 math suggest edit

You know you’re a big geek when a sequence of numbers with an interesting property just pops in your head. No, I’m not talking about myself (this time). Jayson Knight is the big geek as he noticed a pattern in a sequence of numbers that popped in his head…

This just popped into my head the other day for no other reason than to bug me: Square all odd numbers starting with 1…subtract 1 from the result…then divide by 8. Now look for the pattern in the results.

He even provides a code sample to do the math for you, but you can easily do it by hand on paper. The pattern he noticed can be phrased another way, the square of any odd number when divided by eight leaves a remainder of 1.

This is actually a pattern noticed by John Horton Conway and Richard Guy in 1996. They stated that in general, the odd squares are congruent to 1 (mod 8).

I couldn’t find their proof, but it is easily proved by induction. I’ll walk you through the steps.

The Proposition
We want to prove that

(x2 - 1) mod 8 = 0 for all x >= 1 where x is an odd integer.

Note that this is the same as proving that x2 mod 8 = 1. In other words, if we prove this, we prove the interesting property Jayson’s noticed.

Verify the Base Case
Here’s where our heavy duty third grade math skills come into play. We try out the case where x = 1.

(12 - 1) mod 8 = 0 mod 8

So yes, 0 mod 8 is zero, so we’re good with the base case.

Formulate the Inductive Hypothesis
Ok, having demonstrated the fact for x = 1, let’s hypothesise that it is indeed true that

(x2 - 1) mod 8 = 0 for all odd x > 1 where x is an odd integer

Now prove it
Here we prove the next case. So assuming our above hypothesis is true, we want to show that the it must be true for the next odd number. We want to show that

((x+2)2 - 1) mod 8 = 0

Well that can be multiplied out to…

((x2 + 4x + 4) - 1) mod 8 = 0 Note I don’t subtract the one from the four.

So just re-arranging the numbers a bit we get…

((x2 - 1) + 4x + 4) mod 8 = 0

Now I factor the right side and get (You do remember factoring right?)

((x2 - 1) + 4(x + 1)) mod 8 = 0

Ok, you should notice here that we know what’s on the left side is certainly divisible by 8 due to our hypothesis. So we just need to prove that 4(x+1) is also divisible by 8. If two numbers are divisible by another number, we know the sum of the two numbers are also divisble by that number.

Well it should be pretty clear that 4(x+1) is divisible by eight. How? Well since x is an odd number, x + 1 must be an EVEN number. We can rewrite (x + 1) as 2n where n is an integer (the very definition of an even number). So our equation becomes…

(x2 - 1) + 4(2n) mod 8 = 0

Which is naturally…

((x2 - 1) + 8n) mod 8 = 0

And we’re pretty much done. We know that (x^2^ - 1) is divisible by eight due to our inductive hypothesis. We also know 8n is divisible by eight. Therefore the sum of the two numbers must be divisble by 8. And the proof is in the pudding.

Ok, some of you are probably thinking I am hand waving that last conclusion. So I will quickly prove the last step. Since we know that the left hand side is divisible by eight, we can substitute 8m where m is an integer (the very definition of a number divisible by eight).

That leaves us with…

(8m + 8n) mod 8 = 0

which factors to…

(8(m + n)) mod 8 = 0

Conclude the proof for formality sake
And thus, proposition is true for all odd integers.

~~Sorry for such a long boring~~No need to thank me for a long and scintillating math post, but it’s been a loooong time since I’ve stretched my math muscles. This was a fun excercise in inductive proofs.

So how does an inductive proof prove anything? At first glance, for those unfamiliar with inductive proofs, it hardly seems like we proved anything. Our proof rests on an assumption. We stated that if our assumption is true for one odd number, then next odd number must exihibit the same behavior. We went ahead and proved that to be true, but it still leaves the possibility that this isn’t true for any odd number.

That’s where our base case comes in. We showed that for x = 1, it is indeed true. So since it is true for x = 1, we’ve proved it is true for x = 3. Since it is true for x = 3, we know it is true for x = 5. Ad infinitum.

And that concludes today’s math lesson.

UPDATE: Fixed a couple typos. Thanks Jeremy! Also, optionsScalper in my comments list a lot of great links about number theory and congruences. I applied his correct suggestion to clarify the mod operations by putting a parenthesis around the left hand side.

Found a typo or mistake in the post? suggest edit

Comments

16 responses

jayson knight • October 20th, 2005
Great job at explaining the proof...but I'm more intrigued by the pattern in the results of each iteration. i.e. starting w/ n=1;n+=2:

fn = (((n^2)-1)/8)

fn = 0

fn = 1

fn = 3

fn = 6

fn = 10

fn = 15

...

See the pattern yet?
Jeff Atwood • October 20th, 2005
I'm listening to "Barry White - Can't Get Enough of Your Love, Babe".

Just FYI.
Haacked • October 20th, 2005
Yeah, that's the Triangular number series. If you write the series like so...

f(0) = 0

f(1) = 1

f(2) = 1 + 2 = 3

f(3) = 1 + 2 + 3 = 6

f(4) = 1 + 2 + 3 + 4 = 10

.

.

.

f(n) = n + (n-1) + (n-2) + ... + 1 = n(n + 1)/2

You see the pattern more clearly

f(n) = the sum of all numbers n and below.

There's a story about Gauss when he was a child, he was told to add the numbers from 1 to 100 to keep him busy. But he found the answer in a very short time. He discovered that if you paired the numbers, you could simply multiply them together.

1 + 100

2 + 99

3 + 98

...

50 + 51

= 50 * 101

= 5050

The general formula is thus...

f(n) = n(n + 1)/2
optionsScalper • October 20th, 2005
Nice post. Any post with math is a good post.

A few things if I may:

1. When writing the left hand side using modular notation, it is useful to use parenthesis around the entire expression that will be the operand for the mod operation. mod has an equal precedence to multiplication and therefore the parentheses will make certain that the mod operator is applied after all operations on the expression (including the addition). Note that Jayson's code does have the parenthesis around the expression for the % operator. It appears that that is what you meant, but it is worth clarification.

2. An alternate form of this notation in mathematics is to use an equals sign with three dashes. The term is then referred to as "is congruent to" instead of "is equal to". See this page for some backgrounders:

http://mathworld.wolfram.com/Congruence.html

3. The ancient Chinese were known to study congruences and one popular result is the Chinese Remainder Theorem.

http://mathworld.wolfram.com/ChineseRemainderTheorem.html

4. Fermat's Little Theorem demonstrates some congruence math that has implications with the prime numbers.

http://mathworld.wolfram.com/FermatsLittleTheorem.html

5. Euler's Totient Function is a further generalization of Fermat's finding.

http://mathworld.wolfram.com/EulersTotientTheorem.html

6. For those with an interest in Number Theory (Elementary, Algebraic, Analytic, etc.), "A Friendly Introduction to Number Theory, 2nd Edition" (I have a 1st Edition) by Joseph Silverman is a great read. With patience and a little time, Dr. Silverman (of Brown University) will lead the reader through enough math to actually have an understanding of the proof for Fermat's Last Theorem.

http://www.amazon.com/exec/obidos/tg/detail/-/0130309540/qid=1129873701/sr=1-4/ref=sr_1_4/104-1904254-3757561?v=glance&s=books

7. To what reference to Conway and Guy do you refer? Is that "The Book of Numbers"? Guy's "Unsolved Problems in Number Theory, 3rd Edition" is one of my favorite books. (Ok, my teenage daughter still occasionally asks, "You do math for fun in your spare time? WHAT is wrong with you?").

http://www.amazon.com/exec/obidos/tg/detail/-/038797993X/qid=1129873019/sr=8-1/ref=pd_bbs_1/104-1904254-3757561?v=glance&s=books&n=507846

http://www.amazon.com/exec/obidos/tg/detail/-/0387208607/qid=1129873268/sr=1-1/ref=sr_1_1/104-1904254-3757561?v=glance&s=books

Many of these results either have a direct impact on or provide foundations for some forms of modern cryptography.

Regards,

---O

p.s. For me, you can drop "long" and "boring". It is good to see anyone who develops software for a living that can still take time for math, especially a proof by induction.
Keyvan Nayyeri • October 20th, 2005
Ok

But a problem:

You've supposed K is true and proved it's true for K+2 but what will happen for K+1?

As you used induction proof I think that it's necessary to prove it for K+1.

It means this:

You're pattern is true for 9 and also proved that it's true for 13 but how about 11?
Marty Thompson • October 20th, 2005
Keyvan:

In an inductive proof, you prove the next possible case for the assumption being proven. Since x+1 would not be an odd integer, it does not fall into the case he was trying to prove. x+2 is the next possible value for the hypothesis.
Keyvan Nayyeri • October 20th, 2005
Oh

Yeah

I didn't attend to this point.

Thanks for reply ;)
Haacked • October 20th, 2005
optionsScalper, I took your suggestions! Thanks.

Marty is right on the money. This proof only applies to odd numbers. Hence the + 2.

But I appreciate that you awesome readers are actually looking through the proof. I've had a couple small mistakes pointed out to me. I love the peer review!

That's something mathematicians do very well that I think much of the software industry is still catching up on.
lyn wilson • November 9th, 2005
Can anyone tell me the pattern in this sequence? It was posed to me as a challenge, which I have miserably failed... 1, 3, 4, 7, 9, 15, 19, 20, 39, 78, 100, 101, 102, 115, 119, 129....
sequence • May 2nd, 2006
I need help with this sequence. 3692...738...584...232. What is the next number?
Leick Robinson • May 20th, 2006
Proof by induction is a powerful tool, but after thinking about it for a few minutes, I realized that there is a more direct proof:
As you stated, we want to prove that
(x^2 - 1) mod 8 = 0 for all x >= 1 where x is an odd integer.
If x is an odd integer, then we can express it as x = 2n+1 where n is an integer.
Substituting into the expression above, we get
(x^2 - 1) = ((2n+1)^2 - 1) = ((4n^2 + 4n + 1) - 1)
= (4n^2 + 4n) = 4n(n+1).
Now, n must be either even or odd.
If n is even, then (by definition) n is divisible by 2, and so n(n+1) is divisible by 2.
If n is odd, then (n+1) is even, and so n(n+1) is divisible by 2.
Either way, n(n+1) is divisible by 2, and so 4n(n+1) must be divisible by 8.
[Or, more formally, if n(n+1) is divisible by 2, then there must be some integer m such that n(n+1) = 2m. Substituting, we get
(x^2 - 1) = 8m and so
(x^2 - 1) mod 8 = 8m mod 8 = 0.]
Keyvan Nayyeri • May 28th, 2006

Yesterday Jayson Knight had pointed to a pattern in sequence of odd numbers and had written a code...
Coach B • July 12th, 2006
Was anyone able to help with the 3692...738...584...232 sequence?
a • July 19th, 2006
46
Community Blogs • January 2nd, 2007
K. Scott Allen , Jayson Knight , and Keyvan Nayyeri all tagged me, so despite my general antipathy towards
Kalvin WIke • November 14th, 2007
What's up all...
I have a number sequence I've been challenged to crack. I have hit a block and was hoping that someone here might be able to help me.
Here is the sequence given me:1, 2, 3, 10,...(What are the next 2?)
I get the feeling that I have simply overlooked something rather obvious, but I fail to notice the pattern here. If anybody can identify this off the top of their head, I'd appreciate the help.
Thanks in advance!