20130720, 11:34  #1 
Dec 2008
you know...around...
2×443 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)n1p) 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? 
20130720, 20:35  #2  
"Forget I exist"
Jul 2009
Dartmouth NS
2×5^{2}×13^{2} Posts 
Quote:
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 y1 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). 

20130722, 09:50  #3  
"Garambois JeanLuc"
Oct 2011
France
1,193 Posts 
Quote:
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 ! JeanLuc Garambois 

20130723, 18:13  #4 
Dec 2008
you know...around...
2·443 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<3u<1,break());t=0;if(u==0,t=1);if(u>0,t=u);r=0;if(t==1,q=2;while(!ispseudoprime(nq1),q=nextprime(q+1);if(q>n,break()));r=q*(nq1),if(u==1,t=n%2);while(r<=0&&u!=0&&t<sqrt(n),if(u==1,t+=2);s=sigma(t);m=factor((st)*(ns)+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)/(st);p=(ns*(q+1))/((st)*q+s);if(qfloor(q)==0&&ispseudoprime(floor(q))&&pfloor(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(n1),r=(n1)*(n1));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 nq1 is prime, optional u for additional factors N=upq; for u=1, searches through u=2...inf until a solution is found 
20130723, 18:32  #5  
Just call me Henry
"David"
Sep 2007
Liverpool (GMT/BST)
17F1_{16} Posts 
Quote:
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<3u<1, break() ); t=0; if(u==0, t=1 ); if(u>0, t=u ); r=0; if(t==1, q=2; while(!ispseudoprime(nq1), q=nextprime(q+1); if(q>n, break() ) ); r=q*(nq1), if(u==1, t=n%2 ); while(r<=0&&u!=0&&t<sqrt(n), if(u==1, t+=2 ); s=sigma(t); m=factor((st)*(ns)+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)/(st); p=(ns*(q+1))/((st)*q+s); if(qfloor(q)==0&&ispseudoprime(floor(q))&&pfloor(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(n1), r=(n1)*(n1)); 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 nq1 is prime, optional u for additional factors N=upq; for u=1, searches through u=2...inf until a solution is found 

20130723, 19:50  #6 
Dec 2008
you know...around...
376_{16} 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). 
20130723, 20:50  #7  
"Forget I exist"
Jul 2009
Dartmouth NS
20402_{8} Posts 
Quote:
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(y1)); 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(#a1,n,a[n+1]) Last fiddled with by science_man_88 on 20130723 at 20:54 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Iteration of (sigma(n)+phi(n))/2  sean  Factoring  2  20170918 15:39 
Where can I find a Reverse and Add program? I can't find any!  Stargate38  Programming  18  20150710 06:08 
Spooky sigma values  lavalamp  Software  2  20100824 15:22 
Could a Distributed Computing approach help find the smallest Brier number?  jasong  Math  5  20070529 13:30 
Can you find the smallest number?  Fusion_power  Puzzles  8  20031118 19:36 