mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2003-08-06, 16:28   #1
dsouza123
 
dsouza123's Avatar
 
Sep 2002

10100101102 Posts
Default Search for Mersenne primes by checking for perfect numbers

After reading http://www.utm.edu/research/primes/mersenne/ and finding the link between perfect numbers and mersenne primes,
with each perfect number the product of a number times a mersenne prime, I wonder if a search for perfect numbers would be useful for finding mersenne primes.

There seems to be fewer perfect numbers then mersenne primes ( for a given range ), some of the mersenne primes aren't factors of a perfect number. So this strategy will skip some mersenne primes but still may find some that were missed or not yet found.

The binary format for perfect numbers seems amenable for a program,
1s followed by 0s and the test: convert to decimal then keep adding the digits until only one digit remains, if it is 1 then it is a perfect number.

The prime exponents Prime95 is dealing with would be under 10 million bytes. Example p = 24 000 000 , so it is the same number of bits, divide by 8 to get bytes equals 3 000 000 bytes.
This may only get a mersenne prime of roughly 1/2 p so doubling the size of p to 48 000 000 would give 6 million bytes and should put it back in range.
Given x number of bits would give roughly x/2 for p.

The coding doesn't appear to be hard but I don't know how long it would take to run for each large possible perfect number.

I may code it, testing with the smaller numbers first.

Is there already someone working on this or is there some other issue(s) (math or programming) that would make this nonviable ?

I guess this topic could have gone in the new forum Factoring if it was open.
Discovering perfect numbers to get their mersenne prime factor !
dsouza123 is offline   Reply With Quote
Old 2003-08-06, 17:43   #2
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22×3×11 Posts
Default

I think you missed something from that page:

Quote:
Theorem One: k is an even perfect number if and only if it has the form 2^(n-1)(2^n-1) and 2^n-1 is prime.
This basically says that all mersenne primes correspond with an even perfect number and all even perfect numbers correspond with a mersenne prime.

As far as I know, an LL test is much faster than any methods we have for finding perfect numbers.
NickGlover is offline   Reply With Quote
Old 2003-08-06, 18:48   #3
dsouza123
 
dsouza123's Avatar
 
Sep 2002

29616 Posts
Default

The very property of perfect numbers that could be exploited is,
if a perfect number then one factor is a mersenne prime.

The only (obvious) thing that could derail it is given a number that follows the binary form from the web page, converting it to decimal, repeatedly summing the digits, finally getting one digit with a value of 1, and it not being a perfect number.

My understanding was all the perfect numbers followed the binary form given on the web page.

As for the speed of this algorithm, that remains to be seen.

I was able to match some of the mersenne primes to perfect numbers, some had no obvious pairing.

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127 for mersenne primes.
2.3=6, 4.7=28, 16.31=496, 64.127=8128 as the pairs.

Where is the pair for 2,5,13,17,19,61,89,107 ?
dsouza123 is offline   Reply With Quote
Old 2003-08-06, 18:59   #4
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

100001002 Posts
Default

Quote:
Originally Posted by dsouza123
I was able to match some of the mersenne primes to perfect numbers, some had no obvious pairing.

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127 for mersenne primes.
2.3=6, 4.7=28, 16.31=496, 64.127=8128 as the pairs.

Where is the pair for 2,5,13,17,19,61,89,107 ?
You need to match the mersenne primes, not just the exponents:

2*(2^2-1) = 6
4*(2^3-1) = 28
16*(2^5-1) = 496
.
.
.
NickGlover is offline   Reply With Quote
Old 2003-08-06, 19:04   #5
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2×5×37 Posts
Default

Quote:
Originally Posted by dsouza123
I was able to match some of the mersenne primes to perfect numbers, some had no obvious pairing.

n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127 for mersenne primes.
2.3=6, 4.7=28, 16.31=496, 64.127=8128 as the pairs.

Where is the pair for 2,5,13,17,19,61,89,107 ?
You're looking at the exponents, not the Mersenne primes themselves.
The first Mersenne prime is 3 (2^2-1)
The second Mersenne prime is 7 (2^3-1)
The third Mersenne prime is 31 (2^5-1)
etc.

