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

You are not logged in.

- Topics: Active | Unanswered

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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

**satish kumar singh****Guest**

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

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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

**satish kumar singh****Guest**

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

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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

**satish kumar singh****Guest**

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

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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

**satish kumar singh****Guest**

satish kumar singh wrote:

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

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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

**satish kumar singh****Guest**

bobbym wrote:

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

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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

**satish kumar singh****Guest**

bobbym wrote:

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

**danaj****Member**- Registered: 2014-03-03
- Posts: 29

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

**danaj****Member**- Registered: 2014-03-03
- Posts: 29

satish kumar singh wrote:

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).

satish kumar singh wrote:

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

**satish kumar singh****Guest**

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

**satish kumar singh****Guest**

satwnz wrote:

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

**danaj****Member**- Registered: 2014-03-03
- Posts: 29

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

**satish kumar singh****Guest**

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

**danaj****Member**- Registered: 2014-03-03
- Posts: 29

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

**satish kumar singh****Guest**

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

**satish kumar singh****Guest**

can be use it to find out prime number

satish kumar singh wrote:

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

**bobbym****bumpkin**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 108,752

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?

**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

**satish kumar singh****Guest**

bobbym wrote:

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

**danaj****Member**- Registered: 2014-03-03
- Posts: 29

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

**satish kumar singh****Guest**

danaj wrote:

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