23 November 2007

Numbers that "look prime"

From MathNotations, which is a math education blog. A suggested activity for high schoolers:

Using positive integers, think of primes ending in 1 or 3 (you may want to use the technically precise phrase 'whose units digit is 1 or 3'). For example, 21 'ends in' 1, but it is not prime. You must go in order and you are not allowed to ask the number the previous person gave!

I tried doing this myself; it's surprisingly hard! I would never be so foolish as to say 51 is prime... but I said to myself "41... 43... um, what comes next?" It's something about looking at that list of numbers out of context; a significant part of my knowledge about which numbers are prime is apparently just being able to recite the first thirty or forty (up to 150 or so) pretty quickly. ("Recite" is not quite the right word; I tried to actually do this and once I got past 37 I realized that I was not quite working from memory so much as doing trial division.)

Also, I have to share the old joke that 91 is the first number that "looks prime" but isn't. The argument is that multiples of 2 and 5 "look composite" (by looking at their last digit); multiples of 3 "look composite" since people know the fact that a number is divisible by 3 if and only if the sum of its digits is; and (two-digit) multiples of 11 "look composite" because of their repeated digits. Furthermore, squares don't "look prime". So the smallest number that looks prime, but isn't, is 7 times 13, or 91. After that, numbers that look prime but aren't are:
119, 133, 143?, 161, 187, 203, 209?, 217, 221, 247, 253?, 259, 287, 299.
(I put a question mark after multiples of 11 because I'm not sure how to count multiples of 11 which are greater than 100. And of course, this criterion of "looks prime" is subjective; for example, I don't think 217 or 287 look prime, since they can easily be written as 210 + 7 or 280 + 7 and thus their factorizations as 7 × 31 and 7 × 41 are obvious)

so there are 14 "psuedoprimes" in the range from 100 to 300, compared with 32 actual primes in that range. So this test isn't too bad in that range. Of course, eventually it becomes quite bad; it identifies (1/2)(2/3)(4/5)(10/11) = 8/33 of all integers as primes (ignoring the fact that it identifies squares as nonprimes), when the actual density of the primes is zero. In the limit, almost all of the numbers identified by this test as primes are in fact composite.


.mau. said...

143 is ostensibly one less of 144 which is a square, so I would not say it could be a prime :-)

Dave Marain said...

You're absolutely right - this is harder than it looks! Obviously, most of our middle schoolers and high schoolers haven't worked enough with the sequence of primes up to 150 or so to be fluent. One of the purposes or benefits of activities like this one is to provide enough practice with primes
so that students who ordinarily freeze up under pressure or don't pay much attention will actually improve over time! Their confidence, accuracy and speed become progressively better so that more students remain standing. Initially, your best students will generally survive the first couple of rounds and prevail, not only because they have more fluency with primes and better retention but, most importantly, because of their ability to focus and concentrate which separate them from the rest. As an educator I recognize that some students are naturally more capable in that area but I do not then assume that others in the class cannot improve their performance via many such activities. We (not you!) often overlook that activities such as mathematics, playing chess, etc., develop our powers of concentration as well as our reasoning ability.

By the way, I view myself as both a math educator and a mathematician, but my blog is most often classified as a 'math ed blog', I guess because I write activities for the classroom teacher. Oh well...

I realize that your focus was more on numbers that appear to be prime but aren't but I did want to mention this issue of cognitive development that is also important to me.

Isabel, thanks again for linking your many readers to my blog.

Dave Marain

.mau. said...

I reread my comment, and I noticed it could be misunderstood. Of course 143 is not a prime number; I wanted to say that - at least for me, like 217 and 287 for Isabel - when I see it I immediately know it is not a prime number.

Jack said...

Also, 253 doesn't look prime to me, because the middle digit is the sum of the other two, which makes it a multiple of 11.

(1979 Texas Mental Arithmetic Champion!)

John Armstrong said...

I'll follow Grothendieck. 57 is prime!

Dave Marain said...

One of my favorite patterns is 1,11,111,1111,11111,... Are any of these prime after 11? Which ones are easy to eliminate? A related sequence would be 101,1001,10001,...
Lots of interesting connections to algebra here (which is of course part of pure number theory).

John Armstrong said...

Which ones are easy to eliminate?

Any composite length goes right away. Three is also out by inspection. The rest are tough, but the 19th and 23rd in the sequence seem to be prime, so they're not all composite.

Charles said...

Yeah, I have to agree with jack. Multiples of 11 do have an easy test, even in many digits. A number is divisible by 11 if and only if (I think) the sum of the odd position digits is equal to the sum of the even position digits. It's not quite as nice as 2,3,5 but it's workable.

Dave Marain said...

John, a nice reference for these 'repunits' as they are called is the
MathWorld article
A necessary condition for the nth repunit, a string of n 1's, to be prime is that n is prime (otherwise it's easily factorable) but this is not a sufficient condition. Lots of research about these kinds of numbers.