# Student Project about Prime Numbers: How to Continue?

I know a talented, enthusiastic, and very very hard-wroking 7th grade student, who began working on a research project about prime numbers a month ago.

He has written numerous Pascal programs to find large prime numbers (using methods such as sieve of Eratosthenes) and twin primes, computing density of prime numbers and twin primes and their relative frequencies in successive intervals of arbitrary length, etc. His programs work quite fine and fast. He consistently improves his codes, e.g. his last code for finding prime numbers yields all primes less than 1000000 in 3 minutes (the first one took 3 hours!).

Also, he knows/has discovered some theoretical facts about prime numbers, e.g. how to prove that there are infinitely many primes, and why the twin primes are of the form $6k-1$ and $6k+1$.

My Question: What are the possible directions for him to continue his research project (via programming or pure mathematical practice), without facing technicalities?

Thanks.

• This is an open-ended, personal project? – NiloCK Jan 29 '15 at 16:32
• @NiloCK Yes, it is. – Behzad Jan 29 '15 at 16:36
• Since every prime except $2$ or $3$ is one more or less than a multiple of $6$, it doesn't need much to see a pair of twin primes must be of the form $6k-1$ and $6k+1$. It would be more interesting to understand why there are infinitely many primes of the form $6m+1$ and why there are infinitely many primes of the form $6n-1$, which refines the fact that there are infinitely many primes altogether. – KCd Jan 29 '15 at 23:01

Your student may be interested in solving the Project Euler series of problems. These are programming exercises to solve mathematical challenges, many of which deal with number theory. All of the exercises are designed such that the running time on a normal personal computer should be not much more than a minute. However, achieving reasonable running times will often require the clever use of a theorem or algorithm. Therefore, these exercises are valuable for gaining knowledge in both pure and applied mathematics.

The solutions for Project Euler questions are discussed on many websites. One website that I highly recommend is Code Review, where there are currently over 200 questions about Project Euler problems. Other programmers will give feedback, both on the coding style and mathematical principles.

Of course, Code Review questions about any programming project are welcome too — as long as the code works as intended.

(Note that minors under age 13 should have a parent create the account.)

• Good catch on the under 13. Parent should create and actively supervise the account. – Richard Jan 30 '15 at 2:49

Ask them how much they would like to discover on their own and reinvent, and how much they would like to do research and verify results as a stepping stone to becoming an independent researcher.

Ideally, the student will find resources on his own, such as the Prime Pages by Chris Caldwell, Ribenboim's books on primes and Diophantine equations, Crandall and Pomerance's book on computational number theory, and many other nontechnical and technical results. Sooner or later, this student will have to make up or adopt terminology for the concepts he will encounter, such as pseudoprimes, primality tests, prime constellations, and the like. You can tell the student about these piecemeal to keep the fire going, or give them a wheelbarrow full of resources and see if they get overwhelmed. I recommend that if they have a question you can't handle, that you direct them to math.stackexchange, where it may get a technical answer.

If you visit my homepage on MathOverflow, you will find a reference to my email address there. I have some computational projects involving coprimality, and am willing to give some of them over to youthful energy.

Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2015.01.29

• For a senior high school student, I would agree with the above. However, as the student may not even be 13, directly interacting on social media sites like stackexchange may be unwise and may contravene user agreements. In general, students of that age have a hard time evaluating the reliability or appropriateness of Internet information, so at this stage I would recommend that it is the teacher or parent's job to help the student as they search for information. – Richard Jan 30 '15 at 2:42

side note: If he is not using iPython, he might give it a go. There are free cloud based iPython notebooks and it is an excellent environment for investigations, with easy graphing etc. A couple of my students of similar age use it.

Test for primality rather than finding all primes

First I would show him how to extend his research by tweaking his current algorithm. As he can compute all primes up to $10^6$, he can evaluate primarily up to $10^{12}$ without any libraries and with basically the same algorithm.

He can therefore investigate prime conjectures much higher than he can evaluate and store a complete list of primes.

Mersenne Primes Test these and any other related conjectures he can devise up to $2^{40}$

Distribution of primes

An interesting case might be estimating the distribution of primes using statistical sampling. He could then try informal curve fitting. He could make predictions on the proportion of primes at various sizes of numbers and test them.

Non-prime related Montecarlo investigations

After he has got used to sampling, he can move away from primes and implement any number of Montecarlo algorithms.

He can easily calculate the value of $\pi$. He should be able to handle Pythagorus to find the distance from origin of a point. A simple method could be to make a random point with x,y each in [0,1], and count the proportion that is less than distance 1 from the origin. This proportion is the area of a quarter of a circle of radius 1 ($p\times 4 = \pi$).

Further to the above, he could investigate how many extra trials it takes to make an improvement of a significant figure.

Montecarlo methods opens up a range really interesting applications for computationally intensive mathematics.

probability

He can investigate the statistical distribution of rolling 1-2 dice, and possibly compare to the theoretical distributions. Lots of common statistical laws or fallacies can be investigated.

Or investigate basic binomial distributions with coin flips. He could find the exact distribution for 8 coin flips (maybe counting bits in integers up to $2^{8}-1$. What is the likelihood of getting 8 heads in a row? Or n heads in a row?

At some point he will need to take a statistical approach as the number of coin flips increases. What is the mean number of heads in n coin flips? He should be able to sort his list of results using a library function, and therefore easily find the interquartile range. How does this change as the number of flips increases?

If you use a weighted coin how does the above change?

The problems you describe are the tip of an iceberg call "Computation Number Theory" and a google search should turn up a variety of resources at various levels.

One possible route is to have the student learn about polynomial time vs. non-polynomial time algorithms and then try to implement the polynomial time primality testing algorthim (called the AKS primality test after the discovers).

Another route is to have them look into basic number-theoretic cryptography schemes (like RSA). Implementing them requires only a bit of modular arithmetic knowledge, which would be beneficial to learn anyway and shouldn't be too hard for this student.

I feel like I was once this student (though not quite that young) so I encourage and applaud your desire to continue to feed their fire!

Continuing with the prime theme there is a natural progression to prime polynomials. Then there's primitive polynomials.

• As a side-note: It is a nice exercise (or problem) to show that there cannot be a polynomial $f$ for which $f(\mathbb{N}) = \{$primes$\}$. – Benjamin Dickman Jan 31 '15 at 3:30

The Ulam Prime Spiral

and its variants leads to interesting questions to explore, e.g.,

I am sure there are many more along this vein that could be explored experimentally.