mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2013-07-20, 11:34   #1
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

60810 Posts
Default 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?
mart_r is offline   Reply With Quote
Old 2013-07-20, 20:35   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by mart_r View Post
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).
science_man_88 is offline   Reply With Quote
Old 2013-07-22, 09:50   #3
garambois
 
garambois's Avatar
 
Oct 2011

5578 Posts
Default

Quote:
Originally Posted by mart_r View Post
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
garambois is offline   Reply With Quote
Old 2013-07-23, 18:13   #4
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

25·19 Posts
Default

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&&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.)
mart_r is offline   Reply With Quote
Old 2013-07-23, 18:32   #5
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

34·71 Posts
Default

Quote:
Originally Posted by mart_r View Post
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&&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.
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
henryzz is offline   Reply With Quote
Old 2013-07-23, 19:50   #6
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

25·19 Posts
Default

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).
mart_r is offline   Reply With Quote
Old 2013-07-23, 20:50   #7
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by mart_r View Post
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&&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:

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
science_man_88 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Iteration of (sigma(n)+phi(n))/2 sean Factoring 2 2017-09-18 15:39
Where can I find a Reverse and Add program? I can't find any! Stargate38 Programming 18 2015-07-10 06:08
Spooky sigma values lavalamp Software 2 2010-08-24 15:22
Could a Distributed Computing approach help find the smallest Brier number? jasong Math 5 2007-05-29 13:30
Can you find the smallest number? Fusion_power Puzzles 8 2003-11-18 19:36

All times are UTC. The time now is 02:20.

Sat Nov 28 02:20:39 UTC 2020 up 78 days, 23:31, 3 users, load averages: 1.09, 1.28, 1.21

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.