mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2016-11-25, 20:55   #12
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

233 Posts
Default

Quote:
Originally Posted by Sergei Chernykh View Post
My factorization code uses exactly this combination: trial division up to fourth root of N and then 1 or 2 Pollard-Brent calls to get the remaining factors. I've just run a quick test on numbers you're interested in.

It factorized 106 even numbers in the range [1015, 1015+2*106) in 3.72 seconds on a single core of Intel Xeon E5-1650 v3 (which has about the same performance as i7-4790 on single-threaded code).

So it's ~268,000 factorizations per second. If you're interested, I can prepare this code as a standalone library.

P.S. I also have an implementation of GCD which is ~1.8 times faster than the classic one.
That is definitely interesting. Thank you for the suggestion. I did not compute the speed of my factorisation routine but I can imagine that it is slower.
The most flexible way of course is to share the source code. However if you want to keep it with you then providing a library can be a good solution. In that case I will need a function which takes long long n as an input and returns the sum of divisors of n as an output. I also use a modified version of that function which stops working as soon as it becomes clear that s(n) > 2*n, and return n+1 in this case. This function is used to speed up the process when we need s(n) - n to be at most n. I guess these functions should not be a big deal as soon as you have a factorisation routine.
Drdmitry is offline   Reply With Quote
Old 2016-11-26, 16:32   #13
Sergei Chernykh
 
Jun 2015
Stockholm, Sweden

83 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
That is definitely interesting. Thank you for the suggestion. I did not compute the speed of my factorisation routine but I can imagine that it is slower.
The most flexible way of course is to share the source code. However if you want to keep it with you then providing a library can be a good solution. In that case I will need a function which takes long long n as an input and returns the sum of divisors of n as an output. I also use a modified version of that function which stops working as soon as it becomes clear that s(n) > 2*n, and return n+1 in this case. This function is used to speed up the process when we need s(n) - n to be at most n. I guess these functions should not be a big deal as soon as you have a factorisation routine.
The code is not a secret - look at Factorize.h/cpp at my github. The version there is a bit slower than my latest code used in my BDE solver. It also has a lot of dependencies, that's why I'll need to prepare it first.

Update: the code at my github is actually very old, it doesn't even use Pollard-Brent. I'll publish my latest code somewhat later today.

Update 2: I've attached my latest factorization code with compiled EXE for benchmarking.
Attached Files
File Type: zip Factorize_2016.zip (168.6 KB, 63 views)

Last fiddled with by Sergei Chernykh on 2016-11-26 at 17:21
Sergei Chernykh is offline   Reply With Quote
Old 2016-11-26, 17:00   #14
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

24×3×72 Posts
Default

Hi Drdmitry.
I'm wondering how often should I find cycle in the range I have choosen (100k, 100k+150). Because so far, with about 1/6 of the work done, I have only found 1 2-lenght cycle. ( Windows 10, 64 bit).
firejuggler is offline   Reply With Quote
Old 2016-11-26, 22:55   #15
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

3518 Posts
Default

Quote:
Originally Posted by firejuggler View Post
Hi Drdmitry.
I'm wondering how often should I find cycle in the range I have choosen (100k, 100k+150). Because so far, with about 1/6 of the work done, I have only found 1 2-lenght cycle. ( Windows 10, 64 bit).
Your numbers sound fine to me. I just checked the amicable pairs: there is only one pair within the range 100000 - 100150 (it is for 1000042, am I right?) Then next pair goes for n = 1000184.
Drdmitry is offline   Reply With Quote
Old 2016-11-28, 16:16   #16
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

1001001100002 Posts
Default

interesting
819501511565312= 2^13*139*2339*307691
831903237028288=2^6*4751*6733*406349
(found this pair @ 100036)
I have another pair found at 100024 but none at 100042
firejuggler is offline   Reply With Quote
Old 2016-11-28, 17:28   #17
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

18CE16 Posts
Default

20M .. 20M+5k completed, it took about 60 hours on 1 core 2.6GHz Ivy Bridge and found 0 cycles

Trying (1M + 1) .. (1M + 200)

Last fiddled with by fivemack on 2016-11-28 at 17:31
fivemack is offline   Reply With Quote
Old 2016-11-28, 17:33   #18
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

2·52·127 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
Your numbers sound fine to me. I just checked the amicable pairs: there is only one pair within the range 100000 - 100150 (it is for 1000042, am I right?) Then next pair goes for n = 1000184.
I am slightly confused, the range is 10^5 .. 10^5+150 and you are talking about 10^6+42 and 10^6+184. It's good to know that I should get at least two hits in my range :)

Last fiddled with by fivemack on 2016-11-28 at 17:33
fivemack is offline   Reply With Quote
Old 2016-11-28, 19:13   #19
pinhodecarlos
 
pinhodecarlos's Avatar
 
"Carlos Pinho"
Oct 2011
Milton Keynes, UK

2×33×5×17 Posts
Default

One question.

1) Have doubts with regards to how to use the flags on the client. Imagine I want to run the n-range 1500-1600. Is the following correct?

Code:
start /low /min aliquot_even_10e15.exe 1500 1600
My question follows the fact that on your presentation I don't understand if the input flags are multiplied by 10e6 or not.

Last fiddled with by pinhodecarlos on 2016-11-28 at 19:14
pinhodecarlos is online now   Reply With Quote
Old 2016-11-29, 00:13   #20
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

233 Posts
Default

Quote:
Originally Posted by firejuggler View Post
interesting
819501511565312= 2^13*139*2339*307691
831903237028288=2^6*4751*6733*406349
(found this pair @ 100036)
I have another pair found at 100024 but none at 100042
Ups, I looked at the range starting from 10e6, For 10e5 the first pair comes for 100024 and the second one comes at 100036.

Last fiddled with by Drdmitry on 2016-11-29 at 00:20
Drdmitry is offline   Reply With Quote
Old 2016-11-29, 00:16   #21
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

3518 Posts
Default

Quote:
Originally Posted by pinhodecarlos View Post
One question.

1) Have doubts with regards to how to use the flags on the client. Imagine I want to run the n-range 1500-1600. Is the following correct?

Code:
start /low /min aliquot_even_10e15.exe 1500 1600
My question follows the fact that on your presentation I don't understand if the input flags are multiplied by 10e6 or not.
Yes, aliquot_even_10e15.exe 1500 1600 will do the range 1500-1600. Just be careful, the program does not automatically split the job between cores. On one core this task will take two - three months to complete.
Drdmitry is offline   Reply With Quote
Old 2016-12-02, 15:45   #22
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

635010 Posts
Default

(1M+1)..(1M+200) done

Code:
New cycle found!!
884037842133212
895944731690788
New cycle found!!
136025029735528
136243747173272
but you knew about both of those already
fivemack is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Aliquot cycles search, the state of the art. Drdmitry Aliquot Sequences 124 2017-07-02 02:48
Program for searching all odd-16-digit Aliquot cycles Drdmitry Aliquot Sequences 302 2016-05-11 02:17
Is a search for aliquot 3-cycles feasible? schickel Aliquot Sequences 7 2013-02-08 01:33
Small search of cycles with odd and even elements Drdmitry Aliquot Sequences 0 2011-12-14 13:50
Jan Munch Pedersen's Tables of Aliquot Cycles R. Gerbicz Math 0 2010-07-01 12:30

All times are UTC. The time now is 18:00.

Fri Jul 3 18:00:24 UTC 2020 up 100 days, 15:33, 2 users, load averages: 1.86, 1.46, 1.46

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.