 mersenneforum.org New σ for Aliquot
 Register FAQ Search Today's Posts Mark Forums Read  2011-08-19, 06:09 #1 JohnFullspeed   May 2011 France 7·23 Posts New σ for Aliquot In an aliquot research you have two step: 1- Facrotize N 2-Compute 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 a-1 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 a-1 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 a-1 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 2011-08-19 at 06:10   2011-08-19, 11:52 #2 Mini-Geek Account Deleted   "Tim Sorbera" Aug 2006 San Antonio, TX USA 426710 Posts    2011-08-19, 12:42 #3 kar_bon   Mar 2006 Germany 22·23·31 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 This will save some time in the calculations of the sum of divisors. But the most time is spent in finding the primefactors so this is negligible.   2011-08-19, 15:23   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

23·3·59 Posts Quote:
 Originally Posted by kar_bon This will save some time in the calculations of the sum of divisors. But the most time is spent in finding the primefactors so this is negligible.
There is also known for ages a division free fast method (for every e) to calculate (p^e-1)/(p-1). So there is nothing new from JohnFullspeed.   2011-08-19, 15:58 #5 JohnFullspeed   May 2011 France A116 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= A-B 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   2011-08-19, 16:09   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

202618 Posts Quote:
 Originally Posted by JohnFullspeed 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= A-B 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
problem return in some languages ( at least in PARI script) terminates the code and stops it running so until A<D break() is almost as useful.   2011-08-19, 19:43   #7
JohnFullspeed

May 2011
France

101000012 Posts I don't understand

Quote:
 Originally Posted by R. Gerbicz There is also known for ages a division free fast method (for every e) to calculate (p^e-1)/(p-1). So there is nothing new from JohnFullspeed.
The calcul is not (p^e-1)/(p-1) but(P^e+1)+1 div (p-1)let e=1
to compute ((P^2)-1) div p-1 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   2011-08-19, 20:15   #8
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

23×3×59 Posts Quote:
 Originally Posted by JohnFullspeed I do a add I never see this tips do you see that if e=2 then the calcil is p*(p+1)+1???? ... John
I don't understand every sentences from you, but anyway here it is my code to get
sigma(p^e)=(p^(e+1)-1)/(p-1) 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*r-T;T*=T,r+=T*r*p;T*=T*p));return(r)
There is only multiplication, addition/subtraction and no division.

Last fiddled with by R. Gerbicz on 2011-08-19 at 20:37   2011-08-19, 20:24   #9
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

23×3×59 Posts Quote:
 Originally Posted by R. Gerbicz Code: S(p,e)=v=binary(e);L=length(v);r=1;T=1;\ for(i=1,L,if(v[i]==0,r+=T*r-T;T*=T,r+=T*r*p;T*=T*p));return(r) There is only multiplication, addition/subtraction and no division.
Another method:
Code:
S(p,e)=r=1;for(i=1,e,r=r*p+1);return(r)
This is also good, but the problem with it, that it is much slower than the other methods if "e" is large.

Last fiddled with by R. Gerbicz on 2011-08-19 at 20:44   2011-08-20, 06:16 #10 JohnFullspeed   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   2011-08-20, 07:43   #11
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

101100010002 Posts Quote:
 Originally Posted by JohnFullspeed 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
Division in one cycle? For arbitrary large p values, say for p=10^999+7 ?

Read some math and English books.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post schickel FactorDB 18 2013-06-12 16:09 firejuggler Aliquot Sequences 26 2012-01-19 08:15 firejuggler Aliquot Sequences 1 2010-06-01 23:47 Andi47 Aliquot Sequences 3 2009-03-08 10:18 grandpascorpion Math 5 2008-02-06 15:12

All times are UTC. The time now is 19:24.

Mon Nov 23 19:24:04 UTC 2020 up 74 days, 16:35, 2 users, load averages: 2.63, 2.51, 2.54