mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2010-04-05, 00:31   #1
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·3·5·163 Posts
Default 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?
EdH is online now   Reply With Quote
Old 2010-04-05, 02:22   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

2·3·23·31 Posts
Default

Quote:
Originally Posted by EdH View Post
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 View Post
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 Mini-Geek on 2010-04-05 at 02:25
Mini-Geek is online now   Reply With Quote
Old 2010-04-05, 03:41   #3
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

1110010110112 Posts
Default

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.
RichD is offline   Reply With Quote
Old 2010-04-05, 07:21   #4
10metreh
 
10metreh's Avatar
 
Nov 2008

232210 Posts
Default

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
10metreh is offline   Reply With Quote
Old 2010-04-05, 11:59   #5
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

102668 Posts
Default

Quote:
Originally Posted by 10metreh View Post
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 View Post
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 Mini-Geek on 2010-04-05 at 12:22
Mini-Geek is online now   Reply With Quote
Old 2010-04-05, 14:57   #6
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2×3×5×163 Posts
Default

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
EdH is online now   Reply With Quote
Old 2010-04-06, 00:12   #7
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

367510 Posts
Default

Quote:
Originally Posted by Mini-Geek View Post
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?
RichD is offline   Reply With Quote
Reply

Thread Tools


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

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


Fri Sep 30 12:35:39 UTC 2022 up 43 days, 10:04, 0 users, load averages: 1.05, 1.05, 1.03

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.

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