Mixing
Does c#k + i actually generate all primes above c# (plus some composites)?
Clash Royale CLAN TAG#URR8PPP
up vote
0
down vote
favorite
The Wikipedia page for "Primality test", linked below [1], states that "all primes are of the form c#k + i for i < c# where c and k are integers, c# represents c primorial, and i represents the numbers that are coprime to c#."
I understand this to mean the following:
- Pick a particular value for c, for example set c=11.
- Compute the primorial of c, c#=2*3*5*7*11=2310.
- The values that i can take on for this choice of c are: 1, 13, 17, ..., 2309. (The values 2, 3, 5, 7, and 11 are omitted due to being primes less than 11, and the list of possible i values ends at the largest prime smaller than c#=2310 or in this case 2309.)
- For this c# every possible prime number above c#=2310, can be produced for some value k (any integer) and a particular value of i.
- Note, I understand that the series will ALSO generate composite numbers, but my understanding is that it will be guaranteed to generate every prime above c#.
I tried to test this. Specifically, I checked to see if [(2^13)-1]=8191 (which is a prime number, specifically a Mersenne prime) can be generated by the sequence of numbers for c=11, c#=2310.
- To find the appropriate value for k I computed [(2^13)-1]/(2310)=3.54... Thus I selected k=3 since the values of i are less than c#, and if k were any other value there would be no chance of reaching the number in question (8191).
- Then I did [(2^13)-1]-3*2310=1261. And looked to see if 1261 is a possible value that i can take on. However, 1261 is not prime, so i can not equal 1261.
- Thus I concluded that the series of numbers generated by c#k + i can not possibly equal [(2^13)-1] for the series generated by c=11.
So it would seem to me that the claim made in the Wikipedia page for Primality Tests that all prime numbers above c# can be generated by the series c#k+i is false. Am I misunderstanding the original claim? Or have a applied it incorrectly and make a mistake in the calculations? Any clarification regarding series of this form that generate all primes (plus some composites) would be greatly appreciated. (Is there a name for series of this type that I could use to search for more information?)
[1] Wikipedia page for "Primality test"
https://en.wikipedia.org/wiki/Primality_test
primality-test primorial
asked Jul 25 at 21:51
user669487
662
add a comment |Â
up vote
0
down vote
favorite
The Wikipedia page for "Primality test", linked below [1], states that "all primes are of the form c#k + i for i < c# where c and k are integers, c# represents c primorial, and i represents the numbers that are coprime to c#."
I understand this to mean the following:
- Pick a particular value for c, for example set c=11.
- Compute the primorial of c, c#=2*3*5*7*11=2310.
- The values that i can take on for this choice of c are: 1, 13, 17, ..., 2309. (The values 2, 3, 5, 7, and 11 are omitted due to being primes less than 11, and the list of possible i values ends at the largest prime smaller than c#=2310 or in this case 2309.)
- For this c# every possible prime number above c#=2310, can be produced for some value k (any integer) and a particular value of i.
- Note, I understand that the series will ALSO generate composite numbers, but my understanding is that it will be guaranteed to generate every prime above c#.
I tried to test this. Specifically, I checked to see if [(2^13)-1]=8191 (which is a prime number, specifically a Mersenne prime) can be generated by the sequence of numbers for c=11, c#=2310.
- To find the appropriate value for k I computed [(2^13)-1]/(2310)=3.54... Thus I selected k=3 since the values of i are less than c#, and if k were any other value there would be no chance of reaching the number in question (8191).
- Then I did [(2^13)-1]-3*2310=1261. And looked to see if 1261 is a possible value that i can take on. However, 1261 is not prime, so i can not equal 1261.
- Thus I concluded that the series of numbers generated by c#k + i can not possibly equal [(2^13)-1] for the series generated by c=11.
So it would seem to me that the claim made in the Wikipedia page for Primality Tests that all prime numbers above c# can be generated by the series c#k+i is false. Am I misunderstanding the original claim? Or have a applied it incorrectly and make a mistake in the calculations? Any clarification regarding series of this form that generate all primes (plus some composites) would be greatly appreciated. (Is there a name for series of this type that I could use to search for more information?)
[1] Wikipedia page for "Primality test"
https://en.wikipedia.org/wiki/Primality_test
primality-test primorial
asked Jul 25 at 21:51
user669487
662
1
It says coprime to $c#$. Since $1261 = 13cdot 97$, it is coprime to $11#$.
– Daniel Fischer♦
Jul 25 at 21:54
@DanielFischer Thank you. I see now I have somehow misunderstood the original claim. The value 1261 is "coprime" with c# as it shares no common prime factors (2,3,5,7,11). This is many more possible values than I listed for i, or understood that i could take on.
– user669487
Jul 25 at 22:07
add a comment |Â
up vote
0
down vote
favorite
up vote
0
down vote
favorite
The Wikipedia page for "Primality test", linked below [1], states that "all primes are of the form c#k + i for i < c# where c and k are integers, c# represents c primorial, and i represents the numbers that are coprime to c#."
I understand this to mean the following:
- Pick a particular value for c, for example set c=11.
- Compute the primorial of c, c#=2*3*5*7*11=2310.
- The values that i can take on for this choice of c are: 1, 13, 17, ..., 2309. (The values 2, 3, 5, 7, and 11 are omitted due to being primes less than 11, and the list of possible i values ends at the largest prime smaller than c#=2310 or in this case 2309.)
- For this c# every possible prime number above c#=2310, can be produced for some value k (any integer) and a particular value of i.
- Note, I understand that the series will ALSO generate composite numbers, but my understanding is that it will be guaranteed to generate every prime above c#.
I tried to test this. Specifically, I checked to see if [(2^13)-1]=8191 (which is a prime number, specifically a Mersenne prime) can be generated by the sequence of numbers for c=11, c#=2310.
- To find the appropriate value for k I computed [(2^13)-1]/(2310)=3.54... Thus I selected k=3 since the values of i are less than c#, and if k were any other value there would be no chance of reaching the number in question (8191).
- Then I did [(2^13)-1]-3*2310=1261. And looked to see if 1261 is a possible value that i can take on. However, 1261 is not prime, so i can not equal 1261.
- Thus I concluded that the series of numbers generated by c#k + i can not possibly equal [(2^13)-1] for the series generated by c=11.
So it would seem to me that the claim made in the Wikipedia page for Primality Tests that all prime numbers above c# can be generated by the series c#k+i is false. Am I misunderstanding the original claim? Or have a applied it incorrectly and make a mistake in the calculations? Any clarification regarding series of this form that generate all primes (plus some composites) would be greatly appreciated. (Is there a name for series of this type that I could use to search for more information?)
[1] Wikipedia page for "Primality test"
https://en.wikipedia.org/wiki/Primality_test
primality-test primorial
asked Jul 25 at 21:51
user669487
662
The Wikipedia page for "Primality test", linked below [1], states that "all primes are of the form c#k + i for i < c# where c and k are integers, c# represents c primorial, and i represents the numbers that are coprime to c#."
I understand this to mean the following:
- Pick a particular value for c, for example set c=11.
- Compute the primorial of c, c#=2*3*5*7*11=2310.
- The values that i can take on for this choice of c are: 1, 13, 17, ..., 2309. (The values 2, 3, 5, 7, and 11 are omitted due to being primes less than 11, and the list of possible i values ends at the largest prime smaller than c#=2310 or in this case 2309.)
- For this c# every possible prime number above c#=2310, can be produced for some value k (any integer) and a particular value of i.
- Note, I understand that the series will ALSO generate composite numbers, but my understanding is that it will be guaranteed to generate every prime above c#.
I tried to test this. Specifically, I checked to see if [(2^13)-1]=8191 (which is a prime number, specifically a Mersenne prime) can be generated by the sequence of numbers for c=11, c#=2310.
- To find the appropriate value for k I computed [(2^13)-1]/(2310)=3.54... Thus I selected k=3 since the values of i are less than c#, and if k were any other value there would be no chance of reaching the number in question (8191).
- Then I did [(2^13)-1]-3*2310=1261. And looked to see if 1261 is a possible value that i can take on. However, 1261 is not prime, so i can not equal 1261.
- Thus I concluded that the series of numbers generated by c#k + i can not possibly equal [(2^13)-1] for the series generated by c=11.
So it would seem to me that the claim made in the Wikipedia page for Primality Tests that all prime numbers above c# can be generated by the series c#k+i is false. Am I misunderstanding the original claim? Or have a applied it incorrectly and make a mistake in the calculations? Any clarification regarding series of this form that generate all primes (plus some composites) would be greatly appreciated. (Is there a name for series of this type that I could use to search for more information?)
[1] Wikipedia page for "Primality test"
https://en.wikipedia.org/wiki/Primality_test
primality-test primorial
asked Jul 25 at 21:51
user669487
662
edited Jul 25 at 21:58
asked Jul 25 at 21:51
user669487
662
asked Jul 25 at 21:51
user669487
662
asked Jul 25 at 21:51
user669487
662
662
1
It says coprime to $c#$. Since $1261 = 13cdot 97$, it is coprime to $11#$.
– Daniel Fischer♦
Jul 25 at 21:54
@DanielFischer Thank you. I see now I have somehow misunderstood the original claim. The value 1261 is "coprime" with c# as it shares no common prime factors (2,3,5,7,11). This is many more possible values than I listed for i, or understood that i could take on.
– user669487
Jul 25 at 22:07
add a comment |Â
1
It says coprime to $c#$. Since $1261 = 13cdot 97$, it is coprime to $11#$.
– Daniel Fischer♦
Jul 25 at 21:54
@DanielFischer Thank you. I see now I have somehow misunderstood the original claim. The value 1261 is "coprime" with c# as it shares no common prime factors (2,3,5,7,11). This is many more possible values than I listed for i, or understood that i could take on.
– user669487
Jul 25 at 22:07
1
1
It says coprime to $c#$. Since $1261 = 13cdot 97$, it is coprime to $11#$.
– Daniel Fischer♦
Jul 25 at 21:54
It says coprime to $c#$. Since $1261 = 13cdot 97$, it is coprime to $11#$.
– Daniel Fischer♦
Jul 25 at 21:54
@DanielFischer Thank you. I see now I have somehow misunderstood the original claim. The value 1261 is "coprime" with c# as it shares no common prime factors (2,3,5,7,11). This is many more possible values than I listed for i, or understood that i could take on.
– user669487
Jul 25 at 22:07
@DanielFischer Thank you. I see now I have somehow misunderstood the original claim. The value 1261 is "coprime" with c# as it shares no common prime factors (2,3,5,7,11). This is many more possible values than I listed for i, or understood that i could take on.
– user669487
Jul 25 at 22:07
add a comment |Â
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862857%2fdoes-ck-i-actually-generate-all-primes-above-c-plus-some-composites%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
It says coprime to $c#$. Since $1261 = 13cdot 97$, it is coprime to $11#$.
– Daniel Fischer♦
Jul 25 at 21:54
@DanielFischer Thank you. I see now I have somehow misunderstood the original claim. The value 1261 is "coprime" with c# as it shares no common prime factors (2,3,5,7,11). This is many more possible values than I listed for i, or understood that i could take on.
– user669487
Jul 25 at 22:07