mersenneforum.org New App: "Factor This" in python
 Register FAQ Search Today's Posts Mark Forums Read

 2020-10-22, 05:17 #1 ONeil   Dec 2017 24·3·5 Posts New App: "Factor This" in python Ah the speed for the first 101 non-Mersenne Primes where 2^p-1 when p is the inputted number. For under 101 when I typed in 67 it took the longest with this output: Enter a prime number: 67 193707721 93.221183 seconds Yet most numbers would come back like this: Enter a prime number: 1741 1002817 1.8384916000000002 seconds Remember its 2^1741-1 so its a very large number that's is some speed eh hoser. In some cases this App does work exceptionally well for larger number too. However, if you are going to search for 8 digit numbers derived from a prime number that's unknown to be a Mersenne Prime you may need to wait. Also you should change the range if you are going for very large numbers like 8 digit primes. Reply back and I can edit the code for you if you want to wait longer for the big factors. This current code as is returns factors from 9 digits long under 1.3 billion in size. It is written solely in python: So download python 3.7 and run this program: I can turn this into an exe if anyone is interested just reply and ask cheers Happy Halloween find some scary factors k. Code: import timeit print('''This application finds factors of numbers that are 2^p-1. If the number has factors they are not Mersenne Primes, when p (i.e. p is for prime) is the number you entered! For most factors this program finds them under 1.3 billion, only 9 digits. This is for speed purposes. If you try large numbers you will wait for no reason so change the range if you like waiting ''') print("___________________") while True: p = int(input("Enter a prime number: ")) start_time = timeit.default_timer() for z in range(7432339208719,7432339208720,2): if ((2**p-1)% z ) == 0: print(z) print(timeit.default_timer() - start_time,'seconds') break if p == 1: print(p,"Come on man type a larger number or vote for Biden, because he is number 1") continue if p == 2: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 3: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 5: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 7: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 13: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 17: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 19: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 31: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 61: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 89: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 107: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 127: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 521: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 607: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 1279: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 2203: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 2281: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 3217: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 4253: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 4423: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 9689: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 9941: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 11213: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 19937: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 21701: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 23209: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 44497: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 86243: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 110503: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 132049: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 216091: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 756839: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 859433: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 1257787: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 1398269: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 2976221: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 3021377: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 6972593: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 13466917: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 20996011: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 24036583: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 25964951: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 30402457: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 32582657: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 37156667: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 42643801: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 43112609: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 57885161: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 74207281: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 77232917: print(p,"The input 'p' produces a Mersenne Prime") continue elif p == 82569933: print(p,"The input 'p' produces a Mersenne Prime") continue for x in range(3,(999999999),2): if ((2**p-1)% x ) == 0: print(x) print(timeit.default_timer() - start_time,'seconds') break
 2020-10-22, 05:21 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 22×7×132 Posts This is the slowest form of trial factoring available. You have exhibited zero knowledge of the structure of mersenne factors. You've never seen "2kp+1"? You could start there. EDIT: Wait, there are likely even slower trial factoring methods available- I forget how weird some of the inventions are around here.... Last fiddled with by VBCurtis on 2020-10-22 at 05:22
2020-10-22, 05:24   #3
ONeil

Dec 2017

24010 Posts

Quote:
 Originally Posted by VBCurtis This is the slowest form of trial factoring available. You have exhibited zero knowledge of the structure of mersenne factors. You've never seen "2kp+1"? You could start there. EDIT: Wait, there are likely even slower trial factoring methods available- I forget how weird some of the inventions are around here....

I understand but some of my returns you have to admit are lightening fast Come on man.

 2020-10-22, 05:53 #4 ONeil   Dec 2017 24·3·5 Posts VB Curtis I think you were to quick to shoot your gun so goes the edit LOok: here is: Enter a prime number: 2^1741-1 123943127595827984958197853301549195184477 951834649657232740658002980565512365360620 750598993511752753104781984819812404805160 890680671892376416742365754415406079582806 461586400276749177364829017737044195679413 446889774379589504010560948137281790718665 410595066884189580638081516368262928596510 612673202568108065230108178215006522436790 409863754899181812033711098574995216116141 064253029870990368664577321247037027510999 375505505057966517508215106597988717628821 189242173762409427175322603725836942582902 938380429071380119551 Now at Alpertron Try factoring this 2^1741-1 at Alpertron and it will take a long time its been 7 minutes and my program did it under 2 seconds. Last fiddled with by ONeil on 2020-10-22 at 05:57
 2020-10-22, 06:46 #5 ONeil   Dec 2017 24×3×5 Posts Wow my code just found a factor in 14 seconds for a huge number! My code is very fast for some numbers its true, yet for 8 digits you might have to edit the range if you want a long time search. I'm going to try it with the existing code on some 8 digit searches to see if there are any with small 9 digit factors. As you can see I think this beats most if all factoring codes out there with some factoring coding techniques on some numbers. Enter a prime number: 2^16273-1 390553 14.113915800000001 seconds
