mersenneforum.org Is a search for aliquot 3-cycles feasible?
 User Name Remember Me? Password
 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,399 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 7×271 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

84A16 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

20C016 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 838410 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

84A16 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.

 Thread Tools

 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 09:27.

Wed Sep 30 09:27:07 UTC 2020 up 20 days, 6:38, 0 users, load averages: 1.58, 1.56, 1.49

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.