20201023, 00:19  #1  
Dec 2017
2^{4}×3×5 Posts 
if p is prime, factors of 2^p1?  Is it possible?
Ok according to the mods and some users "Factor this" was a disaster, so they locked the thread. Yet is it all lost or not. So I got to thinking and some here would say that is a dangerous thing lol :). I have a big question for some of the python programmers here.
As you may or may not know all factors of prime numbers which use this formula 2^p1 when p is prime and 2^p1 does not produce a prime, the factor is prime. Would it be possible to use a text file with many prime numbers and then access it instantaneously and apply modular arithmetic to instantly find a factor for '2^p1' if 'p' is a prime number while using 2^p1 and that does not produce a prime number this is what's in my text file: k=(3,5,7,11,13,17,19,23, 47, 223, 233) Here is the code I have so far but its throwing this error: Quote:
Code:
import timeit while True: p = int(input("Enter a prime number: ")) start_time = timeit.default_timer() for k in range(3,300,2): if (2**p1) % (open("C:\python37\k.txt"),'r') == 0: print(k) print(timeit.default_timer()  start_time,'seconds') break Last fiddled with by ONeil on 20201023 at 00:25 

20201023, 00:34  #2 
Sep 2002
Database er0rr
2×3×19×31 Posts 
Learn to program. Get yourself an elementary book on Python.
I do not know Python. It does have set membership and arrays. I guess Python, like may other languages, requires you to open the file and the loop over the stream until the end of the file and then close it. So you could open the file and read in the vector. Whether you can take a "%" over a vector I am not sure. Somebody else who is knowledgeable about this language will jump in and put you right. Last fiddled with by paulunderwood on 20201023 at 00:38 
20201023, 00:39  #3  
Dec 2017
2^{4}×3×5 Posts 
Quote:
I think it is possible I'm just worried about speed, if it does it in a flash then I think its worth pursuing. I can imagine the text file could be very large tho yet if you can test large digit primes and say one inputs an 8 digit prime to test and then a factor comes back in a flash then you can move on to another test. 

20201023, 01:42  #4 
"Curtis"
Feb 2005
Riverside, CA
5^{3}×37 Posts 
You can move on to other tests already all of the factors your methods could find have already been found for exponents below 4 billion or so.
You haven't the slightest idea of the mathematics of mersenne factors, nor how to program so you're writing really slow code that does really slow algorithms to factor. If you want fast factors of mersennes, use factor5, or Prime95. Or, read the most basic properties of mersenne factors. Your first statement isn't even true not every factor of 2^p1 is prime. Some are composite, really. 
20201023, 01:49  #5 
"Rashid Naimi"
Oct 2015
Remote to Here/There
3676_{8} Posts 
I think what he is referring to is that a factor of 2^p1 is prime if (single"f") it is equal to 2p+1.

20201023, 02:11  #6 
Dec 2017
2^{4}×3×5 Posts 
Yes there is always a single factor for one of them is prime. This is a worth while venture if the returns are fast. Think about it I can spend the time to print out a list of big primes into a text file beyond the ones that are found. Then simply type a number 8 to 9 digits as a prime number and it it returns quickly as a factor then we have something otherwise I agree with you VB if time does not permit this.
VBCurtis you should really expand your mind a little and like these fresh well thought out creative experiments they do leed to greatness sometimes. I not saying we or I am there yet, but who knows what if we get the speeeeeeeeeeeed. Last fiddled with by ONeil on 20201023 at 02:13 
20201023, 02:30  #7 
"Curtis"
Feb 2005
Riverside, CA
5^{3}·37 Posts 
We already have the speed. You don't. Your methods are slow, and reflect no comprehension of factoring.
You don't even grasp how long it would take to read primes from a text file, versus generate them live via code. You think reading a file is "instant". It's not, not even a little bit. "I'm so ignorant I might be a genius" is a special sort of argument. We have a name for that flavor of ignorance, too. Last fiddled with by VBCurtis on 20201023 at 02:32 
20201023, 02:32  #8 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2×991 Posts 
To see if 2p+1 divides 2*p1 is computationally about as expensive as a PRP test. It is deterministic but not much, much faster than a PRP test and then a N1 test.
I learned about it from SM and here is an old relevant thread: https://www.mersenneforum.org/showthread.php?t=24964 Last fiddled with by a1call on 20201023 at 02:33 
20201023, 02:35  #9  
"Curtis"
Feb 2005
Riverside, CA
5^{3}×37 Posts 
Quote:
Hint: testing k=1 in trial factoring, versus a prp test. No ,not the same computational length. No. Edit: Wait, do you mean 2*p1, or 2^p1? If you mean 2*p1, how is 2p+1 going to divide 2p1, which is smaller? Eh? Last fiddled with by VBCurtis on 20201023 at 02:37 

20201023, 02:53  #10 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·991 Posts 
Meant 2^p1
If for any prime p 2*p+1  2^p1 Then 2*p+1 is definitely prime. The test is deterministic and computationally about as expensive as a PRP test. 
20201023, 02:55  #11 
"Rashid Naimi"
Oct 2015
Remote to Here/There
2·991 Posts 
Meant 2^p1
If for any prime p 2*p+1  2^p1 Then 2*p+1 is definitely prime. The test is deterministic and computationally about as expensive as a PRP test for 2*p+1. The time saved is not significant. Sorry for the double post. Was not intentional. Last fiddled with by a1call on 20201023 at 02:56 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
largest n such that n^2+1 has prime factors within a set  fivemack  Abstract Algebra & Algebraic Number Theory  8  20201001 14:36 
Checking that there are no prime factors up to x  CRGreathouse  Math  14  20170922 16:00 
Prime factors of googolplex  10.  Arkadiusz  Factoring  6  20111210 15:16 
Are all factors prime?  kurtulmehtap  Math  4  20100902 19:51 
Distribution of Mersenne prime factors mod 6  alpertron  Math  0  20060623 20:07 