 mersenneforum.org > Math OT: Twin Primes
 Register FAQ Search Today's Posts Mark Forums Read 2005-07-14, 16:30   #1
R.D. Silverman

Nov 2003

164448 Posts 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.   2005-07-14, 20:17 #2 alpertron   Aug 2002 Buenos Aires, Argentina 5·277 Posts 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.   2005-07-14, 20:35   #3
alpertron

Aug 2002
Buenos Aires, Argentina

25518 Posts 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.   2005-07-14, 20:41   #4
R.D. Silverman

Nov 2003

22×5×373 Posts 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.   2005-07-14, 21:01   #5
alpertron

Aug 2002
Buenos Aires, Argentina

5·277 Posts 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.   2005-07-15, 12:56   #6
R.D. Silverman

Nov 2003

164448 Posts Quote:
 Originally Posted by alpertron 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.   2005-07-15, 13:27   #7
alpertron

Aug 2002
Buenos Aires, Argentina

5×277 Posts 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.   2005-07-15, 18:34 #8 philmoore   "Phil" Sep 2002 Tracktown, U.S.A. 3·373 Posts 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   2005-07-15, 21:56   #9
wblipp

"William"
May 2003
New Haven

23×103 Posts 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)

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  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 3 2017-08-10 13:47 Computer Science & Computational Number Theory 171 2013-05-14 02:57 Hugh Math 64 2011-01-26 08:45 sghodeif Miscellaneous Math 9 2006-07-19 03:22 Chris Card Math 1 2005-05-26 14:18

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

Sun Nov 28 00:23:26 UTC 2021 up 127 days, 18:52, 0 users, load averages: 1.45, 1.21, 1.13