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

26·113 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

8,369 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

172B16 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

9,791 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

161008 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
London, UK

101000111002 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

23A816 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
London, UK

130810 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 21:55.

Mon Oct 26 21:55:38 UTC 2020 up 46 days, 19:06, 0 users, load averages: 1.66, 1.52, 1.65

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.