mersenneforum.org Aliquot Termination Question - Largest Prime?
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-05, 00:31 #1 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 5×1,051 Posts Aliquot Termination Question - Largest Prime? Sorry if I should be able to easily locate this, but I'm wondering what the largest prime termination is for any sequence. All the curves I've reviewed seem to decrease considerably prior to terminating in a prime. Is there a mathematical explanation for this behavior, other than probability?
2010-04-05, 02:22   #2
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts

Quote:
 Originally Posted by EdH Sorry if I should be able to easily locate this, but I'm wondering what the largest prime termination is for any sequence.
This is far from conclusive, but see http://factordb.com/search.php?so=1&...limit=100&ew=1
The largest of those that actually terminates in a prime (darn bugs/hacks...) is 1923540, with a P14. The largest one that started below 1000000 is 891210, with a P10.
Quote:
 Originally Posted by EdH All the curves I've reviewed seem to decrease considerably prior to terminating in a prime. Is there a mathematical explanation for this behavior, other than probability?
Yes (well, it's still about probability, but of a different sort than the chances of e.g. a 100 digit number being prime). IIRC, to become odd, (and so have a chance of terminating in a prime besides 2) the line (besides the 2^x factor) needs to be a square (whether p^2 or p^4*q^2 or what). This grows extremely unlikely as the sequence grows past 5-20 digits. Hence nearly all prime terminations happen when the sequence is very small.

Last fiddled with by TimSorbet on 2010-04-05 at 02:25

 2010-04-05, 03:41 #3 RichD     Sep 2008 Kansas 25·7·17 Posts I questioned the same thing. Why is a multiple of 2 always in the next factorization sequence? Thereby the sum being (most likely) even. So I put pen to paper and came up with the following - FWIW. Assume the factors are of the form 2^n * p1 * p2 * ..., with n > 0 and possible p's being an odd number from 3 to X. It doesn't make any difference if pX is squared, it's just another "odd" p in this explanation. Any factor or multiple of 2 will always be even. These can be excluded. The need is to focus on the odd p's to see if the total sum will have a chance of being odd (and possible prime). Assuming the sequence has one pX then the sum of the odd factors will be p1 + 1, or an even number. Bummer! (2) Let's assume the sequence has two pX. The sum would be p1 + p2 + p1*p2 + 1. Again an even number of odds! (4) With three odd p's the total sum would be p1 + p2 + p3 + p1*p2 + p1*p3 + p2 *p3 + p1*p2*p3 + 1. Darn, again an even number of odd primes! (8) I'm sure you can see the sequence by now. Not until the numbers approach a very small number (as Mini-Geek pointed out) is there a chance of a prime. The best down driver is 2^1 with no small p. This will cut the next number nearly in half. This exercise is left to the reader.
 2010-04-05, 07:21 #4 10metreh     Nov 2008 2·33·43 Posts There is a formula for the aliquot sum of a number: If the prime factorization of N is pa * qb * rc, with p, q, r etc. all prime, then its aliquot sum is: $\frac{p^{a+1}-1}{p-1}\ *\ \frac{q^{b+1}-1}{q-1}\ *\ \frac{r^{c+1}-1}{r-1}\ *\ . . . \ -\ N$ From this it is easy to prove many results about sums of divisors, such as the (very obvious) even number one. Another one that can be easily proved with this formula is that when a term in a sequence has a factor of 2 raised to an even power but no factor of 3, then the next term can acquire a factor of 3 if and only if there is no prime factor (other than 2) of the form 3n-1. This is left as an exercise to the reader. And as an answer to the original post, the largest known prime termination is that of sequence 243112609-1. Last fiddled with by 10metreh on 2010-04-05 at 07:30
2010-04-05, 11:59   #5
TimSorbet
Account Deleted

"Tim Sorbera"
Aug 2006
San Antonio, TX USA

11·389 Posts

Quote:
 Originally Posted by 10metreh And as an answer to the original post, the largest known prime termination is that of sequence 243112609-1.
Nope, I've got a larger one: 243112609
It terminates in 243112609-1 at index 1.
(Of course, the aliquot sum of p2^n is p2^n-1.)

But I think we were all referring to examples that aren't that trivial...

10metreh: I thought we were talking about the highest prime, not the highest sequence.
Mini-Geek: He did indeed refer to "
the largest prime termination", but you said "is that of sequence ...", so I thought you were talking about the largest sequence, not the largest prime. On closer reading, and with your response, it seems I was mistaken.

Quote:
 Originally Posted by RichD The best down driver is 2^1 with no small p.
Except for odd numbers, of course. They drop rather quickly.

Last fiddled with by TimSorbet on 2010-04-05 at 12:22

 2010-04-05, 14:57 #6 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 10100100001112 Posts Thank you for the replies. I think I have a handle on it. And, I do realize that any large prime would equal itself, but I was more so thinking of a sequence as having more than one iteration, a requirement which, of course, 243112609 meets, although, again, not qute what I was interested in. However, I appreciate all the answers and thank you again. Take Care, Ed
2010-04-06, 00:12   #7
RichD

Sep 2008
Kansas

1110111000002 Posts

Quote:
 Originally Posted by Mini-Geek Except for odd numbers, of course. They drop rather quickly.
Ah, yes. Especially when p1 and p2 are not "near" each other.
(Also meaning p1 can not be squared.)

How often does this appear in the wild, especially after index 10?

 Similar Threads Thread Thread Starter Forum Replies Last Post dabaichi News 571 2020-10-26 11:02 10metreh Aliquot Sequences 0 2010-03-11 18:24 philmoore Math 3 2009-03-20 19:04 amcfarlane Math 6 2004-12-26 23:15 wfgarnett3 Lounge 7 2002-11-25 06:34

All times are UTC. The time now is 04:58.

Sun Feb 5 04:58:07 UTC 2023 up 171 days, 2:26, 1 user, load averages: 1.20, 0.88, 0.87