20110819, 06:09  #1 
May 2011
France
7×23 Posts 
New σ for Aliquot
In an aliquot research you have two step:
1 Facrotize N 2Compute with the prime factors the sum of the divisors(New value for N)until N=1; For the step 2 we use a polynome : Let power be a standard exponanciation we give a and b ans the answer is a^b Sigma:= power (a,b+1)+1) div a1 Exemple 8244565422068579772 = 2^2 * 3 * 7 * 98149588357959283 we can write 2,2 3,1 7,1 98149588357959283,1 Sigma :=1; for i:=1 to 4 do Sigma:= sigma *power (a,b+1)+1) div a1 Sigma:=Sigma*n you have to compute the square of 98149588357959283 and then div the square by 98149588357959282 Just imagine that 98149588357959283, fas 200 digits the square will have 400 digits and the result of the div 200 digit In fact when the power is one !+1) = two you have directly the sum of the divisor : just add 1 to the factor If you number have 98149588357959283 like factot the the sum of divisors for this factor will be 98149588357959283+1=98149588357959284 for i:=1 to 4 do if b=1 then Sigma:= sigma *(a+1) else Sigma:= sigma *power (a,b+1)+1) div a1 With other powers you have others computations but in Aliquot just tthe power 1 is necessary. In our sample 3 factors are power 1 and it's also easy to commute more faster the 2 power With this method you have only one point to work: factotize N John Last fiddled with by JohnFullspeed on 20110819 at 06:10 
20110819, 11:52  #2 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
17·251 Posts 

20110819, 12:42  #3 
Mar 2006
Germany
2^{3}×5×71 Posts 
I think what he means is:
The formula for the Sum of divisors for is: Sigma = . But for example if and , you don't have to calculate the value , because for an exponent = 1, the value ist primefactor + 1, so in this example = 18. So, instead of looping over all primefactors and calculating the value strictly with that formula, you can do like: Calculating Sum of divisors: Code:
SUM = 1 Loop over all primefactors if exponent == 1 value = primefactor + 1 else value = (primefactor ^ (exponent+1) 1) div (primefactor  1)) SUM = SUM * value endloop But the most time is spent in finding the primefactors so this is negligible. 
20110819, 15:23  #4 
"Robert Gerbicz"
Oct 2005
Hungary
562_{16} Posts 
There is also known for ages a division free fast method (for every e) to calculate (p^e1)/(p1). So there is nothing new from JohnFullspeed.

20110819, 15:58  #5 
May 2011
France
161_{10} Posts 
yes
Tbhis id to goal= Sur the sigma compiutation is small. The time is spend in the factorisation
but when yo look a dfacrorisation of a aliquyoit value You see that you have 2..5 smalls factotrs 2,3,5,7,11... and a big one.. Soo in fact it's eay tu find the smalll factor and to test directluy the primarity samppe : You divide you umber with 100milliions otdf Prime number(you have 200 M in the data base) You need fews secondes( less 5) and after a strong primarity test (rabbin or JPSW i/e here you have the iteration 176 of 276;;;; 1073 . 2456947364948302297366000713024035345443479605944542725601064789572027245204254426895325680697020863926 = 2 * 3 * 7 * 31^2 * 71 * 857363174868950887903208607532826283208609829614015248480499643567972959227531134394059703589913 to facorise you have 100 Millions of div with a small divisor 31 bits and affer a primariti test for 857363174868950887903208607532826283208609829614015248480499643567972959227531134394059703589913 So working on primetest seems useful than the factotisatuon TIPS Speed a mob b =0 (with a et b as big as possible) on your computer if you want a modulo basikely you make the div and get the rest. Now look a div The computation is long to get the quotient the moduli is automatic So for big number (more 10^19 ) the computer doesin't know hos to do: it'ds the coder but you doesn't need the quotient of th division so I give you the sppeder modulo of the univers: speeder than The Faucon Miillénium and Superman if you want to know if D= B is a divisor of A make B greater than A (shift) while B>A do B:=B SHL; B:= B SHR 1 repeat If A> B then A= AB B:=B shr 1 until A< D Return a=0; a is the modulo using shifth not div 10 win multiply substract B from A In binary the new A is always smaller then Bnotin Base 10 (I can explain you how optimize this code....) you make on shift for each bit of b and a sub for ach bit of B set to one... John 
20110819, 16:09  #6  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
Quote:


20110819, 19:43  #7  
May 2011
France
7·23 Posts 
I don't understand
Quote:
to compute ((P^2)1) div p1 so a mul a sub a sub and a div I do a add I never see this tips do you see that if e=2 then the calcil is p*(p+1)+1???? SUM = 1 Loop over all primefactors if exponent == 1 value = primefactor + 1 if exponent == 2 value = primefactor *(primefactor + 1)+1 else value = (primefactor ^ (exponent+1) 1) div (primefactor  1)) SUM = SUM * value You can win the exponent+1...... @ science_man_88 I don't now PARI but it seems to me that the break is for the power of the factor not the mod But I perhaps make a mistake John 

20110819, 20:15  #8  
"Robert Gerbicz"
Oct 2005
Hungary
2·13·53 Posts 
Quote:
sigma(p^e)=(p^(e+1)1)/(p1) without any division: Code:
S(p,e)=v=binary(e);L=length(v);r=1;T=1;\ for(i=1,L,if(v[i]==0,r+=T*rT;T*=T,r+=T*r*p;T*=T*p));return(r) Last fiddled with by R. Gerbicz on 20110819 at 20:37 

20110819, 20:24  #9  
"Robert Gerbicz"
Oct 2005
Hungary
2·13·53 Posts 
Quote:
Code:
S(p,e)=r=1;for(i=1,e,r=r*p+1);return(r) Last fiddled with by R. Gerbicz on 20110819 at 20:44 

20110820, 06:16  #10 
May 2011
France
7×23 Posts 
Sigma
Without divion.
No matter for me : i don't have a CISC for me div;add,mul are only 1 cycle so less instruction= less time John thanks for the others methods I study them.... But wwhen I ask for other methods I fave no repons... Jhon 
20110820, 07:43  #11  
"Robert Gerbicz"
Oct 2005
Hungary
562_{16} Posts 
Quote:
Maybe in your dream. Read some math and English books. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Broken aliquot sequences  schickel  FactorDB  18  20130612 16:09 
aliquot escape  firejuggler  Aliquot Sequences  26  20120119 08:15 
aliquot and mersenne  firejuggler  Aliquot Sequences  1  20100601 23:47 
serious bug in aliquot.ub  Andi47  Aliquot Sequences  3  20090308 10:18 
Aliquot Sum Function  grandpascorpion  Math  5  20080206 15:12 