## Monday, April 30, 2007

### More Prime Searches...

[Update - The answers to the questions below appear in the comments section.]

I am continually amazed by some of the search phrases that lead to this blog. Although many are math topics about which readers are looking for more information, some are actual math problems that intrigue me. Here is one for today that led me to probe more deeply. On the surface it doesn't seems to require that much analysis, just an understanding of the rule for finding the number of factors of a positive integer from its prime factorization (see my earlier post on Fun with Factoring) and a good list of primes, but you may see something deeper here. At the least, it looks like an interesting investigation for middle schoolers and beyond with a webquest built in. I am indebted to the searcher whoever she or he may be!

Here's the actual search phrase I found:

1. What is the largest 3-digit integer with exactly four factors?

Before revealing the answer, I decided to expand this a bit:

2. (Easier but still worth doing) What are the largest and smallest 2-digit integers with exactly four factors?

3. Ok, so naturally, we would also ask: What is the smallest 3-digit integer with exactly four factors?

5. Keep going... What are the largest and smallest 4-digit integers with exactly four factors?

Of course, a simple factoring program written on a graphing calculator or in C++, etc., would suffice, but see how long it takes you to search and how logical reasoning and analysis can save some time. Of course it always helps to have a list of primes handy so don't forget the ultimate primes list from the U. of Utah.

Before you decide this is just a way to keep kids busy, try it. If you see a pattern or wish to expand this, go for it!

Dave Marain said...

The largest 3-digit integer with exactly 4 factors is...drumroll, pls...

998 = 2x499
998 is known as a semiprime (product of exactly two distinct primes).

How many students would simply work backwards from 999 (which has 8 factors since 999 = 27x37 = 3^3 x 37). How mnay would start multiplying primes together to see which gives a product close to 1000? The analysis here comes from recognizing that if a number has exactly 4 factors, it must be of the form pq or p^3, where p,q are distinct primes.

jonathan said...

Hmm. That one was good for me. Wrote down p^3 and pq, quickly decided that pq was going to be it... Square root of 1000 is close to 31, so checked 29*37 (too big), then 23*43, promising, 989. Switched gears, checked 991, 997...

(Switching gears is a big deal. But forgetting what one is doing - I started hunting primes instead of semi-primes - is a real danger)

Realized I had wandered off, and checked 995, 994, and 998, in order of increasing factor of annoyingness to handfactor.

I may try this with kids Friday morning.

Thanks, as always.

Will you keep writing?

Dave Marain said...

Jonathan--
When solving problems, students and the rest of us do not immediately stop to consider what might be the most efficient or logical approach. Getting students to analyze the problem first rather than do it by brute force or with the calculator is a hard habit to change. However, I suspect mathematicians do not always 'see' the best method at first. That usually comes AFTER arriving at an answer or method. We need to help students cultivate this attitude of "Now lets' reexamine the problem and ..."

Largest 3-digit: 998 (as previously noted)
Smallest 3-digit: 106 (2x53)

Largest 2-digit: 95 (5x19)
Smallest 2-digit: 14 (2x7)

Largest 4-digit: 9998 (2x4999)
Smallest 4-digit: 1003 (17x59)

Now ask your students to keep going! How long will it take htem to beg you for a program that produces price factors! For middle schoolers, it may be obvious but ask them to write a brief explanation of why 999...9 will never be the answer for the largest n-digit 'semiprime'.

jonathan said...

Dave,

this morning was "games and puzzles" day with my senior elective, and I offered a "prize puzzle" with top prize being 3 HW passes, 2nd prize being 2 HW passes, (if the scores were close.) Students chose freely who to work with, but the bigger the group, the smaller the prize/member

"11 has 2 factors, 1 and 11.
12 has 6 factors, 1, 2, 3, 4, 6, and 12
---------------------------------"
(that was on the board so that when the obvious question was asked, I could just point...)
"1 pt. What is the smallest 2 digit number with exactly 4 factors?"
"2 pt. What is the largest 2 digit number with exactly 4 factors?"
"3 pt. What is the smallest 3 digit number with exactly 4 factors?"
"4 pt. What is the largest 3 digit number with exactly 4 factors?"
"5 pt. What is the smallest 4 digit number with exactly 4 factors?"
"6 pt. What is the largest 4 digit number with exactly 4 factors?"
"7 pt. What is the smallest 5 digit number with exactly 4 factors?"
"8 pt. What is the largest 5 digit number with exactly 4 factors?"

I hadn't erased it when my freshman walked in, and some immediately engaged. Since the routine part of the lesson really was routine, I didn't mind if they distracted themselves a bit. I left it on the board the whole period, and from time to time freshmen updated their guesses (all information about prizes was gone; this was pure recreation)