You are not logged in.
About your question 111 111 111 111 111 is prime or not
I am not asking whether it is prime or not. I am asking to see your method applied to it.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
I can explan for just 281 is prime or not
1. find squre root of number near about it is 17
2 17*=Pn*=510510
3 Ip17 =number not divisible by 2,3,5,7,9,...17
510513
510515
510517
510521
510523
510527
510529
510533
510539
510541
510547
510551
510553
510557
510563
510569
510571
510577
510581
510583
510589
510593
510599
510607
510611
510613
510617
510619
510623
510637
510641
510647
510649
510659
510661
510667
510673
510677
510683
510689
510691
510701
510703
510707
510709
510721
510733
510737
510739
510743
510749
510751
510761
510767
510773
510779
510781
510787
510791
510793
510803
510817
510821
510823
510827
510841
510847
510857
510859
510863
510869
now
Ip17 Pn* prime= Ip17-Pn*
510513 510510 3
510515 510510 5
510517 510510 7
510521 510510 11
510523 510510 13
510527 510510 17
510529 510510 19
510533 510510 23
510539 510510 29
510541 510510 31
510547 510510 37
510551 510510 41
510553 510510 43
510557 510510 47
510563 510510 53
510569 510510 59
510571 510510 61
510577 510510 67
510581 510510 71
510583 510510 73
510589 510510 79
510593 510510 83
510599 510510 89
510607 510510 97
510611 510510 101
510613 510510 103
510617 510510 107
510619 510510 109
510623 510510 113
510637 510510 127
510641 510510 131
510647 510510 137
510649 510510 139
510659 510510 149
510661 510510 151
510667 510510 157
510673 510510 163
510677 510510 167
510683 510510 173
510689 510510 179
510691 510510 181
510701 510510 191
510703 510510 193
510707 510510 197
510709 510510 199
510721 510510 211
510733 510510 223
510737 510510 227
510739 510510 229
510743 510510 233
510749 510510 239
510751 510510 241
510761 510510 251
510767 510510 257
510773 510510 263
510779 510510 269
510781 510510 271
510787 510510 277
510791 510510 281
510793 510510 283
510803 510510 293
510817 510510 307
510821 510510 311
510823 510510 313
510827 510510 317
510841 510510 331
510847 510510 337
510857 510510 347
510859 510510 349
510863 510510 353
510869 510510 359
There are several things wrong with what I understand of your method.
1) It takes a lot of work to determine the primality of even a small number. Look at your post #27. Is it not much easier to just trial divide 281 by 2,3,5,7,11,13. Just 6 divisions is all that is necessary. Yours is huge and needs to work with numbers bigger then the number you are testing.
2) There is no way to do this for large numbers, which by the way is the main point of primality testing.
3) It is going to be slow. Slower than the slowest algorithm known, trial division.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Hi
Thanks for reply i know that...
1. I have given the way how one can find out each and every prime number in any range. Is it any way to find each nanevery prime number.
2. Both pn*, nad Ipn is will define so dont worry about time takin to find them.
3. I use to substract two big well define number to fin out each and every prime number.
Thanks
Satish kumnar singh
I have given the way how one can find out each and every prime number in any range.
That statement is a little premature. You and I do not know if that is true. It may be false for some number you have not tried.
Let's say it is true...
If it is slow and needs to use numbers bigger then the number you are testing why should anyone use it?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
it is true because i have tested it up to 15 digits.
secondly it is not process to test any number whether it is prime or composite number. Result always gives all prime number in fix range
ex i have given you
just i am giving the range
3*=6 gives all prime 3>=p<9
5*=30 gives all all prime 5>=p<=25
7*=210 gives all prime 7>=p<=49
11*=2310 gives all prime 11>=p<=121
.
.
.
.
Pn*=...gives all prime Pn*>=p<=(Pn)^2
so we can find out any prime number in any range.Only thing is that i have required more advance compute which is comfortable with large numbers.
if you want i will share you the excel sheet
Br
satish kumar singh
Hi;
I do not program in Excel. How about one example for a 15 digit number. Is it so long that it can not be shown?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
1. As in Ex you can see result, tragate is to find out prime number.
2. we use to substract Ipn-Pn*=Prime no ( Each and every prime number in fix range).So we may say it is a formula to find out prime number.
3. Pn* you know very well( product of prime number).
4. Ipn I have define above.( it is well define set of odd number)
About your question 111 111 111 111 111 is prime or not
first i will have to find out 10540923 ( product of all prime less then equl to 10540923) can be done
second Ipn i.e ( Ip10540923) set.
Result.. it will give all prime number form 10540923 to its squre.for ex as in above post
Drawback of formula......
Needed big numers to find out small prime number
refer #15
That is a very severe drawback. Also, you have an algorithm not a formula. There are many algorithms already to do that.
What exactly are you trying to do?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
That is a very severe drawback. Also, you have an algorithm not a formula. There are many algorithms already to do that.
What exactly are you trying to do?
Which one is fastest one and what are there limitation.
as, 1. For single number cheacking whether prime or not.
2. For all number cheacking whether prime or not.
3. we all know all prime number up to some limit why?
Br
satish
There is the AKS? algorithm for checking the primality of a number. With it you can check whether a 1000 digit number is prime in about an hour or so on a desktop.
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
There is the AKS? algorithm for checking the primality of a number. With it you can check whether a 1000 digit number is prime in about an hour or so on a desktop.
Can u explain it with simple example......
next ASK is limited to 1000 digits what about in 10^6 digits and latest records digits.
My Aim on records.
Br
Satish
This is rather complicated because some people are looking for answers of tiny numbers, e.g. under 10 thousand. Some for just small integers like 30608076202112141 (e.g. under 2^64). Others for 100-, 1000-, 10000-, 100000-digit numbers. Each of these has a different best strategy, not to mention numbers of a special form (e.g. Mersenne numbers). Apologies if this reply goes down too many ratholes.
Quick solution for most people, with numbers under 5000 or so digits:
- fire up Pari/GP. Type ispseudoprime(####). (#### is your number).
- for a proof, use isprime(###) instead. Until the number is hundreds of digits long you may as well do this.
For primality of general numbers, some options:
- Trial division. Works great for tiny numbers, like under 100k. Slows down very quickly. See Crandall and Pomerance section2 3.1.2 -
3.1.4 for discussion of testing odds vs. wheels vs. primes.
- Miller-Rabin with N random bases. Probable prime test, quite fast. For numbers under 2^64 there are deterministic sets that give correct results for all inputs. Simple to implement, works pretty well for most people, though as you care more about the correctness you find N gets quite large.
- BPSW test, about same speed as M-R with 3 bases. Probable prime test, no known counterexamples, the test used by almost all math
packages (sometimes they add an extra M-R test). There are verified *no* false results below 2^64.
- Proof: N-1/N+1. Generally using one of the theorems from the Brillhart-Lehmer-Selfridge 1975 paper. Requires factoring n-1 or n+1 so doesn't scale well, but it's quite fast for "small" numbers (e.g. under 40 digits, depending on your factoring code of course). Pretty simple to understand and implement theorem 5. Can produce a very simple and fast to verify certificate. Not really useful for numbers of 100+ digits. This was Pari's method 10 or so years ago.
- Proof: APR-CL. Name from the author's initials. Complicated to understand and implement. At least two open source versions available (Pari and mpz_aprcl). No certificate. Quite fast -- 100 digit proof in ~ 0.1 seconds, 1000 digits in under 10 minutes. Implementations typically limited to ~7000 digits (there are a lot of precalculated constants). Pari's current method.
- Proof: ECPP. Elliptic Curve Primality Proof. Complicated to understand and implement. Primo is closed source but free to use. There are at least two open source implementations. ECPP has been used to prove many numbers over 10,000 digits. Quite fast -- 100 digit proof in under 0.1 seconds, 1000 digits in under 10 minutes (Primo with multiple cores will go even faster). The big advantage is that you get a primality certificate that can be verified in a fraction of the time, using different code on a different computer if one wants. Hence,
unlike APR-CL and AKS, you're not just being told: "it's prime. trust me. what could go wrong?"
- Proof: AKS. A theoretical breakthrough. Sort of easy to implement (the algorithm from the v6 paper is surprisingly simple, but doing
modular polynomial multiplication correctly and quickly takes effort). Of no practical use because it's insanely slow -- numbers that APR-CL or ECPP prove in single seconds will take years with AKS.
- There are many other probable prime tests (e.g. various Lucas tests by themselves, PFGW's tests, Frobenius) and proofs (Cyclotomy).
My preferred method:
- If number less than threshold (e.g. 10k) do trial division by primes to sqrt(n). Result is correct.
- Test with some small primes to quickly weed out composites. I test to 53, most people test to less. With GMP and large numbers, I use a big GCD.
- If number less than 2^64, do deterministic M-R or BPSW. Result is correct.
- Do BPSW test. Pretty much every composite is now quickly weeded out.
There are no known counterexamples but we know some exist. If you don't absolutely need a proof, you're done. If you're doing crypto and don't want a proof, add a Frobenius test and/or some M-R tests using random bases. If the number passed BPSW and you want a proof, continue.
- If you have a good factoring library, do a quick attempt at BLS75 theorem 5. Unlikely to work with very large numbers, but with just a
little effort at Pollard-Rho and P-1, it can prove a surprisingly large percentage of 128-bit numbers in a few milliseconds. Worst case you
move on after spending a few milliseconds.
- ECPP. Send resulting certificate through verification if you're paranoid. You could use APR-CL instead.
There are some additional complications if one wants the fastest results at various sizes (e.g. with GMP and large numbers, a big GCD is fast so do small prime testing farther, and with multi-thousand digit numbers a tree sieve is nice). I find the extra strong Lucas test to be the best choice for BPSW's Lucas test, other software makes different choices. Speeding things up for native integers is fun (asm mulmods, Montgomery math, etc.).
Offline
3. we all know all prime number up to some limit why?
Just because we know the 17M digit numbers 2^57885161-1 is prime doesn't mean we have enumerated all the primes up to that point. Maybe I'm not understanding the question. Given numbers of certain forms (e.g. 2^p-1), we can prove their primality much faster than arbitrary numbers of similar size. For general numbers in the 15-22k digit range, it just takes a fast ~$1000US computer, a copy of Primo, and 3-5 months of letting it crunch. We're limited in that most people wouldn't want to wait that long just to get a proof for a number that we knew in a minute or two was almost certainly prime via probable prime tests.
Computers have been getting faster of course, but also gradual advances in fast multiprecision math software in the last few decades. For proofs, APR-CL and ECPP were enormous advances, though had no effect on the records for the largest proven primes, since they were all of special form. I don't follow the Mersenne prime searches so can't elaborate on advances (other than distributed searches, computer speed improvements, and faster math libraries).
next ASK is limited to 1000 digits what about in 10^6 digits and latest records digits.
My Aim on records.
For records, first look at something like the Prime Pages' Top Twenty and all their information about record primes.
Finding probable primes in a range is an interesting task to do quickly. The fastest way I know today for numbers in the 10^6 digit range is presieving then using OpenPFGW on the remaining set. This isn't going to set any records however.
For primality proofs, at 10^6 digits, I don't think general proofs like N-1, AKS, APR-CL, and ECPP will work. The only way those will work is back-construction of something using the proof (basically the same method Maurer's random provable prime technique uses), which means you've found a giant provable prime but you didn't really get to pick it. The largest proof using these methods is currently 26k digits using ECPP and took many months using custom software. The time taken grows approximately as the 4th power of the number of digits (but in practice it slows down at the extreme end).
Offline
for group testing i use optimized set of composite number ( Ipn set )......it is for 33% of natural number to..............tends to zero% of natural number.
so as we go for large number time get decrees for group testing.
Tends to zero% means Ipn for large value , it will give only prime number.
i would explain better buy pic, chat upload option is not here.
..........
If i got chance i can improve present testing process by concept of Ipn set of number.
............
Br
Satish
Ipn series Range of continues Prime No of Ipn sub series Common difference % of Ipn element w.r.t. + Ve integer
I2 2 ≤ P < 4 1 2 100%
I3 3 ≤ P < 9 1 2 50%
I5 5 ≤ P < 25 2 6 33.33%
I7 7 ≤ P < 49 8 30 22%
I11 11 ≤ P < 121 48 210 20%
I13 13 ≤ P < 169 480 2310 19%
I17 17 ≤ P < 289 5760 30030 18%
I19 19 ≤ P < 361 92160 510510 17%
.
.
.
.IpN................
Ex-I3 have one AP Serie and C.d = 2
3, 5, 7, 9, 11, 13------∞
i) Contain all rpimes and specific odd positive integer from 3 to infinite
ii) Continious prime 3≤P<9
ii) I3 Contain only 50.00% of positive integer
Ex-I5 have two AP Serie and C.d = 6
5 11 17 23 29 35 41 ------∞
7 13 19 25 31 37 43 -----∞
i) Contain all prime and specific odd positive integer from 5 to infinite
ii) Continuous prime 5≤P<25
ii) I5 Contains only 33.33% of positive integer
----------------------
This is concept Ipn series
This is a wheel sieve. See, for example, "Wheel factorization" on Wikipedia. There are some good papers by Pritchard, Quesada & van Pelt, and others. Crandall and Pomerance's book is available online if you don't have a copy, and Section 3.1.2 to 3.1.4 discusses some of this.
A lot of sieves use it to 30, as then one has 8 candidates per 30 numbers, which nicely packs into a byte, and you've got most of the gain. I believe primesieve uses it to 210. It starts getting unwieldy before long for very little additional gain. At some point, especially given caches, you're better off doing the extra small mod (or adding one more number to GCD if using bigints) than walking a giant table. Oh, another thing a lot of sieves do is a presieve of the range -- take the wheel-30 as an example, now make a constant memory chunk of size 7*11*13 (only 1001 bytes), and fill the sieve range with it appropriately rotated. Presto -- clearing the memory for the sieve just filled in all multiples of 7, 11, and 13 without any computation, so you can start sieving at 17.
Offline
Thanks i am very happy to see your reply...i will go though your suggestion...
what about large Ipn series is it known to every one.
like ( pn is prime number , is it known for 5digit prime number, 10 digit prime number......and n digit prime number.)
br
satish
510510 = 17# = primorial(17) = 2*3*5*7*11*13*17.
92160 = euler_phi(17#)
I think I'm with everyone else trying to figure out where Ipn is derived. The obvious way (I'm just making a guess) is that it is the primorial plus the previously generated primes with the single new prime sieved out. But that would make the primorial redundant. Then it reduces to "just use this sequence, which was made by sieving p (max p <= sqrt(n)) from the previous sequence. Which was made by sieving out prev_prime(p) from its previous sequence, etc."
I think Bobby's response to the earlier question does kind of get to the point. For the small 15 digit example you have to generate a 4.6 million digit primorial, then somehow come up with the sequence. Take a prime in the range of 2^512, which would be useful for an old RSA key. These take APR-CL 0.1 second to prove on a fast computer, or 200uS for BPSW (not proven, but it would be big news if it was composite since you'd be the first one to find a counterexample). For your method we would need to generate primorial(about 10^77) to get started. Ouch.
Taking a stab at your earlier question #2, which I will take as generating primes in a range, here are some ideas. If you just want something to run, look for primesieve. If you're looking for prime counts, there are fast algorithms that don't involve generating primes, so that's a different question.
1, either a very small range, or a very large base (e.g. well over 10^20). Pick one of:
a) Primality test with a good method that quickly throws out obvious composites.
b) Sieve to some convenient limit, then primality test the remainder.
2, the usual case. Use a segmented Sieve of Eratosthenes.
Notes:
- You may find reference to the Sieve of Atkin. If your SoA is faster than your SoE, I will bet you coded the SoE wrong. It's not as egregious as AKS, but it's another case where it sounds good in theory but it's not so hot in practice.
- there are a lot of ways to optimize the sieve internals. It's important to at least start with the correct 4-line SoE, but you can go crazy unrolling, presieving, cache-blocking, parallelizing, etc.
- especially in the large range, Oliveira e Silva's work on fast segmented sieves can be useful. I don't use it, but primesieve does and it is definitely better in some situations.
- For case 1b sieving, for example T.R. Nicely's prime gap verification program does this. Personally I just worked on making the primality test fast for weeding out composites, but partly because it made things simpler. As the range grows the sieving would be more and more advantageous. For cases like next/prev prime, the range is typically small and you're guessing at it, so it's more of a tossup.
- For bases over 3k digits there are some additional ideas.
Offline
please suggest about
Ipn set % OF NATURAL NUMBER Prime range
I15485807 0.031511447 Contain all prime number from 15485807 to infinite and only prime Betwn 15485807 to 15485807^2
I15485837 0.031511445 Contain all prime number from 15485837 to infinite and only prime Betwn 15485837 to 15485837^2
I15485843 0.031511443 Contain all prime number from 15485843 to infinite and only prime Betwn 15485843 to 15485843^2
I15485849 0.031511441 Contain all prime number from 15485849 to infinite and only prime Betwn 15485849 to 15485849^2
I15485857 0.031511439 Contain all prime number from 15485857 to infinite and only prime Betwn 15485857 to 15485857^2
I15485863 0.031511437 Contain all prime number from 15485863 to infinite and onlyl prime Betwn 15485863 to 15485863^2
Br
Satish
can be use it to find out prime number
please suggest about
Ipn set % OF NATURAL NUMBER Prime range
I15485807 0.031511447 Contain all prime number from 15485807 to infinite and only prime Betwn 15485807 to 15485807^2
I15485837 0.031511445 Contain all prime number from 15485837 to infinite and only prime Betwn 15485837 to 15485837^2
I15485843 0.031511443 Contain all prime number from 15485843 to infinite and only prime Betwn 15485843 to 15485843^2
I15485849 0.031511441 Contain all prime number from 15485849 to infinite and only prime Betwn 15485849 to 15485849^2
I15485857 0.031511439 Contain all prime number from 15485857 to infinite and only prime Betwn 15485857 to 15485857^2
I15485863 0.031511437 Contain all prime number from 15485863 to infinite and onlyl prime Betwn 15485863 to 15485863^2Br
Satish
Hi satish kumar singh;
You are ignoring what is being said to you.
This is a forum, here people converse and reply to each other. This was said to you:
For the small 15 digit example you have to generate a 4.6 million digit primorial, then somehow come up with the sequence.
Do you agree?
In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.
Offline
Hi satish kumar singh;
You are ignoring what is being said to you.
This is a forum, here people converse and reply to each other. This was said to you:
danaj wrote:For the small 15 digit example you have to generate a 4.6 million digit primorial, then somehow come up with the sequence.
Do you agree?
................
No this is main point i have no need to go with primorial, As
Ipn set is well defined.
Can be genrated for any range.
Br
Satish
In the example for "is 281 prime" you did:
1. find squre root of number near about it is 17
2 17*=Pn*=510510
3 Ip17 =number not divisible by 2,3,5,7,9,...17
then: prime= Ip17-Pn* where IP17 started at 510513, and Pn* was 510510.
For the example "111,111,111,111,111" (decimal), I get a square root of 10540925. Step 2 as well as the prime generation says to use Pn*=10530925#. That came out to 4,576,061 digits for me. The number in "No of Ipn sub series" is going to be similarly titanic. What is different about this example from the 281 example?
You have to either store these or calculate them, and either way I don't see how you can say "don't worry about time [...] to find them." Why not just precalculate the primes directly if we get to discount the time and/or space?
Offline
In the example for "is 281 prime" you did:
1. find squre root of number near about it is 17
2 17*=Pn*=510510
3 Ip17 =number not divisible by 2,3,5,7,9,...17then: prime= Ip17-Pn* where IP17 started at 510513, and Pn* was 510510.
For the example "111,111,111,111,111" (decimal), I get a square root of 10540925. Step 2 as well as the prime generation says to use Pn*=10530925#. That came out to 4,576,061 digits for me. The number in "No of Ipn sub series" is going to be similarly titanic. What is different about this example from the 281 example?
You have to either store these or calculate them, and either way I don't see how you can say "don't worry about time [...] to find them." Why not just precalculate the primes directly if we get to discount the time and/or space?
then: prime= Ip17-Pn* where IP17 started at 510513, and Pn* was 510510.
Just for General way
For the example "111,111,111,111,111" (decimal), I get a square root of 10540925. Step 2 as well as the prime generation says to use Pn*=10530925#. That came out to 4,576,061 digits for me. The number in "No of Ipn sub series" is going to be similarly titanic. What is different about this example from the 281 example?
hi
First of all I would like to clear for two type of test of prime number
1- Finding for any single prime number( it is not testing ).
( Prime number = Ipn element-Pn*(only values i.e multiplication) )
Ex-
510751(Ipn) - 510510 (P17) = 241 ( prime )
467 (Ipn) - 450 (P5) = 17 ( prime )
469 (Ipn) - 450 (P5) = 19 ( prime )
2- Second group testing.( I use Ipn Set it is well defined itself and in A.P ). So can be operate very easily. Second Ipn set tends to zero% in compression of natural number in fact it will give only prime number in higher range of prime table)
Ex. I33,5,7,9,11,---infine
Ex I5----5,11,17,23
.. infine
7,13,19,25
. Infine
In general Go to post#15
You have to either store these or calculate them, and either way I don't see how you can say "don't worry about time [...] to find them." Why not just precalculate the primes directly if we get to discount the time and/or space?
Thanks