Given sigma(n)-n, find the smallest possible n

[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?

[science_man_88]

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).

[garambois]

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.
I hope I help you !
Jean-Luc Garambois

[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:

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

(Will modify it a little more later, for example trying a number of "special" small factors first.)

[henryzz]

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:

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

(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?
It is unreadable.
Here is my attempt at making it readable. The way it handles elseifs doesn't lend it to multilines.

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

[mart_r]

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).

[science_man_88]

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:

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

(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:

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])