mersenneforum.org (https://www.mersenneforum.org/index.php)
-   ONeil (https://www.mersenneforum.org/forumdisplay.php?f=167)
-   -   New App: "Factor This" in python (https://www.mersenneforum.org/showthread.php?t=26114)

 ONeil 2020-10-22 05:17

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:

I can turn this into an exe if anyone is interested just reply and ask cheers Happy Halloween find some scary factors k.
:two cents:
:not prime:
[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

[/CODE]

 VBCurtis 2020-10-22 05:21

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

 ONeil 2020-10-22 05:24

[QUOTE=VBCurtis;560652]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....[/QUOTE]

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

:picard:

 ONeil 2020-10-22 05:53

VB Curtis I think you were to quick to shoot your gun so goes the edit

LOok::groan:

here is:

Enter a prime number: 2^1741-1

123943127595827984958197853301549195184477
951834649657232740658002980565512365360620
750598993511752753104781984819812404805160
890680671892376416742365754415406079582806
461586400276749177364829017737044195679413
446889774379589504010560948137281790718665
410595066884189580638081516368262928596510
612673202568108065230108178215006522436790
409863754899181812033711098574995216116141
064253029870990368664577321247037027510999
375505505057966517508215106597988717628821
189242173762409427175322603725836942582902
938380429071380119551

Now at [URL="https://www.alpertron.com.ar/ECM.HTM"]Alpertron[/URL]

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.

 ONeil 2020-10-22 06:46

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.
:retina:
:bmw:

Enter a prime number: 2^16273-1
390553
14.113915800000001 seconds

 LaurV 2020-10-22 08:13

Things you learn on mersenne forum: :razz:
[QUOTE=ONeil;560651]
[CODE]If the number has factors they are not Mersenne Primes,
[/CODE][/QUOTE]
Sorry to disappoint you, but 2^4-1 has the factor 3, which IS a mersenne prime...

[QUOTE=ONeil]
Enter a prime number: 2^16273-1
[/QUOTE]
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...

:ban:
:dnftt:

 paulunderwood 2020-10-22 08:31

[QUOTE=ONeil;560654]LOok::groan:

here is:

Enter a prime number: 2^1741-1

123943127595827984958197853301549195184477
951834649657232740658002980565512365360620
750598993511752753104781984819812404805160
890680671892376416742365754415406079582806
461586400276749177364829017737044195679413
446889774379589504010560948137281790718665
410595066884189580638081516368262928596510
612673202568108065230108178215006522436790
409863754899181812033711098574995216116141
064253029870990368664577321247037027510999
375505505057966517508215106597988717628821
189242173762409427175322603725836942582902
938380429071380119551

Now at [URL="https://www.alpertron.com.ar/ECM.HTM"]Alpertron[/URL]

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.[/QUOTE]

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.

 mart_r 2020-10-22 08:35

[QUOTE=ONeil;560658]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.[/QUOTE]

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.[/CODE]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!:smile:

 VBCurtis 2020-10-22 08:54

[QUOTE=mart_r;560670]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![/QUOTE]

You only get the really fast replies when you post really terrible stuff, and do it with pride.

 retina 2020-10-22 11:32

[QUOTE=ONeil;560658]As you can see I think this beats most if all factoring codes out there with some factoring coding techniques on some numbers.[/QUOTE]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[/code]I guarantee my code is faster than yours for any number you input, except for the hardcoded known primes which I removed.

 All times are UTC. The time now is 17:49.