Monday, February 12, 2007

A Number Theory Problem for 2-12-07: Mission Impossible?


Thanks to jd2718 for motivating me to include the following famous number-theory conundrum. You can find many references to it on the web but I remember it from the classic text by Hardy and Wright. Give this as a challenge bonus problem or as an activity for your middle or high schoolers. Revise and modify it to make it appropriate for your students. I've tried to turn this into something students can at least attempt, but you could probably make it much more user-friendly...
Remember: My goal is to provide meaningful activities for ALL of your students, not only for honors or accelerated classes. The challenge is to modify them for students who struggle in math. The real test comes when I implement today's problem in my 'skills' class to which I frequently refer. That is my plan -- I'll let you know if it worked or was a disaster! Pls note that these activities also provide practice for those open-ended types of questions that now frequently appear on standardized and state assessments.
Finally, I hope you enjoy these challenges, but my primary target audience is students. I am really interested in reading students' reactions to these.

Now, boys and girls, we know that, despite all attempts by the most famous mathematicians, no one has yet devised a formula for primes. At one time, it was thought that 2^p-1 would always be prime if p is prime:
2^2-1 = 3; 2^3-1 = 7; 2^5-1 = 31; 2^7-1 = 127 -- all primes. But alas, 2^11-1 - 2047 = (23)(89). Imagine the disappointment!
But I think I found a method that will produce primes EVERY time! If you can do all parts below and prove I'm wrong, you get 5 bonus points. You'll get at least one point for doing part (a).

Ok, I decided to start with my favorite prime 41, since that's the age I once was!
41 + 2 = 43
43 + 4 = 47
47 + 6 = 53
53 + 8 = 61
61 + 10 = 71
71 + 12 = 83
Here's your mission:
(a) I listed the first 6 and they're all prime. You can see the pattern, right? Keep the sequence going until you reach 40 numbers. Check that they are all prime by researching a list of primes on the web. So, am I right? Am I famous now?
(b) My method is easy to see but harder to describe algebraically. Here's one way:
To get each number in the list after the first, you can see that I added the next even number to the preceding term. SHOW that the following recursive description produces the first 6 terms:
a(1) = 41; a(n+1) = a(n) + 2n, n = 1,2,3,... where the notation a(n) refers to the nth term. Then explain why this will generate all the terms.
(c) This one is harder but I'll give you a hint: Devise a polynomial that will generate this sequence of numbers when n = 1,2,3,....
Hint: Think of a quadratic like n^2 +.... Just remember, when n is replaced by 1 it has to yield a value of 41!
(d) Show that my amazing sequence 'blows up' when you reach the 41st term. Why? There goes my million dollars from the Clay Institute!
Extension: Is there any other sequence like this? What's special about 41? Happy web-questing...


Totally_clueless said...

For (c), the numerical math may be made easier if in part (b), you start the indexing at 0, thus a(0)=41. This can also introduce the concept of a zero index to the students, which may be useful later when they learn programming.


Dave Marain said...

good suggestion tc!
remember, i implemented this in my class of freshmen who struggle in math.
Here's what happened:
I needed to review powers of 2 for a few minutes. I did this by continuing the 'unsummable' numbers from the previous lesson, a natural link to this lesson. I then developed the sequence of primes on the whiteboard. After about 10 minutes, they got into their teams and I gave them the handout which developed the activity more gradually than I suggested in my post. I also gave them a handout from the web (U. of Utah) listing the first 1000 primes, since I didn't have time for them to do an internet search. We got through the 2^p-1 problem in about 5 minutes. I had them develop the recursive sequence starting with 41, but some needed help in recognizing the pattern. They recognized the addition of the next 'even' number but missed the fact that the output from each step became the next input. I could have introduced the concept of recursive sequences prior to this but I decided to let it evolve. Most got it the first time. J.J. was able to get through the first 24 terms of the sequence by the end of the period. For each result they had to check if the result was prime using the reference table. They will finish this up tomorrow.
Remember, I'm trying to give you immediate feedback in real time. This leaves me wide open for 'constructive' criticism but that's what this blog is all about. If you see ways to improve on this activity, go for it! Most importantly, I would have taught this lesson quite differently for an advanced class.

jonathan said...

Dave, I may run this for a few minutes for 'fun' one day this week, maybe right before vacation. I'll let you know if I do, and how it goes.

I do not think I will supply lists of primes. Let the kiddies test, and practice breaking up and sharing the work.

Dave Marain said...

i made a decision that i felt would work best for this group; however, it might have been much more fun for them to discover for themselves if the results were prime since looking it up in a table seems to be of little value; but we each know our 'children' best and we go with our instincts; they worked again for the whole period and didn't leave their seats or ask to leave the room once -- this is an extraordinary achievement, trust me! i will up the ante tomorrow and we'll see what happens we discuss recursive formulas!

Eric Jablow said...

Do they know why one can test a number n for primality by trial division only up to Floor(Root(n)) yet?

Have you tried some non-numerical math probles yet, like the simplest case of Ramsey's Theorem, or the Bridges of Konigsburg? These might help them realize that mathematics is not simply about numbers.

Dave Marain said...

great ideas! do they know these things? no and no! should they? yes! they can certainly learn to test primality up to [sqrt(n)]; i think i'll show them that tomorrow; the network problems are definitely worth pursuing...
Understand that my curriculum is somewhat open-ended but I am guided by the 4 main clusters tested on the NJ state assessment (HSPA):
1. Number Sense, Concepts and Applications
2. Spatial Sense and Geometry
3. Data Analysis, Probability and Statistics and Discrete math
4. Patterns, Functions and Algebra
Right now, I am combining Clusters 1 and 4. My emphasis is not on primes as much as it is geared towards generalizing patterns and developing formulas. I'm using the context of number theory because I have a passion for it and because it is engaging. Having these students engaged and experiencing success is just as important as the content if you get my drift...

