Pattern Breaking II

This is a followup to Pattern Breaking.

Since I got interested in apparent patterns that break later on, I’ve discovered an article on this very subject by Richard K. Guy, published in the American Mathematical Monthly over 20 years ago! Also, Justin Lanier has directed me to a discussion on this topic at MathOverflow with many more examples. Lastly, I’ve got a solution to the computational half of the problem that many of the examples found in these sources are not conceptually or computationally accessible at the secondary level. Namely, I’ve come across a couple of computational resources that might help to bring some of these examples (especially the ones involving primes) within striking distance of a lesson you might create at the middle or high school level.

The article is called “The Strong Law of Small Numbers” and is found in Vol. 95, No. 8 (Oct., 1988) of the AMM. Here it is as a pdf. It is somewhat silly in tone, but it is actually more academically serious than anything else I’ve pointed you to thus far. Here is how it starts:

This article is in two parts, the first of which is a do-it-yourself operation, in which I’ll show you 35 examples of patterns that seem to appear when we look at several small values of n… The question will be, in each case: do you think that the pattern persists for all n, or do you believe that it is a figment of the smallness of the values of n that are worked out in the examples?

Caution: examples of both kids appear; they are not all figments!

In the second part I’ll give you the answers, insofar as I know them, together with references. (p. 697)

The compendium of patterns is excellent. Credit where credit is due: some of my favorites so far, e.g.

The points on a circle pattern;
The fact that 31, 331, 3331, …, 3333331 are all prime;
The fact that 3!-2!+1!, 4!-3!+2!-1!, …, 8!-7!+…+2!-1! are all prime

were in this article before they were anywhere else I’ve found them. In addition, Guy has interesting commentary on what’s going on – for example, he offers some insight regarding why the points-on-a-circle pattern matches the powers of 2 in the first 5 cases and then breaks.

Now, I became interested in these pseudo-patterns because I think they’re pedagogically important. Guy has a different angle: he is actually trying to say something about math. In his view, pseudo-patterns like this are quite common, because of his eponymous “Strong Law of Small Numbers”:

There aren’t enough small numbers to meet the many demands made of them (p. 698)

It’s worth it for you to download the pdf. The article is a good and enlightening read all the way through. I’ll share one more pattern (or almost-pattern? which is it??) from it but really I recommend downloading the whole thing.

Example 24. Consider the sequence
,

	0	1	2	3	4	5	6	…
	1	2	3	5	10	28	154	…

Is always an integer? (p. 704)

Okay. Secondly. Justin Lanier pointed me to a source of a good many more examples of patterns breaking: a discussion of this very topic at MathOverflow. (This is a link to the Wikipedia article to tell you what MathOverflow is. There is a link to the actual site at the beginning of this post.) Here it is:

MathOverflow: The phenomena of eventual counterexamples

Justin also directed me to a particular link within this discussion:

“Law of Small Numbers”… more examples!

So, here are two more sources for patterns that break. The repository is growing…

Now a drawback of some of Guy’s and many of MathOverflow’s examples are that they are not really accessible at the middle or high school level. Now in some cases this is because of the concepts involved. But in other cases, it’s just a matter of the computations being out of range. For example, Guy mentions a famous example several of us also noted when I first raised the issue: Fermat’s conjecture that is always prime. This is true for n=0, 2, 3, 4, and wrong for n=5, but is over 4 billion and its smallest prime factor is 641. Not something the kiddies can find out, even with a calculator.

Enter PARI/GP. This is an open-source computer algebra system that does number-theoretic calculations at ludicrous speed. For example, just now I had it execute the following self-explanatory code:

{t=0;
for(n=1,20000000,
if(isprime(n),t=t+1)
);
print(t)}

Running on my new MacBook, it produced the output (1,270,607) in about 24 seconds.

In other words, it individually assessed the primality of twenty million numbers, most of them fairly large, in under thirty seconds.

In other words, if you want to do a lesson based on Fermat’s conjecture and want to make it computationally possible, PARI/GP has you covered.

Now it is freely downloadable at the link above. It is not particularly user-friendly, however. Downloading and installing it forced me for the first time to interact with my Mac’s UNIX interface. The installation instructions at the PARI/GP website are not designed to be comprehensible by someone who doesn’t know anything about UNIX. For some reason, no one I asked for help seemed to be 100% able to comprehend the existence of people like me who want to install a piece of software like PARI/GP but don’t know anything about UNIX. I had a lot of trouble getting the answers I needed. The whole experience was pretty frustrating. If you want to download and run this program on a Mac but don’t know how to install something in UNIX, feel free to email me.

Now in order to take PARI/GP into the classroom, if you have a smartboard or projector or something and can get it on one computer, you can do experiments with the whole class. If you want to have the kiddies interact with it, you need it on more than one computer. Also, it doesn’t produce files so to have kids save their work you have to show them how to have it import text from a text editor. All this has to happen in UNIX. This could be a pain.

