Aliquot Termination Question - Largest Prime?

EdH · 2010-04-05, 00:31

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?

TimSorbet · 2010-04-05, 02:22

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.

RichD · 2010-04-05, 03:41

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.

10metreh · 2010-04-05, 07:21

There is a formula for the aliquot sum of a number:

If the prime factorization of N is p^a * q^b * r^c, 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 2^43112609-1.

TimSorbet · 2010-04-05, 11:59

Quote:

Originally Posted by 10metreh

And as an answer to the original post, the largest known prime termination is that of sequence 2^43112609-1.

Nope, I've got a larger one: 2^43112609
It terminates in 2^43112609-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.

EdH · 2010-04-05, 14:57

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, 2^43112609 meets, although, again, not qute what I was interested in. However, I appreciate all the answers and thank you again.

Take Care,
Ed

RichD · 2010-04-06, 00:12

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?

2010-04-05, 00:31	#1
EdH "Ed Hall" Dec 2009 Adirondack Mtns 2⁷×3²×5 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, 07:21	#4
10metreh Nov 2008 2×3³×43 Posts	There is a formula for the aliquot sum of a number: If the prime factorization of N is p^a * q^b * r^c, 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 2^43112609-1. Last fiddled with by 10metreh on 2010-04-05 at 07:30*

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
A new termination below 100k	10metreh	Aliquot Sequences	0	2010-03-11 18:24
Aliquot sequence convergence question	philmoore	Math	3	2009-03-20 19:04
Largest 64 bit prime?	amcfarlane	Math	6	2004-12-26 23:15
need Pentium 4s for 5th largest prime search (largest proth)	wfgarnett3	Lounge	7	2002-11-25 06:34

2010-04-05, 03:41	#3
RichD Sep 2008 Kansas 2×7²×41 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 + p1p2 + 1. Again an even number of odds! (4) With three odd p's the total sum would be p1 + p2 + p3 + p1p2 + p1p3 + p2 p3 + p1p2p3 + 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, 14:57	#6
EdH "Ed Hall" Dec 2009 Adirondack Mtns 2⁷×3²×5 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, 2^43112609 meets, although, again, not qute what I was interested in. However, I appreciate all the answers and thank you again. Take Care, Ed