## Thursday, December 6, 2007

### Does doubling an integer double the number of factors? A Deeper Investigation for Middle School

NOTE: PLS READ THE COMMENTS FOR A DETAILED DISCUSSION OF THIS PROBLEM, WHICH SHOULD PROVE QUITE CHALLENGING FOR MOST MIDDLER SCHOOLERS.

The previous activity I posted regarding integers that have exactly four factors might lead to some interesting discussion regarding a general description of such numbers. All of these kinds of problems could be handled by simply giving students the general rule for determining the number of factors of any positive integer. I have given this well-known number theoretic formulation in earlier posts, so I won't review that at this time. However, there is a greater benefit to be derived from having students investigate these relationships. The following activity should be adapted to meet the needs of your students.

Some educators react to these kinds of deeper investigations with reactions like:

(a) I have a curriculum to cover. I don't have time for this.
(b) Unless this kind of question appears on state testing, it's simply not practical for me to do this.
(c) My students are just not ready for this kind of thinking.
(d) Dave, you're out of the classroom now, so you're forgetting the realities of most classrooms. Some students don't know their basic facts and you want me to do higher-order thinking! Gee, Dave, are you forgetting we have classified children mainstreamed in our classes? Get real!
(e) Dave, stop suggesting HOW we should teach and just give us the problem. You're trying to impose your style on others - it doesn't work - we each bring our own style to a lesson.

[Comment: I have strong reactions to some of the above, but then I'd be arguing with myself! I'll respond to some of these in the comments section or devote an entire post to these critical issues if my readers decide to respond to this.]

I'm certainly not suggesting that these kinds of explorations should BE the curriculum. There must be a balance between these problem-centered approaches and skills development. I am suggesting there needs to be some time devoted to deeper cognitive processes to foster mathematical development. The following investigation is far from one inch deep! I may continue it later but I'm hoping some will suggest extensions, make comments or report back how it played out in real classrooms (also how it was adapted/revised).

Part I
1. The number 6 has 4 factors: 1,2,3,6 (or in paired form: 1,6;2,3).
Suggested Questions:
If we double the number 6, what do you think will happen to the number of factors? Will it increase or stay the same? Will the number of factors also double?
Mathematicians, like scientists, make conjectures or educated guesses, but not wild guesses! We need some evidence or data on which to base our conjectures. With your partner, fill in (and possibly extend) the following table, then formulate your conjecture using correct mathematical language:
Positive Integer.................Number of Factors
6...........................................4
12.........................................____
24........................................____
48.......................................____

Do you think we have enough data to make a conjecture or should we continue the table? Record your observations and then state your conjecture or 'rule'.

Teacher Tip: Depending on the maturity of the group and their experience with these kinds of formulations, you may want to start them off with a prompt:
If we double a positive integer, the number of factors _______________.

Many students will be convinced they have found a mathematical rule that will always work. That's one of the objectives of this investigation: To help them understand that
(a) Pattern recognition does not a rule prove!
(b) The conjecture is based on starting from the number 6. There is no basis for assuming that their 'rule' will be valid if we start from a different positive integer!

Part II
This time have students start from a different integer: 18
Make a table similar to the one above, again doubling the integer in the left column.
Again, record your observations and then state your conjecture or 'rule'.

Suggested Questions:
Do you think there is a more general rule that covers all cases or are there simply different rules for different integers? If you were going to investigate this further, what other kinds of starting positive integers would you try?

Teacher Tip: Asking many questions stimulates student thinking and leads to more questions and deeper thought processes on their part. A free interchange for a couple of minutes is invaluable here to have students come to see that mathematical research requires persistence and an attitude of inquiry. As Ms. Fribble from the Magic School Bus would say: ASK QUESTIONS! (or something like this!).

Part III - Start from an odd integer this time: 15
Part IV: To be continued...

cecil kirksey said...

Dave:
When do you consider 1 as a factor?

Dave Marain said...

Cecil,
Unless the problem states otherwise, 1 and the number itself are considered as positive integer factors. If the problem asked for prime factors, then 1 would NOT qualify, since 1 is not prime.

Denise said...

"If we double a positive integer, the number of factors _______________."

The number of factors goes up by a certain amount with each doubling, as if we were skip-counting by some number. That skip-counting number is clearly related to the factors of the number we started with, but I don't think any of my middle school students would discover the relationship. Though perhaps I am selling them short.

Dave Marain said...

denise--
This investigation is far different from the previous one. There is no obvious conclusion this time, so the feeling one gets is similar to the final episode of the Sopranos!

After investigating a 'rule' for a few starting integers, it would appear that there are different rules involved and nothing in particular that unifies them, a very unsettling situation. For that reason, most students would lose interest after awhile and, therefore, we may want to restrict the problem to starting with an ODD integer for which the title of the post becomes meaningful. The following statement is true:

If N is odd, then doubling N doubles the number of factors.

