pattern in prime numbers?

[MRC_Hans]

Really, the algorithm that gives the best understanding of primes, and the patterns in them is the sieve algorithm.

Since primes are not divisible by anything but 1 and themselves, if follows that if you take each prime and "sive" out all numbers that can be divided by it, you'll end up with all the primes.

So, lets for simplicity look at the numbers up to 20:

1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17-18-19-20

1 is a special case, so we skip that and take the next special case, 2. All numbers divisible by 2 go out:

1-2-3--5--7--9--11--13--15--17--19-

Ok, the next prime is 3, knock out all numbers divisible by 3 (except, of course 3):

1-2-3--5--7--11--13--17--19-

If the row of numbers was longer we could go on. but no more is needed now. All we need is test up to the square root of the larget number tested.

This also shows you why there will always be primes, no matter how high you go: The sieve gets ever more coarse.

Hans

 

[ceptimus]

31, 331, 3331, 33331, 333331 and 3333331 are all primes. I leave the primality testing of 33333331 etc. as an exercise for the interested reader

 

[xouper]

ceptimus: 31, 331, 3331, 33331, 333331 and 3333331 are all primes. I leave the primality testing of 33333331 etc. as an exercise for the interested reader

Not prime. 33333331 = 17 * 19607843

How about the following number (one hundred 3s followed by a 1)? Is it prime?

33333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333331


<table cellpadding="4" cellspacing="1" border="0" bgcolor="#666699" align="center" width="80%"><tr><td bgcolor="#666699"><font size="1" face="Arial, Helvetica, sans-serif" color="#FFFFFF">Spoiler:</font></td></tr><tr><td bgcolor="white"><font size="2" face="Arial, Helvetica, sans-serif" color="white">
Yes, (10¹⁰¹-7)/3 is prime.

Here's a list:
http://homepage2.nifty.com/m_kamada/math/33331.htm

</font></td></tr></table>

 

[ceptimus]

Not prime. 33333331 = 17 * 19607843

Oops! Not correct I'm afraid xouper! 33333331 is prime. The factors you give are for the next example (with 8 threes before the one).

 

[xouper]

ceptimus: Oops! Not correct I'm afraid xouper! 33333331 is prime. The factors you give are for the next example (with 8 threes before the one).

Oops is right.

That'll teach me to be hasty, eh?

I had double checked the answer with a calculator, twice, but apparently I can't count simple things like how many threes there are.

 

[LW]

A fun thing with primes is that if someone is demonstrating some algorithm or formula or whatever about primes and asks the audience to name a smallish prime, then shout 91.