mersenneforum.org Is a search for aliquot 3-cycles feasible?
 Register FAQ Search Today's Posts Mark Forums Read

2013-02-02, 03:46   #1
schickel

"Frank <^>"
Dec 2004
CDP Janesville

2·1,061 Posts
Is a search for aliquot 3-cycles feasible?

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 dofor 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$ thenif $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.ifend.ifend.ifend.ifend.doend.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$.

 2013-02-03, 01:47 #2 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 1,493 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^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. Last fiddled with by R. Gerbicz on 2013-02-03 at 01:49
 2013-02-03, 17:15 #3 chris2be8     Sep 2009 41768 Posts Will all aliquot 3-cycles have to meet those criteria? If not what criteria would they meet? Chris
2013-02-07, 11:57   #4
schickel

"Frank <^>"
Dec 2004
CDP Janesville

2×1,061 Posts

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}$)

2013-02-07, 13:25   #5
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

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)

Last fiddled with by science_man_88 on 2013-02-07 at 13:36

 2013-02-07, 17:01 #6 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 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.
2013-02-08, 01:27   #7
schickel

"Frank <^>"
Dec 2004
CDP Janesville

2·1,061 Posts

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]

2013-02-08, 01:33   #8
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

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.

 Similar Threads Thread Thread Starter Forum Replies Last Post Drdmitry Aliquot Sequences 124 2017-07-02 02:48 Drdmitry Aliquot Sequences 25 2016-12-16 15:26 Drdmitry Aliquot Sequences 302 2016-05-11 02:17 Drdmitry Aliquot Sequences 0 2011-12-14 13:50 R. Gerbicz Math 0 2010-07-01 12:30

All times are UTC. The time now is 05:56.

Sat Oct 16 05:56:03 UTC 2021 up 85 days, 25 mins, 0 users, load averages: 1.44, 1.31, 1.17