For example, the number of factors of 15 is 4, whereas the number of factors of 30 is 8 - a simple enough ratio rule (not that we're attempting to prove it of course). However, instead of looking at the ratio here, we can also say that the number of factors increased by 4, which was the number of factors of the odd number 15.

In function notation (for the more advanced): Let f(N) denote the number of factors of N.
Then, if N is odd,
f(2N) = 2f(N).

If N is even, the situation is much murkier as is evident from the investigation and your observations.

Consider N = 60 = (4)(15). Remember, we just showed that f(15) = 4 and 15 IS THE LARGEST ODD FACTOR OF 60.
By counting factors, students can determine that f(60) = 12. By counting, they can also determine that f(120) =16. So the increase is 4, which happens to be f(15). This is wicked hard but the 2-3 students in the room who have the qualities of curiosity and persistence (which separate the future researchers from the rest) will go home and play around with it, particularly if you offer bonus points for their grade!

For this reason, the instructor will have to edit/revise/adapt this investigation according to their groups and, for most middle schoolers, this investigation is a huge reach. But, still, there is a benefit from learning that some math questions do not have easy answers. Even if they can only answer a limited part of the problem, that's significant too. That's what mathematical researchers often do: Break the problem into simpler cases, analyze each case and then ask if there is a more general conclusion. For this question, one really needs to understand more number theory - the multiplicative nature of certain number-theoretic functions - in order to see the big picture.

I suspect one will come away from this question feeling this was way too hard for middle schoolers but, again, look for other benefits of investigation beyond the answer.

Eric Jablow said...

There is a theme in combinatorics, number theory, and group theory of counting arguments. Let's try to avoid the general formula for d(n) here.

1. If d | n, then d|2n too.

2. If d' | 2n, then either d' | n, or 2 | d' and d'/2 | n. In general, both can be true. But, if n is odd, only one of the conditions can be true.

These are easy to prove. Now, assume n is odd. Consider the sets {d, 2d} where d is any divisor of n. For different choses of d, are these sets disjoint? In other words, if d ≠ e, can {d, 2d} and {e, 2e} have any elements in common? That's also easy.

So, one can sweep out all the divisors of 2n by taking the disjoint union f all the sets {d, 2d}, and so 2n has 2+2+...+2 divisors.

Now, you can ask your students the following problem: when is d(n) odd? You can get the pattern by looking at the first 10 values of d(n). A student might guess at the answer being prime squares. But extend the survey to n=20, and the student might refine her guess to be all squares.

Can a student find a pairing among the divisors of n? Certainly. Match d with n/d. Are the sets {d, n/d} and {e, n/e} always distinct for d ≠ e both dividing n? No, because e=n/d gives identical sets. But that's the only way they can intersect. If {d, n/d} and {e, n/e} intersect, d = e or d = n/e, and then the two sets are identical. So, the divisors of n can be partitioned into the disjoint union of some of the sets {d, n/d}. So, n has 2+2+...+2 divisors, an even number. Right? How could that not happen? Only when d = n/d is possible.

Going to combinatorics, one can find another kind of pairing argument. One can apply the binomial theorem to (1-1)^n to show that C(n, 0) - C(n, 1) + C(n, 2) - C(n, 3) +...± C(n, n) = 0. Rewrite this as C(n, 0) + C(n, 2) +... = C(n, 1) + C(n, 3) + ....

Let's prove this without any symbolic arguments. Consider n people (Alice, Bob, Carol, Donald, Eve...), and look at all the ways to pull an even number of people from them. Now, shout out, "Alice, change sides!" Were Alice in the subset, the subset loses a member, and you get one with an odd number of elements. Instead, if she weren't in the subset, she joins it, and you again get an odd subset. This process is self-inverse. So, there is a 1-1 relationship between even subsets and odd subsets. That's the proof.

Dave Marain said...

Beautiful description of a set-theoretic approach to the even vs odd factors, Eric!

To make the analogy closer to the problem and see why the key is to count the number of odd factors of the largest odd factor in N, consider hte following.

N = 9; Factors: 1,3,9; f(9) = 3

N=18 = (2)(9)
Factors: 1,3,9; 2,6,18;
f(18) = 6
Note that introducing the factor of 2 produced exactly 3 new factors obtained by multiplying the original odd factors by 2.

N=36 = (4)(9)
Factors: 1,3,9; 2,6,18; 4,12,36
f(36) = 9
Note that multiplying by 2 again introduced exactly 3 new factors obtained by multiplying the original odd factors by 4.

If N is a power of 2, the largest odd factor would be 1, so each multiplication by 2 would produce exactly ONE additional factor!

N=1: Factors: 1
N=2: Factors: 1; 2
N=4: Factors: 1; 2; 4
etc...

There's no doubt that even high schoolers would be hard-pressed to come up with these observations on their own, but, hey, ya' never know!

Denise said...

"If N is odd, then doubling N doubles the number of factors."

Actually, no matter what N is, multiplying it by any prime that is not a factor of N will double the number of factors. But I think you are wise to limit the discussion to multiplying by two at this point.

"... the key is to count the number of odd factors of the largest odd factor in N ..."

This is a more awkward statement than necessary. The key is to count the number of odd factors of N itself, OR to count the factors of N's largest odd divisor. No need to specify that they are odd factors in the latter case.

Normally, we list factors from smallest to largest or in (d, N/d) pairs. Looking at your last comment, Dave, I think it would help to give the students this hint: Whatever number N you start with, sort its factors into odds and evens. How does the list change, and how does it stay the same, as you double and re-double the number?