if p is prime, factors of 2^p-1? - Is it possible? - Page 2

LaurV · 2020-10-23, 05:32

Quote:

Originally Posted by ONeil

As you may or may not know all factors of prime numbers

...are the number itself and 1.
I think you only trolling, because I can't imagine a real person can behave the way yo do, so ignorant and so proud in the same time.
Take the advice other people gave you, and start learning something serious.

ONeil · 2020-10-23, 07:56

I think they have the inside scoop.

I have found the machine for finding factors very fast. You need to make a list of many primes that are at least 10 digits long or greater than the average for factors found length. That's work I know, but when you are done you save time. Instead of a month processing your machine will come back in seconds with a factor. Now granted its about your list so you could miss a factor. At least if you miss a factor you could either make you list bigger or test that number to see if its prime here is the code. This code opens the list in a text file and uses it as mod against your test 2^p-1.

Here you can at least assess the average factor length:
https://www.mersenne.org/report_fact...xp_lo=12354673

Here is a small portion of my list inside the text file:

Quote:

k = ( 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283)

Code:

import timeit
while True:
	p = int(input("Enter a prime number: "))
	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

	with open("C:\python37\k.txt",'r') as f:
		primes = f.read().split("(")[1].split(')')[0].split(',')  # int list of primes
		primes = [int(i.strip()) for i in primes]
		for prime in primes:
			if (2**p - 1) % int(prime) == 0:
				start_time = timeit.default_timer()
				print(prime)
				print(timeit.default_timer() - start_time,'seconds')
				break

Viliam Furik · 2020-10-23, 08:02

Quote:

Originally Posted by a1call

Meant 2^p-1
If for any prime p
2*p+1 | 2^p-1
Then 2*p+1 is definitely prime.
The test is deterministic and computationally about as expensive as a PRP test.

This works with only k=1, thus if it divides 2^p-1, it is definitely a prime factor.

ONeil · 2020-10-23, 08:04

Quote:

Originally Posted by LaurV

...are the number itself and 1.
I think you only trolling, because I can't imagine a real person can behave the way yo do, so ignorant and so proud in the same time.
Take the advice other people gave you, and start learning something serious.

LaurV you are not a decent person you misquoted me you now have no respect from me you stoop very low indeed!

Viliam Furik · 2020-10-23, 08:07

Quote:

Originally Posted by ONeil

LaurV you are not a decent person you misquoted me you now have no respect from me you stoop very low indeed!

That is not a misquote, you are simply talking nonsense. Primes are not composite, that is their definition.

If you mean the Mersenne numbers... Those can be composite. Mersenne primes are a very rare special case of those numbers.

paulunderwood · 2020-10-23, 08:07

https://www.w3schools.com/python/python_sets.asp shows how to use sets in python. So you write something like:

Code:

known_mersenne_primes = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 82569933}

and then you can use "in" like:

Code:

if p in known_mersenne_primes:
		print(p,"The input 'p' produces a Mersenne Prime")

ONeil · 2020-10-23, 08:13

Quote:

Originally Posted by paulunderwood

https://www.w3schools.com/python/python_sets.asp shows how to use sets in python. So you write something like:

Code:

known_mersenne_primes = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657, 37156667, 42643801, 43112609, 57885161, 74207281, 82569933}

and then you can use "in" like:

Code:

if p in known_mersenne_primes:
		print(p,"The input 'p' produces a Mersenne Prime")

Thanks for the update Paul

ONeil · 2020-10-23, 08:20

Quote:

Originally Posted by Viliam Furik

That is not a misquote, you are simply talking nonsense. Primes are not composite, that is their definition.

If you mean the Mersenne numbers... Those can be composite. Mersenne primes are a very rare special case of those numbers.

This is what I said

Primes that make numbers from 2^p-1 which are not prime have factors that are prime, sorry for the confusion.

ONeil · 2020-10-23, 08:24

A better way to phrase it would be:

A composite number produced from a prime number using 2^p-1 does contain prime factors!

Viliam Furik · 2020-10-23, 08:51

Quote:

Originally Posted by ONeil

This is what I said

No, it is not. It is what you meant by it, but not what you actually said. But I understand now.

But there's a little sense in saying that. If the Mersenne number (2^p-1) is prime, there is no discussion about factors. If it's not a prime, well, the only other option is that it is composite, which means it does have prime factors, but if it has strictly more than 2 of them (all the time, except for a very small part of those numbers), then the product of any two prime factors is also a factor, but a composite one.

paulunderwood · 2020-10-23, 08:57

It is of absolutely no use in reading in a list of factors. The factors of Mersenne numbers with prime exponents is disjoint: a prime dividing one Mp will not divide another Mq.

Reading in from disk takes time too,

It is better to loop over k for 2pk+1. For example M11 is (2*11+1)*(2*4*11+1)

Going up to "10 digits" is pathetic. The guys (an gals) here go up to over 24 digits routinely.

2020-10-23, 08:57	#22
paulunderwood Sep 2002 Database er0rr 7012₈ Posts	It is of absolutely no use in reading in a list of factors. The factors of Mersenne numbers with prime exponents is disjoint: a prime dividing one Mp will not divide another Mq. Reading in from disk takes time too, It is better to loop over k for 2pk+1. For example M11 is (211+1)(2411+1) Going up to "10 digits" is pathetic. The guys (an gals) here go up to over 24 digits routinely. Last fiddled with by paulunderwood on 2020-10-23 at 09:05

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	2020-10-01 14:36
Checking that there are no prime factors up to x	CRGreathouse	Math	14	2017-09-22 16:00
Prime factors of googolplex - 10.	Arkadiusz	Factoring	6	2011-12-10 15:16
Are all factors prime?	kurtulmehtap	Math	4	2010-09-02 19:51
Distribution of Mersenne prime factors mod 6	alpertron	Math	0	2006-06-23 20:07

2020-10-23, 08:24	#20
ONeil Dec 2017 F0₁₆ Posts	A better way to phrase it would be: A composite number produced from a prime number using 2^p-1 does contain prime factors!