mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2013-02-02, 03:46   #1
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

209810 Posts
Question 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\{\\<br />
p=2^v\ -\ 1\\<br />
p_1=\frac{(2^{v+1}\ -\ 1)(2^u\ -\ 1)\ +\ 2^{u-v}(2^{u+1}\ -\ 1)}{p}\\<br />
p_2=2^v(p_1\ +\ 2)\ -\ 1\\<br />
p_3=2^v(2^{v+1}\ -\ 1)\  +\  2^{u+1}\ -\ 1\\<br />
\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.
schickel is offline   Reply With Quote
Old 2013-02-03, 01:47   #2
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

26028 Posts
Default

"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
R. Gerbicz is offline   Reply With Quote
Old 2013-02-03, 17:15   #3
chris2be8
 
chris2be8's Avatar
 
Sep 2009

23×239 Posts
Default

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

Chris
chris2be8 is offline   Reply With Quote
Old 2013-02-07, 11:57   #4
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

209810 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
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\{\\<br />
\sigma(m_1)=m_1+m_2,\\<br />
\sigma(m_2)=m_3+m_3,\\<br />
\cdots\\<br />
\sigma(m_k)=m_k+m_1<br />
\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})
schickel is offline   Reply With Quote
Old 2013-02-07, 13:25   #5
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by schickel View Post
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
science_man_88 is offline   Reply With Quote
Old 2013-02-07, 17:01   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

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.
science_man_88 is offline   Reply With Quote
Old 2013-02-08, 01:27   #7
schickel
 
schickel's Avatar
 
"Frank <^>"
Dec 2004
CDP Janesville

2×1,049 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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 View Post
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]
schickel is offline   Reply With Quote
Old 2013-02-08, 01:33   #8
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by schickel View Post
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.
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


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

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

Thu Oct 22 18:05:09 UTC 2020 up 42 days, 15:16, 2 users, load averages: 2.75, 2.96, 2.85

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.