2020-10-22, 08:13   #6
LaurV
Romulan Interpreter

Jun 2011
Thailand

100100100110012 Posts

Things you learn on mersenne forum:
Quote:
 Originally Posted by ONeil Code: If the number has factors they are not Mersenne Primes,
Sorry to disappoint you, but 2^4-1 has the factor 3, which IS a mersenne prime...

Quote:
 Originally Posted by ONeil Enter a prime number: 2^16273-1
Suggestion: Reply from application: sorry, this number is not prime. End exits.
(or, if you indeed enter a prime, the system would reply "sorry, this is prime, what do you want to factor at it?".

Let's put some money together until we collect so much to convince Xyzzy to let us ban bloggers...

Last fiddled with by LaurV on 2020-10-22 at 08:22

2020-10-22, 08:31   #7
paulunderwood

Sep 2002
Database er0rr

70418 Posts

Quote:
 Originally Posted by ONeil LOok: here is: Enter a prime number: 2^1741-1 123943127595827984958197853301549195184477 951834649657232740658002980565512365360620 750598993511752753104781984819812404805160 890680671892376416742365754415406079582806 461586400276749177364829017737044195679413 446889774379589504010560948137281790718665 410595066884189580638081516368262928596510 612673202568108065230108178215006522436790 409863754899181812033711098574995216116141 064253029870990368664577321247037027510999 375505505057966517508215106597988717628821 189242173762409427175322603725836942582902 938380429071380119551 Now at Alpertron Try factoring this 2^1741-1 at Alpertron and it will take a long time its been 7 minutes and my program did it under 2 seconds.
Your code sux. Why not input the exponent? Why a huge if then else construct -- doesn't python have set inclusion? At least loop over an array. You do not use the structure of Mersennes with prime exponents, namely 2*k*p+1 -- loop over k instead and watch your ego smoke. You program does not completely factorise M1741 -- it finds a small factor of it. You'll also need to check the exponent entered is prime.

Last fiddled with by paulunderwood on 2020-10-22 at 08:50

2020-10-22, 08:35   #8
mart_r

Dec 2008
you know...around...

11778 Posts

Quote:
 Originally Posted by ONeil My code is very fast for some numbers its true, yet for 8 digits you might have to edit the range if you want a long time search. I'm going to try it with the existing code on some 8 digit searches to see if there are any with small 9 digit factors. As you can see I think this beats most if all factoring codes out there with some factoring coding techniques on some numbers.
If you are amazed by this, you'd be completely flabbergasted by learning what is actually possible these days.

Code:
? p=1741;m=2^p-1;q=2*p+1;while(m%q,q+=2*p);print(q)
1002817
***   last result computed in 0 ms.
? p=16273;m=2^p-1;q=2*p+1;while(m%q,q+=2*p);print(q)
390553
***   last result computed in 0 ms.
? p=67;m=2^p-1;q=2*p+1;while(m%q,q+=2*p);print(q)
193707721
***   last result computed in 318 ms.
Note that "ms" = millliseconds. if the PC would be bothered to measure the time it took to find the factors of the first two examples, it would probably have been less than 0.0001 seconds.

Edit: Meh, LaurV is faster than me in posting things... and I even messed up the quote tags now...*
Edit2: and Paul too... I should really consider posting my prime gap stuff in MiscMath!
*Edit3: Thanks, LaurV!

Last fiddled with by mart_r on 2020-10-22 at 09:08 Reason: fixed quote

2020-10-22, 08:54   #9
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

111748 Posts

Quote:
 Originally Posted by mart_r Edit: Meh, LaurV is faster than me in posting things... and I even messed up the quote tags now... Edit2: and Paul too... I should really consider posting my prime gap stuff in MiscMath!
You only get the really fast replies when you post really terrible stuff, and do it with pride.

2020-10-22, 11:32   #10
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5·1,223 Posts

Quote:
 Originally Posted by ONeil As you can see I think this beats most if all factoring codes out there with some factoring coding techniques on some numbers.
Claim is false because I can make faster code:
Code:
import timeit
while True:
p = int(input("Enter a prime number: "))
start_time = timeit.default_timer()
for k in range(1,999999999):
if ((2**p-1) % (2*k*p+1)) == 0:
print(2*k*p+1)
print(timeit.default_timer() - start_time,'seconds')
break
I guarantee my code is faster than yours for any number you input, except for the hardcoded known primes which I removed.

 Similar Threads Thread Thread Starter Forum Replies Last Post ONeil ONeil 21 2018-05-26 16:38 wildrabbitt Miscellaneous Math 11 2015-03-06 08:17 swl551 GPU Computing 2 2012-12-20 15:20 kracker PrimeNet 2 2012-07-22 17:49 James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09

All times are UTC. The time now is 09:15.

Wed Apr 14 09:15:30 UTC 2021 up 6 days, 3:56, 0 users, load averages: 1.72, 1.73, 1.65