Feeds:
Posts
Comments

Posts Tagged ‘what are the prime numbers’

As a species what sets us apart from the from our nearest neighbours who still prefer to swing from the branches is the ability to categorize and classify everything we see around us.  Trying to stake a claim on posterity is a very human thing to do. We love to leave a mark. Something that will remain when we have gone back to the dust.  We may have at sometime in our lives been impressed by a shelf full of the many volumes that comprise the Encyclopedia Britannica or the chunky tombs like Wisden Cricketing almanac which have all the stats and scores of those great games in the past. For those wishing to record what we have achieved in the world of numeric sequences we have to rely on the OEIS … the online encyclopedia of integer sequences.  This ‘encyclopedia’ was something started by a guy called Neil Sloane almost 40 years ago. Well not the on-line bit but the integer sequences bit. Like all good ideas at the time it is something that’s outgrown its humble roots and taken on a life of its own.

Here’s how it works.

You dream up a sequence  of integers that are related in some way .. which may only be tenuous … or it may be some thing that springs from a well defined formula .. like y=x^2 .. and you create a list of results and you can put the results in the OEIS … then someone else comes along and if they think they’d like to put the sequence in too they can type the first few digits in to see if someone else has already thought of it … Having just re-read that last paragraph .. it all sounds a tad dull. But if you’re a prime nut then it’s the dog’s whatsits.
Sequences in the OEIS start with the letter A .. for example A000040 is a list of prime numbers. This page dedicated to this sequence links to loads of other sequences and gives all the learned papers on prime numbers as reference … a veritable vade mecum  of all things integer.

So the reason for mentioning this is because on Saturday  .. I entered a sequence that got ‘accepted’ by the editors of the site. They tweaked about with it but in essence they let it be. It came about by playing with Excel and generating several thousand results for a very famous prime generating polynomial.  x^2  + x + 41. This is one of the most prolific prime generators. The first 40 values of X for example are all prime!! Okay those who have little interest in primes may be non-plused but believe me .. that’s a corker of a formula. Anything that can tip-toe through the integers in a well defined way and reach 1681 before it comes across its first composite number is doing very very well.

Here’s what I noticed. When you get to 41^2 where the  prime sequence starts to fall apart and your lovely stream of contiguous primes comes to an end .. something very interesting happens to the semiprimes.   A semi-prime is just two primes multiplied together.  Euler who first published this polynomial was more than aware it couldn’t continue to generate primes past 41.  What I did was to embrace this fact and start to look at how the semi-primes where made up.  I started this work about 3 months ago now as it takes quite a while factorizing numbers to see if they’re prime or not. If numbers get very large then I would suggest you go to Alpertron’s ECM site as that will take the grunt out of doing it.

I noticed that the factors themselves started sequences that appeared regularly through the results …

Let me give you an example so as to explain myself a little better.

37 1447 1447
38 1523 1523
39 1601 1601
40 1681 41 41
41 1763 41 43
42 1847 1847
43 1933 1933
44 2021 43 47
45 2111 2111
46 2203 2203
47 2297 2297
48 2393 2393
49 2491 47 53
50 2591 2591
51 2693 2693
52 2797 2797
53 2903 2903
54 3011 3011
55 3121 3121
56 3233 53 61
57 3347 3347
58 3463 3463
59 3581 3581
60 3701 3701
61 3823 3823
62 3947 3947
63 4073 4073
64 4201 4201
65 4331 61 71

The leftmost column is the value of X in the equation x^2+x+41. So, for example,  if you take the value 60 you get (60*60) + 60 + 41 = 3701 .. which just happens to be prime.

But now look at the result when X = 41 .. here the result is 1763 .. which isn’t a prime number but is a number with two factors i.e. 41 and 43. This is because 41 * 43  = 1763.

Look down columns 3 and 4 and you get all the factors (41*41), (41*43),(43*47),(47*53)(53*61)….. ( I can feel a ‘so what’ moment coming on .. 🙂 )

Well these factors are the start of the sequence for x^2+x+41  when x = 1 . (See below)

1 43 43
2 47 47
3 53 53
4 61 61
5 71 71
6 83 83
7 97 97
8 113 113
9 131 131
10 151 151
11 173 173
12 197 197
13 223 223
14 251 251
15 281 281
16 313 313
17 347 347
18 383 383
19 421 421
20 461 461
21 503 503
22 547 547
23 593 593
24 641 641
25 691 691
26 743 743
27 797 797
28 853 853

The other thing to note is that the semi-primes appear at a very regular intervals .. 2,4,6,8,10……

Once x gets to 2 x 41 (remember the 41 was added on  ( x^2+x+41) .. another sequence starts …

81 6683 41 163
82 6847 41 167
83 7013 7013
84 7181 43 167
85 7351 7351
86 7523 7523
87 7697 43 179
88 7873 7873
89 8051 83 97
90 8231 8231
91 8413 47 179
92 8597 8597
93 8783 8783
94 8971 8971
95 9161 9161
96 9353 47 199
97 9547 9547
98 9743 9743
99 9941 9941
100 10141 10141
101 10343 10343
102 10547 53 199
103 10753 10753
104 10961 97 113
105 11171 11171
106 11383 11383
107 11597 11597
108 11813 11813
109 12031 53 227
110 12251 12251
111 12473 12473
112 12697 12697

This time the factors are made up of those that appeared in the values of x between 1 and 40 and new values that do not occur in the sequence. These can be seen to be 163,167, 179,199 ,227 … and they appear regularly spaced too.

You can try this for yourself at home .. (as they say) and you will note every time X increases by 41 another sequence springs up. I have worked out a formula for the sequence starts and their gaps.
While in the lake district this year I got up early most mornings to work on a general formula for all these sequences and come up with this  ..

(n^2*x^2) +/- ((n^2-2n)*x) + (n^2*k – (n-1)) ………………. (k = to 41)

The table below shows how each sequence follows the above formula:

n x k (n^2*x^2)+((n^2-2n)*x)+(n^2*k-(n-1)
1 0 41 41
1 1 41 43
1 2 41 47
1 3 41 53
2 0 41 163
2 1 41 167
2 2 41 179
2 3 41 199
3 0 41 367
3 1 41 373
3 2 41 397
3 3 41 439
4 0 41 653
4 1 41 661
4 2 41 701
4 3 41 773
5 0 41 1021
5 1 41 1031
5 2 41 1091
5 3 41 1201

I decided to publish this formula against one specific set of results in the OEIS .. It was allocated A214732. and is when n=5 so the generic formula becomes  …. 25x^2 + 15x+1021. It produces around 16 contiguous primes starting at x=0 –> x=16.

So based on the theory that the OEIS will be around long after I’ve shuffled off this mortal coil … this along with the primorial conjecture .. is my bold claim on posterity … ya what I hear you say … get a life ….. 🙂

Advertisements

Read Full Post »