Is a search for aliquot 3-cycles feasible?

schickel · 2013-02-02, 03:46

From Perfect, Amicable and Sociable Numbers by Song Y. Yan comes this, from the chapter Algrebraic Rules for Aliquot k-Cycles:

Quote:

Theorem 4.5.1 If $v,\ u\ \in\ N$ and $u\geq v,\ 2u+1 \equiv 0\ \pmod v$ , then

$\left\{\\ p=2^v\ -\ 1\\ p_1=\frac{(2^{v+1}\ -\ 1)(2^u\ -\ 1)\ +\ 2^{u-v}(2^{u+1}\ -\ 1)}{p}\\ p_2=2^v(p_1\ +\ 2)\ -\ 1\\ p_3=2^v(2^{v+1}\ -\ 1)\ +\ 2^{u+1}\ -\ 1\\ \right.$

are integers. If $p,\ p_1,\ p_2,\ p_3$ are all primes, then

$(m_1,\ m_2,\ m_3)=(2^v\ \cdot \ p\ \cdot\ p_1,\ 2^v\ \cdot\ p_2,\ 2^v\ \cdot\ p_3)$

is an aliquot 3-cycle.

He gives an algorithm to search for aliquot 3-cycles with $i\leq v\leq j,\ v\leq u\leq j$ and $v$ odd prime:

Quote:

for u from i to j do

for v from i to u while $u\geq v$ and $2u+1 \equiv 0$ (mod $v$ ) do
$p=2^v-1$

if $p\ \in\ Primes$ then

$p_1=\frac{(2^{v+1}\ -\ 1)(2^u\ -\ 1)\ +\ 2^{u-v}(2^{u+1}\ -\ 1)}{p}$
$p_2=2^v(p_1\ +\ 2)\ -\ 1$
$p_3=2^v(2^{v+1}\ -\ 1)\ +\ 2^{u+1}\ -\ 1$
if $p_1\ \in\ Primes$
if $p_2\ \in\ Primes$ then
if $p_3\ \in\ Primes$ then
$m_1=2^v\cdot p \cdot p_1$
$m_2=2^v\cdot p_2$
$m_3=2^u\cdot p_3$
print $(m_1,\ m_2,\ m_3)$ is an Aliquot 3-cycle

end.if
end.if
end.if
end.if
end.do

end.do

Right off the bat, I can see one way to speed things up: instead of using u in the outer loop and looping over v while testing for primality, use v as the loop invariant and search over a range of u, since we already know what values of v are going to generate a prime.

The only potential problem I see is a little further down the page where he says

Quote:

Our computation experience shows that there are no values for $u,\ v\leq 10^{10}$ in the present rule which can actually generate an aliquot 3-cycle.

Followed by some near misses where one or two of $p_{1..3}$ are prime. The nearest misses, with 2 primes, are $u=4,\ v=3,\ p=7$ , $u=10,\ v=7,\ p=127$ , and $u=24,\ v=7,\ p=127$ .

R. Gerbicz · 2013-02-03, 01:47

"Is a search for aliquot 3-cycles feasible?"

Heuristics gives O(1/u) probability for each p1,p2,p3 number to be prime for fixed v and O(1/v) for p. So the probability that you will find a chain is (assume that these p,p1,p2,p3 are primes "almost" indepedently) O(1/(u^3*v)) summing this for all (u,v) pairs (use that 2u+1==0 mod v) gives a finite (small) value. This also shows that if there is no chain for very small u,v pairs then it is a hopeless search.

chris2be8 · 2013-02-03, 17:15

Will all aliquot 3-cycles have to meet those criteria? If not what criteria would they meet?

Chris

schickel · 2013-02-07, 11:57

Quote:

Originally Posted by chris2be8

Will all aliquot 3-cycles have to meet those criteria? If not what criteria would they meet?

Chris

I don't know if other criteria are possible. Here are a couple more snippets from the book:

Aliquot k-cycles are defined earlier:

Quote:

Definition 1.1.19 The positive integers $(m_1,\ m_2,\ \cdots,\ m_k)$ form an aliquot k-cycle if they satisfy the following conditions:
$\left\{\\ \sigma(m_1)=m_1+m_2,\\ \sigma(m_2)=m_3+m_3,\\ \cdots\\ \sigma(m_k)=m_k+m_1 \right.$

In chapter 3, Exhaustive Numerical Methods, he discusses this method to search for k-cycles:

Quote:

for $m_1$ from $i$ to $j$ do

$m_2=\sigma(m_1)-m_1$
$m_3=\sigma(m_2)-m_2$
$\cdots$
$m_k=\sigma(m_{k-1})-m_{k-1}$
$m_{k+1}=\sigma(m_{k+1}-m_1$
if $(m_{k+1}=m_1)$ and $(m_1\ \neq\ m_2\ \neq\ \cdots\ \neq m_k)$
then $(m_1,\ m_2,\ \cdots, \ m_k)$ is an aliquot cycle!

end.if

end.do

He then concludes §4.5.1 (quoted earlier) thusly:

Quote:

In our opinion, to find an aliquot 3-cycle is as hard as finding an odd perfect number. In order to find an aliquot 3-cycle (if there exists one), either new stronger algrebraic conditions for the 3-rule or a completely new 3-rule will be needed.

Remark 4.5.2 Although we have not found an aliquot 3-cycle yet, this is probably because that at present we do not have enough computing power, or we have not found a more suitable rule for aliquot 3-cycles. As we have conjectured previously, there should exist at least one aliquot 3-cycle.

(Based on the last update on amicable number searches here, any 3-cycle would have to be $\geq 5\ \cdot\ 10^{12}$ )

science_man_88 · 2013-02-07, 13:25

Quote:

Originally Posted by schickel

From Perfect, Amicable and Sociable Numbers by Song Y. Yan comes this, from the chapter Algrebraic Rules for Aliquot k-Cycles:
He gives an algorithm to search for aliquot 3-cycles with $i\leq v\leq j,\ v\leq u\leq j$ and $v$ odd prime:Right off the bat, I can see one way to speed things up: instead of using u in the outer loop and looping over v while testing for primality, use v as the loop invariant and search over a range of u, since we already know what values of v are going to generate a prime.

The only potential problem I see is a little further down the page where he saysFollowed by some near misses where one or two of $p_{1..3}$ are prime. The nearest misses, with 2 primes, are $u=4,\ v=3,\ p=7$ , $u=10,\ v=7,\ p=127$ , and $u=24,\ v=7,\ p=127$ .

lowest u can be appears to be v+n such that 2n+1=v we could substitute and possibly come up with properties of v.

$p = 2^v-1$
$p_1 = \frac{(2^{v+1}-1)(2^{v+n}-1)+2^n(2^{v+n+1}-1)}{p}$
$p_2 = 2^v(p_1+2)-1$
$p_3 = 2^v(2^{v+1}-1)+2^{v+n+1}-1$

so is there anything that can be said of v in this situation ? n ? ( and yes I know n could simplify it more, or at least make it down to one variable)

science_man_88 · 2013-02-07, 17:01

$p = 2^{2n+1}-1$
$p_1 = \frac{(2^{2n+2}-1)(2^{3n+1}-1)+2^n(2^{3n+2}-1)}{2^{2n+1}-1}$
$p_2 = 2^{2n+1}(\frac{(2^{2n+2}-1)(2^{3n+1}-1)+2^n(2^{3n+2}-1)}{2^{2n+1}-1}+2)-1$
$p_3 = 2^{2n+1}(2^{2n+2}-1)+2^{3n+2}-1$

is what I get reducing to just n in all equations.

schickel · 2013-02-08, 01:27

Quote:

Originally Posted by science_man_88

lowest u can be appears to be v+n such that 2n+1=v we could substitute and possibly come up with properties of v.

$p = 2^v-1$
so is there anything that can be said of v in this situation ?

Quote:

Originally Posted by science_man_88

$p = 2^{2n+1}-1$

Think again. What do we know about p that tells us about v?

Hint: If [i]p[/i] is prime we [u]know[/u] that [i]v[/i] is [u]one of only [STRIKE]47[/STRIKE] 48 values![/u]

science_man_88 · 2013-02-08, 01:33

Quote:

Originally Posted by schickel

Think again. What do we know about p that tells us about v?

Hint: If [I]p[/I] is prime we [U]know[/U] that [I]v[/I] is [U]one of only [STRIKE]47[/STRIKE] 48 values![/U]

known values unless you prove there are no more mersenne primes my basics still stand.

2013-02-03, 01:47	#2
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 1568₁₀ Posts	"Is a search for aliquot 3-cycles feasible?" Heuristics gives O(1/u) probability for each p1,p2,p3 number to be prime for fixed v and O(1/v) for p. So the probability that you will find a chain is (assume that these p,p1,p2,p3 are primes "almost" indepedently) O(1/(u^3v)) summing this for all (u,v) pairs (use that 2u+1==0 mod v) gives a finite (small) value. This also shows that if there is no chain for very small u,v pairs then it is a hopeless search. Last fiddled with by R. Gerbicz on 2013-02-03 at 01:49*

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Aliquot cycles search, the state of the art.	Drdmitry	Aliquot Sequences	124	2017-07-02 02:48
Search of all even-15-digit Aliquot cycles	Drdmitry	Aliquot Sequences	25	2016-12-16 15:26
Program for searching all odd-16-digit Aliquot cycles	Drdmitry	Aliquot Sequences	302	2016-05-11 02:17
Small search of cycles with odd and even elements	Drdmitry	Aliquot Sequences	0	2011-12-14 13:50
Jan Munch Pedersen's Tables of Aliquot Cycles	R. Gerbicz	Math	0	2010-07-01 12:30

2013-02-03, 17:15	#3
chris2be8 Sep 2009 2²·11·53 Posts	Will all aliquot 3-cycles have to meet those criteria? If not what criteria would they meet? Chris

2013-02-07, 17:01	#6
science_man_88 "Forget I exist" Jul 2009 Dumbassville 20C0₁₆ Posts	$p = 2^{2n+1}-1$ $p_1 = \frac{(2^{2n+2}-1)(2^{3n+1}-1)+2^n(2^{3n+2}-1)}{2^{2n+1}-1}$ $p_2 = 2^{2n+1}(\frac{(2^{2n+2}-1)(2^{3n+1}-1)+2^n(2^{3n+2}-1)}{2^{2n+1}-1}+2)-1$ $p_3 = 2^{2n+1}(2^{2n+2}-1)+2^{3n+2}-1$ is what I get reducing to just n in all equations.