mersenneforum.org Given sigma(n)-n, find the smallest possible n
 Register FAQ Search Today's Posts Mark Forums Read

 2013-07-20, 11:34 #1 mart_r     Dec 2008 you know...around... 3·229 Posts Given sigma(n)-n, find the smallest possible n For example, for large enough odd sigma(n)-n, it's quite easy to find a possible n. It doesn't take long to find a prime p such that q=(sigma(n)-n-1-p) is also prime and n=p*q is found. The problem now is determining whether this is the smallest solution (mostly it isn't), and how efficiently can it be found?
2013-07-20, 20:35   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts

Quote:
 Originally Posted by mart_r For example, for large enough odd sigma(n)-n, it's quite easy to find a possible n. It doesn't take long to find a prime p such that q=(sigma(n)-n-1-p) is also prime and n=p*q is found. The problem now is determining whether this is the smallest solution (mostly it isn't), and how efficiently can it be found?
Clearly I'm no expert, but I have made a script to look backwards before, that is:
y=sigma(n)-n knowing y solve for possible n so I agree solving for any n can be done simple enough ( though pari can only go so far it seems) really solving for smallest n should be possible as soon as we can limit down the amount of partitions of y that are usable ( as I have tried once they have to have properties of a list of proper divisors so primes need to be in the list or it doesn't work, 1 is a divisor of every natural so you can take it to partitions of y-1 that don't include 1,that include naturals only divisible by the primes in that partition, but don't include powers of those primes that will bring the top number to less than n ( and clearly the top prime is less than y to fit into a partition of y).

2013-07-22, 09:50   #3
garambois

"Garambois Jean-Luc"
Oct 2011
France

24×43 Posts

Quote:
 Originally Posted by mart_r For example, for large enough odd sigma(n)-n, it's quite easy to find a possible n. It doesn't take long to find a prime p such that q=(sigma(n)-n-1-p) is also prime and n=p*q is found. The problem now is determining whether this is the smallest solution (mostly it isn't), and how efficiently can it be found?

Hello,
I work on this problem and you can see my results on the link :
http://www.aliquotes.com/nombre_ante...aliquotes.html
But I'm sorry, it's in french !
Exactly, I want to find the number of aliquot antecedents of the integers (odd and even). My program is written in Mathematica langage and it is very fast. This program finds all the aliquot antecedents of the integers, but I only count them for each integer and not memorize them.
You can also dowload some files on my aliquot sequences data base :
http://www.aliquotes.com/aliquote_base.htm
For information, since february 23th 2013, I'm computing a big program to find the number of aliquot antecedents of the integers from 1 to 50 000 000. I think that the end of this very long calcul will be in january 2014. And at this date, I will put the result on the same internet link.
Jean-Luc Garambois

 2013-07-23, 18:13 #4 mart_r     Dec 2008 you know...around... 3·229 Posts Okay, there are one or two things that I didn't think of off the top of my head. Thanks. This is a broader approach to the problem than I had in mind, I was more concerned about finding one (preferably the smallest) solution to a rather large (>10^12) given number. Anyway the program I compiled during the weekend seems to work quite nicely already, though it still won't find a good solution for, say, n=Xpqr for large primes p,q,r and X a small prime or a product of small primes. This is how far I've gotten on my own: Code: ai(n,u)=if(n<3||u<-1,break());t=0;if(u==0,t=1);if(u>0,t=u);r=0;if(t==1,q=2;while(!ispseudoprime(n-q-1),q=nextprime(q+1);if(q>n,break()));r=q*(n-q-1),if(u==-1,t=n%2);while(r<=0&&u!=0&&t0,x=#v)));if(u>0,u=0)));if(u==-1&&r==0&&isprime(n-1),r=(n-1)*(n-1));if(r>0,print("solution: "r);print(factor(r)),print("no solution u*p*q for u="t)) \\ finds N such that sigma(N)-N=n via N=pq if n-q-1 is prime, optional u for additional factors N=upq; for u=-1, searches through u=2...inf until a solution is found (Will modify it a little more later, for example trying a number of "special" small factors first.)
2013-07-23, 18:32   #5
henryzz
Just call me Henry

"David"
Sep 2007
Cambridge (GMT/BST)

10111001101002 Posts

Quote:
 Originally Posted by mart_r Okay, there are one or two things that I didn't think of off the top of my head. Thanks. This is a broader approach to the problem than I had in mind, I was more concerned about finding one (preferably the smallest) solution to a rather large (>10^12) given number. Anyway the program I compiled during the weekend seems to work quite nicely already, though it still won't find a good solution for, say, n=Xpqr for large primes p,q,r and X a small prime or a product of small primes. This is how far I've gotten on my own: Code: ai(n,u)=if(n<3||u<-1,break());t=0;if(u==0,t=1);if(u>0,t=u);r=0;if(t==1,q=2;while(!ispseudoprime(n-q-1),q=nextprime(q+1);if(q>n,break()));r=q*(n-q-1),if(u==-1,t=n%2);while(r<=0&&u!=0&&t0,x=#v)));if(u>0,u=0)));if(u==-1&&r==0&&isprime(n-1),r=(n-1)*(n-1));if(r>0,print("solution: "r);print(factor(r)),print("no solution u*p*q for u="t)) \\ finds N such that sigma(N)-N=n via N=pq if n-q-1 is prime, optional u for additional factors N=upq; for u=-1, searches through u=2...inf until a solution is found (Will modify it a little more later, for example trying a number of "special" small factors first.)
Why does pari have to encourage one line of code?
Here is my attempt at making it readable. The way it handles elseifs doesn't lend it to multilines.
Code:
ai(n,u)=
if(n<3||u<-1,
break()
);
t=0;
if(u==0,
t=1
);
if(u>0,
t=u
);
r=0;
if(t==1,
q=2;
while(!ispseudoprime(n-q-1),
q=nextprime(q+1);
if(q>n,
break()
)
);
r=q*(n-q-1),
if(u==-1,
t=n%2
);
while(r<=0&&u!=0&&t<sqrt(n),
if(u==-1,
t+=2
);
s=sigma(t);
m=factor((s-t)*(n-s)+s*s);
v=[1];
for(z=1,m[1,2],
v=concat(v,m[1,1]^z)
);
for(y=2,#m[,1],
w=#v;
for(z=1,m[y,2],
for(x=1,w,
v=concat(v,v[x]*m[y,1]^z)
)
)
);
for(x=1,#v,
q=(v[x]-s)/(s-t);
p=(n-s*(q+1))/((s-t)*q+s);
if(q-floor(q)==0&&ispseudoprime(floor(q))&&p-floor(p)==0&&ispseudoprime(p),
r=t*p*q;
if(sigma(r)-r!=n,
r=0
);
if(r>0,
x=#v
)
)
);
if(u>0,
u=0
)
)
);
if(u==-1&&r==0&&isprime(n-1),
r=(n-1)*(n-1));
if(r>0,
print("solution: "r);
print(factor(r)),
print("no solution u*p*q for u="t)
)
\\ finds N such that sigma(N)-N=n via N=pq if n-q-1 is prime, optional u for additional factors N=upq; for u=-1, searches through u=2...inf until a solution is found

 2013-07-23, 19:50 #6 mart_r     Dec 2008 you know...around... 3·229 Posts Oops, sorry. And thanks, henryzz. I type most of my GP programs (which aren't many) in one line because they hardly exceed 100 characters. It's probably because I'm used to compile similarly complicated Excel formulae almost every day (and some of them should actually be unreadable).
2013-07-23, 20:50   #7
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by mart_r Okay, there are one or two things that I didn't think of off the top of my head. Thanks. This is a broader approach to the problem than I had in mind, I was more concerned about finding one (preferably the smallest) solution to a rather large (>10^12) given number. Anyway the program I compiled during the weekend seems to work quite nicely already, though it still won't find a good solution for, say, n=Xpqr for large primes p,q,r and X a small prime or a product of small primes. This is how far I've gotten on my own: Code: ai(n,u)=if(n<3||u<-1,break());t=0;if(u==0,t=1);if(u>0,t=u);r=0;if(t==1,q=2;while(!ispseudoprime(n-q-1),q=nextprime(q+1);if(q>n,break()));r=q*(n-q-1),if(u==-1,t=n%2);while(r<=0&&u!=0&&t0,x=#v)));if(u>0,u=0)));if(u==-1&&r==0&&isprime(n-1),r=(n-1)*(n-1));if(r>0,print("solution: "r);print(factor(r)),print("no solution u*p*q for u="t)) \\ finds N such that sigma(N)-N=n via N=pq if n-q-1 is prime, optional u for additional factors N=upq; for u=-1, searches through u=2...inf until a solution is found (Will modify it a little more later, for example trying a number of "special" small factors first.)
I should be thanking you, it was trying to come up with a "better" ali after looking and responding to this thread that I realized a property of partitions() I hadn't before allowing a partial solution up to a given number ( like vecmax would) and it allowed me to practice with select() as well.

here's what I came up with:

Code:
ali2000(y)=
a=select(v->isprime(v[1])==1 &&
#vecsort(v,,8)==#v &&
#setminus(Vec(divisors(v[#v])),Vec(v))==1,
partitions(y-1));
for(x=1,#a,
if(sigma(a[x][1]*a[x][#a[x]])-(a[x][1]*a[x][#a[x]])==y,
a[x]=a[x][1]*a[x][#a[x]],
a[x]=0)
);
a=vecsort(a,,8);
a=vector(#a-1,n,a[n+1])

Last fiddled with by science_man_88 on 2013-07-23 at 20:54

 Similar Threads Thread Thread Starter Forum Replies Last Post sean Factoring 2 2017-09-18 15:39 Stargate38 Programming 18 2015-07-10 06:08 lavalamp Software 2 2010-08-24 15:22 jasong Math 5 2007-05-29 13:30 Fusion_power Puzzles 8 2003-11-18 19:36

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

Tue Dec 7 18:30:41 UTC 2021 up 137 days, 12:59, 2 users, load averages: 1.30, 1.48, 1.49