mersenneforum.org Search of all even-15-digit Aliquot cycles
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2016-11-25, 20:55   #12
Drdmitry

Nov 2011

233 Posts

Quote:
 Originally Posted by Sergei Chernykh 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.

2016-11-26, 16:32   #13
Sergei Chernykh

Jun 2015
Stockholm, Sweden

83 Posts

Quote:
 Originally Posted by Drdmitry 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
 Factorize_2016.zip (168.6 KB, 63 views)

Last fiddled with by Sergei Chernykh on 2016-11-26 at 17:21

 2016-11-26, 17:00 #14 firejuggler     Apr 2010 Over the rainbow 24×3×72 Posts 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).
2016-11-26, 22:55   #15
Drdmitry

Nov 2011

3518 Posts

Quote:
 Originally Posted by firejuggler 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.

 2016-11-28, 16:16 #16 firejuggler     Apr 2010 Over the rainbow 1001001100002 Posts 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
 2016-11-28, 17:28 #17 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 18CE16 Posts 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
2016-11-28, 17:33   #18
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2·52·127 Posts

Quote:
 Originally Posted by Drdmitry 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

 2016-11-28, 19:13 #19 pinhodecarlos     "Carlos Pinho" Oct 2011 Milton Keynes, UK 2×33×5×17 Posts 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
2016-11-29, 00:13   #20
Drdmitry

Nov 2011

233 Posts

Quote:
 Originally Posted by firejuggler 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

2016-11-29, 00:16   #21
Drdmitry

Nov 2011

3518 Posts

Quote:
 Originally Posted by pinhodecarlos 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.

 2016-12-02, 15:45 #22 fivemack (loop (#_fork))     Feb 2006 Cambridge, England 635010 Posts (1M+1)..(1M+200) done Code: New cycle found!! 884037842133212 895944731690788 New cycle found!! 136025029735528 136243747173272 but you knew about both of those already

 Similar Threads Thread Thread Starter Forum Replies Last Post Drdmitry Aliquot Sequences 124 2017-07-02 02:48 Drdmitry Aliquot Sequences 302 2016-05-11 02:17 schickel Aliquot Sequences 7 2013-02-08 01:33 Drdmitry Aliquot Sequences 0 2011-12-14 13:50 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