And these numbers are what you are matching up.

edit: Oops, Nick beat me to it.
eepiccolo is offline   Reply With Quote
Old 2003-08-06, 19:07   #6
toferc
 
Aug 2002

2·3·5 Posts
Default

Quote:
Originally Posted by NickGlover
Quote:
Theorem One: k is an even perfect number if and only if it has the form 2^(n-1)(2^n-1) and 2^n-1 is prime.
n = 2: 2^1 * (2^2-1) = 6
n = 3: 2^2 * (2^3-1) = 28
n = 5: 2^4 * (2^5-1) = 496

etc.

The definition of a perfect number is that it is equal to the sum of all of its factors. In order to find this sum you need to know all of the number's prime factors. Thus you need to check 2^n-1 to see if it is prime in order to determine if 2^(n-1)(2^n-1) is perfect.

edit: oops, Nick and eepiccolo beat me to it
toferc is offline   Reply With Quote
Old 2003-08-06, 19:09   #7
NickGlover
 
NickGlover's Avatar
 
Aug 2002
Richland, WA

22·3·11 Posts
Default

From the fact that even perfect numbers are of the form 2^(n-1)*(2^n-1), the binary representation must be n 1's followed by n-1 0's.

I also do not understand your algorithm for checking if a number is a perfect number:

Quote:
The only (obvious) thing that could derail it is given a number that follows the binary form from the web page, converting it to decimal, repeatedly summing the digits, finally getting one digit with a value of 1, and it not being a perfect number.
How can you get 1 from summing the digits of a large number unless you sum them mod some other number (10?)? And how does the fact that they add up to 1 mean the number is a perfect number? How do the digits of 6 and 28 add up to 1?
NickGlover is offline   Reply With Quote
Old 2003-08-06, 19:11   #8
dsouza123
 
dsouza123's Avatar
 
Sep 2002

2×331 Posts
Default

ok

thanks, that accounts for the missing pairs.
dsouza123 is offline   Reply With Quote
Old 2003-08-06, 19:28   #9
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2·5·37 Posts
Default

Quote:
Originally Posted by NickGlover
How can you get 1 from summing the digits of a large number unless you sum them mod some other number (10?)? And how does the fact that they add up to 1 mean the number is a perfect number? How do the digits of 6 and 28 add up to 1?
Other than 6, repeatedly summing the digits of a perfect number will eventually get you to 1.
2+8=10, 1+0=1;
4+6+9=19, 1+9=10, 1+0=1;
etc.

But I don't know if that statement is an "iff" statement, and if it isn't (and I don't think it is), the algorithm won't work.
eepiccolo is offline   Reply With Quote
Old 2003-08-06, 19:31   #10
toferc
 
Aug 2002

2×3×5 Posts
Default

Counterexample:
2^10*(2^11-1) = 2096128
toferc is offline   Reply With Quote
Old 2003-08-06, 19:51   #11
eepiccolo
 
eepiccolo's Avatar
 
Dec 2002
Frederick County, MD

2×5×37 Posts
Default

Actually, after looking at it, the summing the digits of a number of form 2^(2n-1) - 2^(n-1) (This formula makes numbers of the binary form describe at the web site) I think results in 1 if n is prime. In no way could this be used to prove that a number is perfect.

BTW, 2+9+6+1+2+8 = 28, 2+8 = 10, 1+0 = 1
eepiccolo is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Odd Perfect Number Search - Factoring Project pinhodecarlos Forum Feedback 1 2012-09-11 05:11
How to generate base10 representation of Mersenne-prime perfect numbers? James Heinrich Miscellaneous Math 10 2012-03-08 07:20
How does the Odd Perfect Number search work? jasong Math 5 2007-04-14 21:56
Could a bot be used to help the Odd Perfect Number search? jasong Factoring 1 2007-04-13 01:52
How much work on Odd Perfect Number search? jasong GMP-ECM 5 2007-04-11 03:00

All times are UTC. The time now is 23:23.


Fri Aug 19 23:23:21 UTC 2022 up 1 day, 20:51, 1 user, load averages: 0.98, 1.17, 1.21

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