mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-10-26, 11:04   #1
kurtulmehtap
 
Sep 2009

22·32 Posts
Default mersenne prime as a factor of another number

I wonder if there are a special class of number which have mersenne primes as factors?
Thanx...
kurtulmehtap is offline   Reply With Quote
Old 2010-10-26, 11:50   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
I wonder if there are a special class of number which have mersenne primes as factors?
Thanx...
No.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-26, 12:29   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
No.
r.d. silverman are you forgetting perfect numbers ? if so I hope you refresh.
science_man_88 is offline   Reply With Quote
Old 2010-10-26, 13:15   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
I wonder if there are a special class of number which have mersenne primes as factors?
Thanx...
Only Mersenne primes, or at least one Mersenne prime?

For the former, that's all subsets of 1 U A056652. For the latter... that's pretty dense, natural density 0.4514311155... if I'm not mistaken. The sequence starts 3,6,7,9,12,14,15,18,21,24,27,28,30,31,... and includes sequences like 22n - 1.
CRGreathouse is offline   Reply With Quote
Old 2010-10-26, 16:41   #5
Raman
Noodles
 
Raman's Avatar
 
"Mr. Tuch"
Dec 2007
Chennai, India

3×419 Posts
Default

23209 is factor of M967
Or do you rather mean that list of Wieferich primes?
such as that cases for that of
q2 | 2p-1
1093, 3511
For example, please notice that 10932 indeed
divides up with that Wagstaff number: (2182+1)/3

Really following up within that way
10932 | M1092
35112 | M3510
of course
for ever
Raman is offline   Reply With Quote
Old 2010-10-27, 19:22   #6
ewmayer
2ω=0
 
ewmayer's Avatar
 
Sep 2002
República de California

22·3·7·139 Posts
Default

Quote:
Originally Posted by kurtulmehtap View Post
I wonder if there are a special class of number which have mersenne primes as factors?
Thanx...
Yes there is:

Initialize x[0] = 4 (other values are also possible, but we'll keep it simple for now)
For m := 2^p-1 prime, do p-2 of the following iterations:
x[i] = x[i-1]^2 - 2

Then x[p-2] is divisible by m.

Simplest case: p=3, m=7, and x[p-2] = x[1] = 14, which is divisible by 7.
ewmayer is offline   Reply With Quote
Old 2010-10-27, 20:25   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Yes there is:

Initialize x[0] = 4 (other values are also possible, but we'll keep it simple for now)
For m := 2^p-1 prime, do p-2 of the following iterations:
x[i] = x[i-1]^2 - 2

Then x[p-2] is divisible by m.

Simplest case: p=3, m=7, and x[p-2] = x[1] = 14, which is divisible by 7.
One can construct many artificial examples of this type. But I took the
question to mean whether there is some a priori interesting set of numbers divisible by Mersenne primes. One can always construct
such classes. Perfect numbers are an example of such a constructed
class (and are the original reason for the study of M_p).
R.D. Silverman is offline   Reply With Quote
Old 2010-10-30, 21:26   #8
Damian
 
Damian's Avatar
 
May 2005
Argentina

2·3·31 Posts
Default

Quote:
Originally Posted by ewmayer View Post
Yes there is:

Initialize x[0] = 4 (other values are also possible, but we'll keep it simple for now)
For m := 2^p-1 prime, do p-2 of the following iterations:
x[i] = x[i-1]^2 - 2

Then x[p-2] is divisible by m.

Simplest case: p=3, m=7, and x[p-2] = x[1] = 14, which is divisible by 7.
I know this is the LL primality test for mersenne numbers (numbers of the form 2^p - 1 for some prime number p )

Is there a similar primality test for numbers of the form 3^p - 2^p for some prime number p ?

Thanks.

Last fiddled with by Damian on 2010-10-30 at 21:26
Damian is offline   Reply With Quote
Old 2010-10-31, 19:49   #9
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

136210 Posts
Default

Quote:
Originally Posted by Damian View Post
Is there a similar primality test for numbers of the form 3^p - 2^p for some prime number p ?
I have absolutely no idea, but here are the first 19 values of p where the expression is prime:
Code:
2
3
5
17
29
31
53
59
101
277
647
1061
2381
2833
3613
3853
3929
5297
7417
Checked all p < 30000. Note that the last one is only a probable prime, the others have been deterministically tested with Primo.
lavalamp is offline   Reply With Quote
Old 2010-10-31, 20:12   #10
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

59×163 Posts
Default

A057468 is well studied.
Batalov is offline   Reply With Quote
Old 2010-10-31, 20:55   #11
lavalamp
 
lavalamp's Avatar
 
Oct 2007
Manchester, UK

101010100102 Posts
Default

Quote:
Originally Posted by http://www.research.att.com/~njas/sequences/A057468
Some of the larger entries may only correspond to probable primes.

The 1137- and 1352-digit values associated with the terms 2381 and 2833 have been certified prime with Primo. - Rick L. Shepherd
I have uploaded primality certificates for p = 3613, 3853, 3929 and 5297, and the certificate for p = 7417 will be uploaded when it's finished. Don't think I'll be creating any for p = 90217 or above...

http://2721.hddkillers.com/3^n-2^n/
lavalamp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
(M48) NEW MERSENNE PRIME! LARGEST PRIME NUMBER DISCOVERED! dabaichi News 571 2020-10-26 11:02
Number of distinct prime factors of a Double Mersenne number aketilander Operazione Doppi Mersennes 1 2012-11-09 21:16
Lucas-number prime factor form proofs Raman Math 1 2012-09-12 13:21
62-digit prime factor of a Mersenne number ET_ Factoring 39 2006-05-11 18:27
How to check if a number is a Mersenne prime ? Unregistered Software 6 2004-06-19 08:18

All times are UTC. The time now is 00:56.


Sat Dec 4 00:56:28 UTC 2021 up 133 days, 19:25, 0 users, load averages: 1.75, 1.51, 1.44

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.