Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2020-05-11 16:51:54

Knewlogik
Guest

All primes formula

Okay I'll check the number 7 and the number 11 and when adding 6 to these numbers it will give you all primes after but the downfall here and there you left a few oddball numbers in between how do I figure out a way to pull the oddball numbers out are what formula would tell me how to obtain the oddball numbers but yet leave the prime ones so I can determine why those oddball numbers are there

#2 2020-05-11 21:02:13

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,829

Re: All primes formula

hi Knewlogik

Welcome to the forum.  you've made two similar posts so I'll try to deal with both here.

If you start with 7 and keep adding 6 you get:

7,   13,   19,   25,   31,   37,   …..

Starting with 11 gives:

11,   17,   23,   29,   35,   41,   …..

Will you ever get the same number in both lists?  No; it'll never happen.

Because the two lists start 4 apart and both go up at the same rate, they never share a value.

Do you know about straight line graphs?  If not look here:

https://www.mathsisfun.com/equation_of_line.html

The first sequence has equation y = 7 +6x.  The second is y = 11 + 6x

These two lines have the same gradient (6) so they are parallel.  So they never cross.

For many, many years mathematicians have tried to find a formula for generating primes.  There are a few that give some primes, and many that look like they are working but then fail, but nobody has yet come up with a formula for all primes.  I suspect it doesn't exist but I don't think there is a proof that no such formula exists.

Best wishes, keep safe,

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob Bundy smile

Offline

#3 2020-05-11 22:50:10

Knewlogik
Member
Registered: 2020-05-11
Posts: 4

Re: All primes formula

bob bundy wrote:

hi Knewlogik

Welcome to the forum.  you've made two similar posts so I'll try to deal with both here.

If you start with 7 and keep adding 6 you get:

7,   13,   19,   25,   31,   37,   …..

Starting with 11 gives:

11,   17,   23,   29,   35,   41,   …..

Will you ever get the same number in both lists?  No; it'll never happen.

Because the two lists start 4 apart and both go up at the same rate, they never share a value.

Do you know about straight line graphs?  If not look here:

https://www.mathsisfun.com/equation_of_line.html

The first sequence has equation y = 7 +6x.  The second is y = 11 + 6x

These two lines have the same gradient (6) so they are parallel.  So they never cross.

For many, many years mathematicians have tried to find a formula for generating primes.  There are a few that give some primes, and many that look like they are working but then fail, but nobody has yet come up with a formula for all primes.  I suspect it doesn't exist but I don't think there is a proof that no such formula exists.

Best wishes, keep safe,

Bob


1,2,3,4,5,6
7,8,9,10,11,12
13,14,15,16,17,18... Now pretend that this is an infinite row that continues downward but instead of stopping at the tent position we're stopping at the sixth position and starting over Seven second line but would normally be the 10th position is now the 7th position and while adding 6 to the 7th line and where the position 7,11 is lying you will forever have all primes with some extras correct ex 07,13,19,25,31,37...       11,17,23,29,35,41,47... Does that make more sense now if you have graph paper you have all those numbers inside of each box with what he leaves you with is a straight line down both 11 and 7 throw with all primes including a couple extras how do I do window out the non primes

Offline

#4 2020-05-12 00:12:50

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,829

Re: All primes formula

hi Knewlogik

I've used a spreadsheet to create a large set of data.

If I label the columns by the first number, ie. 1 2 3 4 5 and 6, then the 2, 4, and 6 columns are always even and so  will never produce primes.  Similarly the 3 column always gives numbers that are divisible by 3, so will not be primes.

So the 1 and 5 columns are the ones to look at and that's the ones you are talking about … good so far.

Looking at the 1 column, we have

1,  7,  13,  19,  25,  31,  37,  43,  …….

From 7 onward we do appear to be getting a lot of primes, but also some that are not, such as 25.  You want to know if these can be easily removed from the list.

Well numbers that are divisible by 5 do keep appearing: 25,  55,  115,  145,  and so on.  We could remove these by testing for divisibility by 5.  Notice that they occur regularly down the column.

But there are also some that are divisible by 7:  49,  91,  133,    175, and so on.  Once again these occur at regular intervals.

Once again we could eliminate these by checking for divisibility by 7.

But there are also some that are divisible by 11: 55,  121,  187 and so on.  Again at regular intervals.

Will this ever stop happening?  Sorry but no.  There are numbers in the column that are divisible by 13, 17, 19, 23 and so on.  In fact every prime will eventually be a divisor for some number in the column, 

I have a way of proving this but it involves some more advanced mathematics.  I'll try to explain it if you would like.

And the same is true for the 5 column.

Thus there is no easy way to remove the unwanted non primes.  Sorry.

Look up the Sieve of Eratosthenes and you'll see that what you have devised is very similar.  It works, but you have to keep eliminating numbers by removing those that are divisible by a known prime.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob Bundy smile

Offline

#5 2020-05-12 11:36:44

Knewlogik
Member
Registered: 2020-05-11
Posts: 4

Re: All primes formula

What is the first prime it misses?

Offline

#6 2020-05-12 19:36:33

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,829

Re: All primes formula

hi Knewlogik

169 won't be removed by dividing by 5, 7 and 11.  That led me to a general result:

Consider the number p^2 where p is any prime > 3.

This number is not a prime as it has more than 2 factors {1, p, p^2}.

It's odd so it won't be in columns 2, 4, or 6.

It isn't divisible by 3 so it's not in column 3.

Therefore it is in column 1 or 5.

Even if you have removed all non primes with prime factors, each of which is less than p, the number p^2 won't have need detected yet.

So, there is no highest prime that can be used to check division and remove all non primes.

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob Bundy smile

Offline

#7 2020-05-19 15:09:20

Knewlogik
Member
Registered: 2020-05-11
Posts: 4

Re: All primes formula

Wouldn't it just be easier to eliminate any number that didn't end with 1,3,7,0r 9?? Then do you lr division thing

Offline

#8 2020-05-19 20:59:57

bob bundy
Administrator
Registered: 2010-06-20
Posts: 8,829

Re: All primes formula

hi Knewlogik

It was your method.  I'm just commenting on it.  As far as I know, there is no simple way to generate all primes from an algorithm other than the following:

(1) Start the primes list with {2}

(2) Consider the next candidate.  This can be 3 initially and then every odd number thereafter.

(3) Test whether any of the numbers in the primes list divide into the number under test.

(4) If they do continue to the next candidate number and repeat step 3.

(5) If not, then the number is also a prime and should be added to the primes list.

You can short cut slightly by eliminating any candidate number that ends in 5.

You can also cutdown on the number of divisions by using the fact that if f is a factor of N below square root(N) then  N/f is another factor that is above the square root.  Thus if you haven't found a factor by the time you reach square root(N) you can safely stop looking.

The Sieve of Eratosthenes involves eliminating non primes by going through a table of numbers crossing out every number divisible by each prime except that number and looking at what remains.  When I taught this I used a grid with 1 - 10 on the top row, then 11 - 20, then 21 - 30 and so on.  This makes it easier to cross out certain candidates such as the whole of the 15, 25, 35 … column.  Factors of three make a satisfying diagonal pattern etc.

But it doesn't provide a way to get all the primes, as you have to keep extending the grid and testing for division by larger and larger primes.

I think your idea amounts to the same thing; just a different grid shape; which helps to cut out more non primes more quickly. Unfortunately the issue of 'when can I stop crossing out non primes' still arises, as with Eratosthenes. The answer is never!

Bob


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob Bundy smile

Offline

Board footer

Powered by FluxBB