Enter SAGE. SAGE is another open-source computer algebra system with the following key advantages:
a) You can run the whole thing online!
b) You can save your work online!
c) You can run PARI/GP from inside SAGE!
PARI does not run as fast if you’re using it inside SAGE online as it does if you download and compile it on your computer. Also, SAGE is not the most dependable piece of internet software there is. (It struggles in particular when accessed through Safari. I recommend Firefox.) But, if you want to bring this computational power to the classroom, without requiring any administrators to invest in any piece of software, this is the way to go. All you need is computers with internet access.

If you are having any inklings you’d like to try these resources out in the classroom, I recommend you go play with SAGE right now. Go to the website, click “try SAGE online,” sign up for a new account, and then click “new worksheet.” To access PARI/GP, choose “gp” from the 4th drop-down menu below the worksheet title. (The one whose default is set to “sage.” Btw, PARI is only one of the many amazing computational software packages you can access from inside SAGE. SAGE is kind of its own one, for example. In fact, it can do a lot of what PARI can do. But PARI is faster with the large-scale computations.) You can find users-guide typed materials (none particularly user-friendly, but oh well…) in a link inside the SAGE worksheets. For PARI you can find them on the PARI website. It helps to be familiar with the basic structure of computer programming languages.

Anyway, I think there are a lot of awesome classroom activities waiting to be made out of SAGE and PARI and a few of the pseudopatterns found in the Guy article and at MathOverflow. Here’s one thought, based on a pseudopattern mentioned in Guy (although actually I learned about this example in a workshop led by John Cullinan, which is also where I learned about PARI). Question: how would you turn it into a classroom-able activity at whatever level you teach?

Are there more primes of the form 4k+1 or 4k+3?

(What does this question even mean?)

Just by counting the small cases:
For primes less than 10, one (5) is 4k+1, while two (3 and 7) are 4k+3
For primes less than 30, four (5, 13, 17, 29) are 4k+1, while five (3, 7, 11, 19, 23) are 4k+3
For primes less than 100, I resorted to PARI. I opened a SAGE worksheet, set it to PARI mode (i.e. picked “gp” from that drop-down menu), and entered:

Ones(n)=\
i=0;\
forstep(k=5,n,4,\
if(isprime(k),i=i+1)\
);\
return(i)

(Some basic syntax info:
*In PARI/GP, everything is really meant to happen on 1 line. Every time you press return, the program executes whatever you entered. If you’re running GP inside SAGE, you use backslashes to split something up over several lines that is really supposed to be 1 line.
*Commands always enclose their arguments in parentheses.
*Use semicolons to separate commands from each other.
*forstep(k=this,that,stepsize,dosuchandsuch) has k count up from this to that by whatever the stepsize and executes suchandsuch for each k.)

Then I entered:

Ones(100)

PARI says there are eleven primes less than 100 of the form 4k+1.

Threes(n)=\
i=0;\
forstep(k=3,n,4,\
if(isprime(k),i=i+1)\
);\
return(i)
Threes(100)

PARI says there are thirteen primes less than 100 of the form 4k+3.

So it looks like the 4k+3’s are consistently outnumbering the 4k+1’s. Will this stay true?

How could we find out?

If you want to go experiment on your own, do it.

If you want some guidance, try this code:

PrimeRace(n)=\
i=0;\
j=0;\
forstep(k=3,n,2,\
if(isprime(k),\
if(Mod(k,4)==1,i=i+1,j=j+1);\
if(j-i<0,print(k))\
)\
);\
return(j-i)

This creates a routine that runs through all the odd numbers from 3 to n and asks if they’re prime. If they are, it checks to see if they’re of the form 4k+1 or 4k+3, and keeps track of the totals. If at any point the 4k+1’s are leading, it prints out whatever prime numbers this happened at. (The if command can be either if(condition,dothisthing), or if(condition,dothisthing,andifnotthendothisthing). I’m using it both ways here.) At the end, it prints out the total amount by which the number of 4k+3’s exceeded the number of 4k+1’s.

Okay, now you can play around with it.

…

More guidance? Alright, but ***SPOILER ALERT***

Have it evaluate:

PrimeRace(10)

Yup, in the first 10 numbers, the 4k+3’s are up 1 as we previously counted.

PrimeRace(100)

Up 2 now, matching what the One(100) and Three(100) functions told us before.

PrimeRace(1000)

Up 7 now.

PrimeRace(10000)

Up 10 now. Aren’t you in suspense?

PrimeRace(30000)

Up 22 now, but what is that other number it printed out? 26861?

PrimeRace(26861)

Yes, for one moment, at 26,861, the 4k+1’s take the lead! But 26,863 is prime as well, evening it back out, and then the 4k+3’s retake and stay in the lead all the way to thirty thousand. How crazy is that?

PrimeRace(700000)

I’m not gonna say anything. Just run it.

Advertisement