mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > ONeil

Closed Thread
 
Thread Tools
Old 2020-10-22, 05:17   #1
ONeil
 
ONeil's Avatar
 
Dec 2017

7·23 Posts
minus 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
ONeil is online now  
Old 2020-10-22, 05:21   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

106258 Posts
Default

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
VBCurtis is online now  
Old 2020-10-22, 05:24   #3
ONeil
 
ONeil's Avatar
 
Dec 2017

7×23 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.

ONeil is online now  
Old 2020-10-22, 05:53   #4
ONeil
 
ONeil's Avatar
 
Dec 2017

7×23 Posts
Default 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
ONeil is online now  
Old 2020-10-22, 06:46   #5
ONeil
 
ONeil's Avatar
 
Dec 2017

7×23 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
ONeil is online now  
Old 2020-10-22, 08:13   #6
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

214028 Posts
Default

Things you learn on mersenne forum:
Quote:
Originally Posted by ONeil View Post
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
LaurV is offline  
Old 2020-10-22, 08:31   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

5×701 Posts
Default

Quote:
Originally Posted by ONeil View Post
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
paulunderwood is offline  
Old 2020-10-22, 08:35   #8
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

25×19 Posts
Default

Quote:
Originally Posted by ONeil View Post
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
mart_r is offline  
Old 2020-10-22, 08:54   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

7×643 Posts
Default

Quote:
Originally Posted by mart_r View Post
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.
VBCurtis is online now  
Old 2020-10-22, 11:32   #10
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

133778 Posts
Default

Quote:
Originally Posted by ONeil View Post
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.
retina is offline  
Closed Thread

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
"Genius" needed to speed up this not-even-a-sieve in Python but he did not succeed ONeil ONeil 21 2018-05-26 16:38
Aouessare-El Haddouchi-Essaaidi "test": "if Mp has no factor, it is prime!" wildrabbitt Miscellaneous Math 11 2015-03-06 08:17
mfaktX result: "found 1 factor for M" swl551 GPU Computing 2 2012-12-20 15:20
Specifing TF factor depth in "Manual Assignments"? kracker PrimeNet 2 2012-07-22 17:49
P-1 factoring != "Mersenne numbers to factor"? James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09

All times are UTC. The time now is 01:34.

Fri Dec 4 01:34:02 UTC 2020 up 21:45, 1 user, load averages: 2.53, 2.88, 2.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.