jonathan said...

Developed 1 + 2 + ... + n ?
(multiple proofs)
Fibonacci? (Ghost the Bunny
How many diagonals in an n-gon?
Develop a formula for the nth centered hexagonal number? (rows are offset, so that we get lots of 60 degree angles. The first number is 1, the next is 7, the next is 19 (rows: 1, 2-3-2, 3-4-5-4-3).

All good for recursion.

mathmom said...

Jonathan, I was just trying to think of other problems related to the handshake problem, and diagonals in an n-gon seems to fit the bill. Also how many points of intersection n lines can have, I think.

I like this lesson, but I would have had my kids do the primality testing on their own. I wonder if they would take the time to check divisibility rules they know before grabbing a calculator...

Dave Marain said...

ok i guess most feel the actvity isn't rich enough without having the students test for primality themselves! although i see your point, my main goal was to have students learn how to use a recursive function or work with a quadratic function, namely,
f(n) = n^2-n+41. A curiosity involving primes was simply the vehicle for this. If this were a middle school lesson, my focus would have been on the primes. Now these youngsters absolutely need review of prime factorization, divisibility tests and much of fundamental mathematics, but I'm trying to ready them for a standard algebra course for next year. i guess i didn't do a good enough job of conveying the needs or nature of the class.

I appreciate the suggestions however! i've already worked through some of the combinatorial problems suggested by jonathan.

Another good one is using lines to divide a circular region into non-overlapping parts. Thus, 1 line divides a circle into at most 2 regions, 2 lines into at most 4 regions, now try 3,4,5 lines. This is well-known but students easily fall into the obvious pattern of 2,4,6! They don't expect the answer for 3 lines to be 7 regions! I may actually use this one in class since it can be described recursivley or with a general formula for the nth term, another quadratic!

Eric Jablow said...

I haven't taught for 17 years, and never at the high school level. I don't know what standards require, although I agree with their necessity. I just want to avoid having students think that mathematics is only glorified arithmetic.

Even so, alongside the required course content, you are trying to help them think mathematically. Here's something else you can do.

Q: "How many games are there in the Division I NCAA Men's Basketball Tournament?"

A1: 1 (play-in game) + 32 (1st round) + 16 (2nd round) + 8 (3rd round) + 4(4th round) + 2 (semifinal) + 1 (final) = 64.

A2: 65 − 1 = 64. There are 65 teams, every game has a loser, no one loses twice, and only one team doesn't lose.

Show how much of mathematics involves simple counting arguments. Now, take off on this idea to get to geometric series. You might thell the fanciful story of the Caliph, the chessboard, and the advisor's reward.

mathmom said...

I did say I would have had my kids (middle school) do the primality testing themselves, mainly because it would relate to work we have done recently on primes, divisibility rules, factorization, etc... For your kids, the decision to give them the list of primes was perfectly reasonable.

Dave Marain said...

i love the elimination method for solving the ncaa tournament problem; we're approaching March Madness so the timing is right!
I'm sure you know that I take the mathematics very seriously so I work hard to convey that math is so much more than computation. However, many youngsters come to us with major gaps in their background. I have to rectify some of that while developing their reasoning skills, problem-solving strategies, and ability to communicate their methods all while teaching algebra and geometry content. I love these kids but they certainly test my patience and require considerable creativity on my part - guess that's what teachers do!

I'll try harder not to get defensive! You understand that there is a risk-reward when sharing not only activities but describing in 'real time' how the lesson went. This is 'reality' blogging for educators - I'm doing it to encourage others to do the same. How many similar detailed anecdotal descriptions have you found describing both the successes and failures of what we do every day. I want others to know it's ok for a lesson not to be perfect. That's part of the practice of our profession. if i want to improve and help my children learn better I have to accept the criticism. I'm trying to model this for others...

Dave Marain said...

Update on lesson today:
I gave students time to complete their recursive number-crunching, asking them if they were getting any non-primes in the sequence. Some did, long before they should so i suggested they check their work. I quickly realized that if a student makes an error in the 8th term for example, then the problem quickly unravels. So I stopped them and we listed the first 15 or so to make sure we were on the same track. Some made errors and were ready to just give up rather than go back and re-do these more carefully. That is a natural reaction. Half-way through the period I made a decision to change the activity. Rather than develop the idea of a recursive description or function, I decided to give them the quadratic
n^2-n+41. This required that I renumber the sequence of terms making the first term, 41 which was out of place in my original list (as tc so ably pointed out).
Ok, boys and girls, turn on your graphing calculators, work with your partner and follow exactly what I'm doing on the overhead calculator. Enter this 'formula' into Y1, using X in place of n. Now Set the TABLE to start with X = 1, etc., now go to 2nd TABLE and tell me what you see! "Hey, we didn't have to figure out each number!" Ok, now check each term of your sequence (careful use of terminology) to see if there's any discrepancy. When n or X = 41, what number do we get: 1681! What's special about that number? It's not in the list of PRIMES! By the way, what else do you notice about that number? No response... Is 16 a perfect square? One student agrees. What about 81? Is 1681 a perfect square? How can we tell?

Ok, now, have I produced a formula that will 'always' generate primes? NO! Do you think after n = 41, there will be any more primes in the list? How can we check that? Most are losing interest but JC is still working on his list because he wants to score 10 out of 10 on this activity and he is really focused this morning...
What objectives did I accomplish? How do I know?
Did the TABLE function of the calculator help them to begin developing an understanding of functions? How will I know? How can I develop this further. Should I have changed my approach midstream or gone with my original plan? hey, I've been doing this a long time and I'm strill learning so much from them...