mersenneforum.org  

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

Reply
 
Thread Tools
Old 2005-07-14, 16:30   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Question

Quote:
Originally Posted by alpertron
I've found that 5*19^2*47*431 | 2^24036583-3.
I will agree with the statement:

"Knowing if M_p -2 is also prime" is somewhat interesting.

However, I would like to observe that in the current state-of-the-art
in factoring, that trying to factor M_p -2 is HOPELESS, except for the
smallest p.

The level of effort spent so far has not been unreasonable. (IMO). However,
I think spending yet more time is unlikely to lead to success(es).

Allow me to instead suggest an alternative project which does have some
hope of success: Extending the Cunningham project to 'homogeneous form',
i.e. numbers of the form A^n - B^n with (A,B) = 1, B>1. [Cunningham
is just B = 1]

I have already done some modest work in this area. I have completed
the following: ("Base x to y" means that I have completed A^n - B^n
for A = x and all B < A up to exponent y with (A,B) = 1)

Base 3 to 330
Base 4 to 256
Base 5 to 225
Base 6 to 195
Base 7 to 165
Base 8 to 155
Base 9 to 135
Base 10 to 130
Base 11 to 130
Base 12 to 120

I will make these results available to anyone who asks. I don't post them
here; the current tables are ~600Kbytes total.

Perhaps some of you might like to extend these? Such an effort would
be achievable.

I am also cross posting this to the 'factoring' sub group.
R.D. Silverman is offline   Reply With Quote
Old 2005-07-14, 20:17   #2
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

24658 Posts
Default

None of the Computational Number Theory projects can really terminate. Even for the projects where 100 to 200 new results are found each year (as is the case for the Cunningham Tables), as soon there are only a few numbers to finish factoring the tables are extended, so the process can continue indefinitely.

The same occurs with factoring x^y+y^x, partition numbers and others.

When the number of candidates is small, it is surely impossible to finish the task for the remaining candidates, as is the case of Seventeen or Bust project even when they are using about one thousand computers.

Well, I decided to find prime factors of M(p)-2 and prime factors of numbers near googolplex (in my site). I even have a page about factors near googolplexplex.

Of course they will never terminate but I like them.
alpertron is offline   Reply With Quote
Old 2005-07-14, 20:35   #3
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31·43 Posts
Default

Quote:
Originally Posted by alpertron
I even have a page about factors near googolplexplex.
The page is about prime factors of numbers near googolplexplex. Sorry for the mistake.
alpertron is offline   Reply With Quote
Old 2005-07-14, 20:41   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Question

Quote:
Originally Posted by alpertron
None of the Computational Number Theory projects can really terminate. Even for the projects where 100 to 200 new results are found each year (as is the case for the Cunningham Tables), as soon there are only a few numbers to finish factoring the tables are extended, so the process can continue indefinitely.

The same occurs with factoring x^y+y^x, partition numbers and others.

When the number of candidates is small, it is surely impossible to finish the task for the remaining candidates, as is the case of Seventeen or Bust project even when they are using about one thousand computers.

Well, I decided to find prime factors of M(p)-2 and prime factors of numbers near googolplex (in my site). I even have a page about factors near googolplexplex.

Of course they will never terminate but I like them.

(1) Your discussion is irrelevant to what I said. It is clear that current
projects can be extended arbitrarily. What I was discussing is doing something
*achievable*, as opposed to doing something that is *hopeless*.
Factoring M_p -2 for the larger p has ZERO hope of presently succeeding.

(2) You wrote:
"When the number of candidates is small, it is surely impossible to finish the task for the remaining candidates, as is the case of Seventeen or Bust project even when they are using about one thousand computers."

This makes no sense at all. It is gibberish. Why does a small number of
candidates imply that finishing the remaining candidates is impossible??
This is clearly not true for Seventeen or Bust.
R.D. Silverman is offline   Reply With Quote
Old 2005-07-14, 21:01   #5
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31×43 Posts
Default

Quote:
Originally Posted by R.D. Silverman
(1) Your discussion is irrelevant to what I said. It is clear that current
projects can be extended arbitrarily. What I was discussing is doing something
*achievable*, as opposed to doing something that is *hopeless*.
Factoring M_p -2 for the larger p has ZERO hope of presently succeeding.
I do not intend to find _all_ factors of M(p)-2 which I know it is not possible, but to find prime factors, as GIMPS does not intend to find _all_ prime Mersenne number because it is impossible, only to find some of them.

Quote:
Originally Posted by R.D. Silverman
(2) You wrote:
"When the number of candidates is small, it is surely impossible to finish the task for the remaining candidates, as is the case of Seventeen or Bust project even when they are using about one thousand computers."

This makes no sense at all. It is gibberish. Why does a small number of
candidates imply that finishing the remaining candidates is impossible??
This is clearly not true for Seventeen or Bust.
Well, now they have found the easier first half, but for the second half the exponents will be very high, especially for the last prime. You are the expert and you know this much more than I know.

Sorting the exponents in ascending order we have:

698207
995972
1013803
1157446
1337287
5054502
7830457
9167433

we can extrapolate it in order to find that they will never find the nine primes remaining with current knowledge.
alpertron is offline   Reply With Quote
Old 2005-07-15, 12:56   #6
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by alpertron

<snip>

Well, now they have found the easier first half, but for the second half the exponents will be very high, especially for the last prime. You are the expert and you know this much more than I know.

Sorting the exponents in ascending order we have:

698207
995972
1013803
1157446
1337287
5054502
7830457
9167433

we can extrapolate it in order to find that they will never find the nine primes remaining with current knowledge.
Huh? Can anyone else make sense of this? I have read it several times
and can not figure out what is being said.

"Easier first half"

First half of WHAT?

"Second half"

Again, half of WHAT?

