New σ for Aliquot

JohnFullspeed · 2011-08-19, 06:09

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

TimSorbet · 2011-08-19, 11:52

http://www.mersennewiki.org/index.ph...ma_of_a_number

kar_bon · 2011-08-19, 12:42

I think what he means is:

The formula for the Sum of divisors for $N = p^{a}\ *\ q^{b}\ *\ r^{c}$ is: Sigma = $\frac{p^{a+1}-1}{p-1}\ *\ \frac{q^{b+1}-1}{q-1}\ *\ \frac{r^{c+1}-1}{r-1}\$ .

But for example if $p = 17$ and $a = 1$ , you don't have to calculate the value $\frac{17^{2}-1}{16}$ , 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.

R. Gerbicz · 2011-08-19, 15:23

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.

JohnFullspeed · 2011-08-19, 15:58

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

science_man_88 · 2011-08-19, 16:09

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.

JohnFullspeed · 2011-08-19, 19:43

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

R. Gerbicz · 2011-08-19, 20:15

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.

R. Gerbicz · 2011-08-19, 20:24

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.

JohnFullspeed · 2011-08-20, 06:16

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

R. Gerbicz · 2011-08-20, 07:43

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 ?
Maybe in your dream.

Read some math and English books.

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:=Sigman 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, 12:42	#3
kar_bon Mar 2006 Germany 3³·113 Posts	I think what he means is: The formula for the Sum of divisors for $N = p^{a}\ \ q^{b}\ \ r^{c}$ is: Sigma = $\frac{p^{a+1}-1}{p-1}\ \ \frac{q^{b+1}-1}{q-1}\ \ \frac{r^{c+1}-1}{r-1}\$ . But for example if $p = 17$ and $a = 1$ , you don't have to calculate the value $\frac{17^{2}-1}{16}$ , 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:58	#5
JohnFullspeed May 2011 France 10100001₂ 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-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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Broken aliquot sequences	schickel	FactorDB	18	2013-06-12 16:09
aliquot escape	firejuggler	Aliquot Sequences	26	2012-01-19 08:15
aliquot and mersenne	firejuggler	Aliquot Sequences	1	2010-06-01 23:47
serious bug in aliquot.ub	Andi47	Aliquot Sequences	3	2009-03-08 10:18
Aliquot Sum Function	grandpascorpion	Math	5	2008-02-06 15:12

2011-08-19, 11:52	#2
TimSorbet Account Deleted "Tim Sorbera" Aug 2006 San Antonio, TX USA 10267₈ Posts	http://www.mersennewiki.org/index.ph...ma_of_a_number