mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2011-08-19, 06:09   #1
JohnFullspeed
 
May 2011
France

7·23 Posts
Smile 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
JohnFullspeed is offline   Reply With Quote
Old 2011-08-19, 11:52   #2
Mini-Geek
Account Deleted
 
Mini-Geek's Avatar
 
"Tim Sorbera"
Aug 2006
San Antonio, TX USA

17·251 Posts
Default

http://www.mersennewiki.org/index.ph...ma_of_a_number
Mini-Geek is online now   Reply With Quote
Old 2011-08-19, 12:42   #3
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

2·3·52·19 Posts
Default

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.
kar_bon is offline   Reply With Quote
Old 2011-08-19, 15:23   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2·3·5·47 Posts
Default

Quote:
Originally Posted by kar_bon View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2011-08-19, 15:58   #5
JohnFullspeed
 
May 2011
France

101000012 Posts
Default 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
JohnFullspeed is offline   Reply With Quote
Old 2011-08-19, 16:09   #6
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by JohnFullspeed View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-08-19, 19:43   #7
JohnFullspeed
 
May 2011
France

7·23 Posts
Default I don't understand

Quote:
Originally Posted by R. Gerbicz View Post
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
JohnFullspeed is offline   Reply With Quote
Old 2011-08-19, 20:15   #8
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×5×47 Posts
Default

Quote:
Originally Posted by JohnFullspeed View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2011-08-19, 20:24   #9
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

101100000102 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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
R. Gerbicz is offline   Reply With Quote
Old 2011-08-20, 06:16   #10
JohnFullspeed
 
May 2011
France

A116 Posts
Default 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
JohnFullspeed is offline   Reply With Quote
Old 2011-08-20, 07:43   #11
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

2×3×5×47 Posts
Default

Quote:
Originally Posted by JohnFullspeed View Post
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.
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


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

All times are UTC. The time now is 12:09.

Fri Oct 23 12:09:46 UTC 2020 up 43 days, 9:20, 0 users, load averages: 1.88, 1.57, 1.42

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.