"The exponents will be very high, especially for the last prime"

If you are discussing the expected value of the smallest exponent which
yields a prime for each of the remaining Sierpinski candidates, then you
have absolutely NO basis for claiming they will be "very high". Firstly
because "very high" is meaningless, and secondly because we do not
know how primes of the form k*2^n + 1 are asymptotically distributed.
We have no way of guessing what will be the smallest value of n for each k.

*I* don't know enough to make such an extrapolation. So how can you
possibly assert "never find the nine primes remaining"??? If we assume
that for a given k, that k*2^n+1 is prime with probability C(k)/n
[which is what PNT implies] where C(k) is a constant depending on k, then
we can estimate n such that the probability there exists a j < n with
k*2^j+1 being prime is greater then 1/2.

*I* will be very surprised if we need to search above exponent = 10^8
to find the remaining primes. Such a search effort is very large, but doable.
R.D. Silverman is offline   Reply With Quote
Old 2005-07-15, 13:27   #7
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

31·43 Posts
Default

Quote:
Originally Posted by R.D. Silverman
Huh? Can anyone else make sense of this? I have read it several times
and can not figure out what is being said.

"Easier first half"

First half of WHAT?
There are 17 sequences k*2^n+1 that are explored in increasing values of n in order to determine the first prime. There were 8 sequences for which a prime was found. So this is the half of the sequences. It is not very difficult for an expert to understand.

Quote:
Originally Posted by R.D. Silverman
"Second half"

Again, half of WHAT?
The nine sequences remaining have no prime discovered yet. This is the second half.

Quote:
Originally Posted by R.D. Silverman
"The exponents will be very high, especially for the last prime"

If you are discussing the expected value of the smallest exponent which
yields a prime for each of the remaining Sierpinski candidates, then you
have absolutely NO basis for claiming they will be "very high". Firstly
because "very high" is meaningless, and secondly because we do not
know how primes of the form k*2^n + 1 are asymptotically distributed.
We have no way of guessing what will be the smallest value of n for each k.

*I* don't know enough to make such an extrapolation. So how can you
possibly assert "never find the nine primes remaining"??? If we assume
that for a given k, that k*2^n+1 is prime with probability C(k)/n
[which is what PNT implies] where C(k) is a constant depending on k, then
we can estimate n such that the probability there exists a j < n with
k*2^j+1 being prime is greater then 1/2.

*I* will be very surprised if we need to search above exponent = 10^8
to find the remaining primes. Such a search effort is very large, but doable.
From the sequence of increasing exponents, the latest exponent could be greater than 10^9.

Look for example at: http://www.prothsearch.net/sierp.html

You have 40 five-digit exponents listed there.
You have 10 six-digit exponents listed there plus 2 in SB, totalling 12.
There are 6 seven-digit exponents found in SB.
There are 9 unknown exponents.

Extrapolating it appears that the largest exponent will have at least 10 digits.

Of course it is not proved that all remaining sequences have a prime k*2^n+1. In the case that one of them is a Sierpinski sequence, the search time will be infinite.
alpertron is offline   Reply With Quote
Old 2005-07-15, 18:34   #8
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

22·32·31 Posts
Default

Note from the moderator:

Since the original Twin Primes thread was being used as a coordination thread for an ongoing project, I have split off the recent postings which seemed somewhat off-topic and used them to start a new thread. If anyone objects, or would like a different heading, please contact me by PM.

Phil
philmoore is offline   Reply With Quote
Old 2005-07-15, 21:56   #9
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman
If we assume that for a given k, that k*2^n+1 is prime with probability C(k)/n [which is what PNT implies] where C(k) is a constant depending on k, then we can estimate n such that the probability there exists a j < n with k*2^j+1 being prime is greater then 1/2.

*I* will be very surprised if we need to search above exponent = 10^8
to find the remaining primes. Such a search effort is very large, but doable.
You can carry this probability model further - I did it for SeventeenOrBust in May 2003. Note that if each of 9 candidates had a 1/2 chance, there is only a 1/512 chance that ALL of them would be found. The binomial theorem also lets you calculate the probability of "j" of them being found.

It's slightly more complicated because the C(k) values - Proth Weights that are easily estimated with Jack Brennan's applet - are different, so the probability of having found a prime by "n" is different for each k.

Some of the remaining numbers, especially 67607, have very low weight. It's likely that we will need to go much higher than 10^8 to find all the remaining primes.

The hardest part of this is figuring out how to present the results to people with poor probability intuition. There are some standard probability "paradoxes" here, such as increasing residual life, that can cause people to tune out the whole heuristic. The approach I found most successful in communicating these results was to calculate, for each "j", the range of values where the most probable number of primes found is "j." The range for all 17 primes doesn't start until 1.8 x 1013.

The original doorway post is on this thread (although software changes have garbaged the original embedded html non-breaking spaces)

http://www.free-dc.org/forum/showthr...&threadid=2268

vjs has posted updates listing the primes next to heuristic. Here's a recent one.

http://www.free-dc.org/forum/showthr...hlight=108G18T

The sixth and seventh primes were "right on schedule," and the eighth is only "slightly early."

William

Last fiddled with by wblipp on 2005-07-15 at 22:04
wblipp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes p which are in a set of twin primes is finite? carpetpool Miscellaneous Math 3 2017-08-10 13:47
Twin Primes Computer Science & Computational Number Theory 171 2013-05-14 02:57
Twin Primes Hugh Math 64 2011-01-26 08:45
twin primes! sghodeif Miscellaneous Math 9 2006-07-19 03:22
Twin primes again Chris Card Math 1 2005-05-26 14:18

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

Wed Nov 25 23:35:00 UTC 2020 up 76 days, 20:45, 3 users, load averages: 1.03, 1.20, 1.26

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.