20200329, 19:19  #1 
Dec 2011
After milion nines:)
10100000101_{2} Posts 
Prime numbers with P1 properties ( or smooth primes)
Is it possible to write program that will produce primes that have P1smooth properties ?

20200329, 19:32  #2  
"Rashid Naimi"
Oct 2015
Out of my Body
17·107 Posts 
Quote:
It is very easy to write programs that will produce integers that are N1 smooth and then check to see if they are prime. Are you asking for algorithms to produce guaranteed primes? Highly probable primes? 

20200329, 21:47  #3  
Dec 2011
After milion nines:)
5×257 Posts 
Quote:
Yes I ask something that I can run so algo produce and give me some primes with properties Last fiddled with by pepi37 on 20200329 at 21:49 

20200329, 23:19  #4 
"Rashid Naimi"
Oct 2015
Out of my Body
17×107 Posts 
I wasn't referring to PRP's. A PRP that is P1 smooth can easily be proven prime (if it is indeed prime). A multiple of (small) primes + 1 is more likely/probable to be prime if it is not much larger than the largest factor of P1. On the other hand if it is much greater than it then the probability of it being prime decreases the larger it gets. If there was a generally known algo that would produce guaranteed large primes then this site world have closed shop long ago.
Last fiddled with by a1call on 20200329 at 23:26 
20200329, 23:30  #5 
Dec 2011
After milion nines:)
2405_{8} Posts 

20200330, 00:02  #6 
"Curtis"
Feb 2005
Riverside, CA
11×383 Posts 
a1call is trying to point out (I think?) that it's much easier to construct smooth numbers and then test them for primality than it is to construct prime numbers and then test them for smoothness.
How many primality tests you'll need to find a smooth prime depends in large part on how big you want these things to be... but the "N+1" test will be a proof of primality, and doesn't take much longer than prp. 
20200330, 00:40  #7 
Dec 2011
After milion nines:)
5·257 Posts 
So to clarify my idea. Prime 95 can do P1. And those method can find fairly large factors. Of course it doesnot find all factors like "standard" sieve but find something that regular sieve will never find because we all do sieve well below .
So I would like ( that is idea and I dont know how to make it) to use P1 primes for making sieve. For example 641146783318960453  93*10^10393321 3060840294625372969  5*10^10377261 1778461772711066380507  6*10^10385141 If it is complicated to make this program I would like some kind of generator of "smooth" primes. It is easy to enter it in script and run PFGW: he will be check divisibility and if factor is found will get zero as result. :) So that tool can remove some extra factors before we start processing. Just is problem how to generate those primes with such properties Last fiddled with by pepi37 on 20200330 at 00:47 Reason: add more info 
20200330, 02:14  #8 
"Curtis"
Feb 2005
Riverside, CA
11×383 Posts 
It seems like you want to do P1 testing on a list of candidates that survived a sieve, but you've set up a rather convoluted way to try to set that up.
Could you maybe try again to explain what your "sieve" would do, or why it would be more effective than either regular P1 testing or more regular sieving? 
20200330, 10:25  #9  
Dec 2011
After milion nines:)
5×257 Posts 
Quote:
As I stated before 1. I know this is not "perfect sieve " and will not eliminate all but only limited number of candidates. 2. I dont know it is better or not from regular sieve process. 3. I start from position that regular sieve from standard user will never reach factors depth as can reach from P1 method 4. I just reversed process : I try to take smooth primes and use them as platform for dividing candidates 5, Maybe it is totally insane idea, but unless I generate lets say 1000 5000 those primes ( and try) I will never know is it or is it not. So I ask once more, if someone here can write script or program that I can execute and will give me primes with those properties please help. Maybe my English is not good to all of you and when I try to explain WHY I needed, and when I start to explain you ALWAYS think I am rude ,ungrateful and refuse to help me. So if you can: help me, if not, forget about idea, I will try it to calculate at home how I know ( it will be hardest way , but in those days when we are all in quarantine there is time to spent) Last fiddled with by pepi37 on 20200330 at 11:08 

20200401, 10:49  #10 
Dec 2011
After milion nines:)
5·257 Posts 
So there is no idea about this?

20200402, 04:58  #11 
Romulan Interpreter
Jun 2011
Thailand
3×2,861 Posts 
The problem here is that sieving is done "by chunks". This means, you create a bitmap in your memory, where you put a bit to 1 for a number, and clear some bits to 0 when you find a factor of some number in your range. If you find a factor for some "bit" in your bitmap and clean it to zero, then other bits in the bitmap, residing at different, deterministic "offsets" compared with the first, can be cleared to zero, by modularity criterias. This is how every sieve works. Now, if your factor is small, then the "offset" is small, because the offset is either the factor itself, or some divisor of the eulerphy of the factor (well, this depends on the properties of the sequence you sieve, but let's ignore this for now). For example, if your factor is 3, then every second, or every third (depending on the sequence) bit in your bitmap can be cleared. By this you eliminate a lot of candidates (like half of them, or a third). Now, if your factor is getting larger, you eliminate less candidates from the bitmap, for one factor. For very large factors, you only eliminate one single candidate from the bitmap (and only if it was not already eliminated before).
Now, thinking about P1, you must do P1 effectively to find out a factor (or more) for each candidate, and once you found that factor, there are zero chances that you can use that factor to eliminate other candidates. For some sequences (like mersenne numbers with prime exponents) it is even proved that they do not share common factors. Therefore, in this respect, your "sieving" doesn't do any better than what was already suggested (i.e. do P1 for all remaining candidates, and eliminate as much as possible from them before going to LLR or PFGW), no matter what and how you find "smooth numbers", or how you "sieve". Even assuming that your sequence allows multiple candidates to have the same factors, these factors that you find by P1 are so large (of course, if sieving with small primes was properly done) that there are zero chances for one factor to eliminate more than one candidate, because your "chunk" you sieve is extremely small compared with the factor. You will need to store trillions of trillions of bits in the memory to have a "worthy" sieve with such large primes. The problem is the chunks you sieve are so small... even if you fill all your RAM with a sieve bitmap. Last fiddled with by LaurV on 20200402 at 05:04 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Why are numbers sum(2^(k*c)) smooth?  preda  Math  11  20180830 17:35 
Not smooth enough numbers  Sam Kennedy  Factoring  5  20121110 07:54 
Properties of Mersenne numbers  kurtulmehtap  Math  31  20110110 00:15 
Smooth and rough numbers  CRGreathouse  Math  3  20090525 05:26 
Smooth Numbers  Yamato  Math  1  20051211 11:09 