mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2014-12-09, 16:10   #34
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

C8E16 Posts
Default

Hi Drdmitry,

My current program only checks up to 4 cycles, and only checks 0 mod 4 and 0 mod 3 even numbers, since I understood you to have covered the others. I'm working at 2*10^13 right now and my fastest machines are checking 1e6 blocks in ~11 seconds, per core. Those machines are Core 2 @ ~3GHz.

If you'd like to provide a program, that would be great. It sounds like yours is much faster than what I put together. I changed the 4 cycle limit to 100 in my program and it didn't return from its first 1e6 block for 7 hours! Of course, I didn't do anything extra for breaking out early, so some of the sequences ran up to the full 100 iterations.

I've been dabbling recently in the CUDA area to see if I can make something a bit faster, but the programming progress is slow.

Ed
EdH is offline   Reply With Quote
Old 2014-12-10, 13:07   #35
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

233 Posts
Default

Here is my program. I'm afraid I can only provide a 64-bit version of it. I had a 32-bit version sometimes ago, but then I had to use a large integer arithmetics. That was about 10 times slower than the current program.
The algorithm now is pretty close to that explained in D. Moews, P. Moews paper. It searches for all cycles where the element preceding the largest element lies in the given range. For optimization reasons it skips all odd numbers less than 10e14 (since they are already been searched). Also it skips all cycles with the smallest elements less than 10e9. If there are new cycles with this property then (I guess) the largest element of such cycle must be out of the range 2^61 supported by the program.
I also put a source code here. It is VC++ and x64 specific. However with some efforts it can be adopted to other platforms.
Attached Files
File Type: exe aliquot.exe (248.0 KB, 75 views)
File Type: zip aliquot.zip (3.2 KB, 88 views)
Drdmitry is offline   Reply With Quote
Old 2014-12-10, 15:00   #36
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

1100100011102 Posts
Default

Thanks! I don't have any Windows machines operating right now, but I will look over the source when I can get a chance. This might add in some interest for some others who weren't ready to program it themselves.
EdH is offline   Reply With Quote
Old 2014-12-11, 20:18   #37
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2×1,607 Posts
Default

Quote:
Originally Posted by MichelMarcus View Post
Jamais 2 sans 3 ?
Il est vrai! Merci, Michel (and others)!
Code:
20770607674232 = 2E3.13.47.28097.151237
22064204391688 = 2E3.19.37.3923222687
22660534251512 = 2E3.19.367.419.969497
22293149012488 = 2E3.41.283.461.520967
I am wondering, though, if I should wait to see if more show up before bothering David Moews any more with individual finds, since I am running an on-going project and he does a lot of renumbering for each find. On the one hand, I like to see them in his list and letting him know, keeps the list current, but I don't like causing him the extra work on too frequent a basis. An occasional list, if any, might alleviate some of his work. I intend to ask him via email. Of course, the "in"frequency of finds might alleviate that concern...
EdH is offline   Reply With Quote
Old 2014-12-12, 20:52   #38
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT)

130528 Posts
Default

Quote:
Originally Posted by EdH View Post
Thanks! I don't have any Windows machines operating right now, but I will look over the source when I can get a chance. This might add in some interest for some others who weren't ready to program it themselves.
wine
henryzz is offline   Reply With Quote
Old 2014-12-12, 23:33   #39
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·1,607 Posts
Default

Quote:
Originally Posted by henryzz View Post
wine
as opposed to wine or whine...

I never think of that anymore. I'm not sure why. I do think of virtual machines, but I recently had to reinstall the OS on my main machine and haven't gotten VirtualBox running yet.

I did install wine and the program seems to run very comparable to my perl version, except that it is searching for cycles much greater than my 4 cycle limit.

I will have to see how I can incorporate this new program into my existing machine network. That and seeing if I can compile it on linux. I tried to compile the c++ code and I don't have the proper intrin.h file apparently. In fact, I have many ##intrin.h files, but none that are just intrin.h. Is that a Windows OS specific header of some sort?

Thanks to all!
EdH is offline   Reply With Quote
Old 2014-12-13, 12:49   #40
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

233 Posts
Default

Quote:
Originally Posted by EdH View Post
as opposed to wine or whine...

I will have to see how I can incorporate this new program into my existing machine network. That and seeing if I can compile it on linux. I tried to compile the c++ code and I don't have the proper intrin.h file apparently. In fact, I have many ##intrin.h files, but none that are just intrin.h. Is that a Windows OS specific header of some sort?
intrin.h contains all intrinsics available in Visual Studio. I used it only for one function _mul128 which multiplies two 64-bit numbers and returns 128-bit result.
Actually to adopt the program to another platform one just needs to rewrite mulmod function which simply multiplies two 64-bit numbers modulo another 64-bit number. The problem is that X64 processors can do that in just two commands. However C++, as well as the most of other high level languages, does not support this feature. You firstly need to implement 128-bit arithmetic which makes program significantly slower. So _mul128 replaces one of the x64 commands. Another command is encoded directly in machine codes (I copied that trick from some forum on the internet).
Drdmitry is offline   Reply With Quote
Old 2014-12-13, 14:30   #41
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2·1,607 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
intrin.h contains all intrinsics available in Visual Studio. I used it only for one function _mul128 which multiplies two 64-bit numbers and returns 128-bit result.
Actually to adopt the program to another platform one just needs to rewrite mulmod function which simply multiplies two 64-bit numbers modulo another 64-bit number. The problem is that X64 processors can do that in just two commands. However C++, as well as the most of other high level languages, does not support this feature. You firstly need to implement 128-bit arithmetic which makes program significantly slower. So _mul128 replaces one of the x64 commands. Another command is encoded directly in machine codes (I copied that trick from some forum on the internet).
Thanks! I will look into this more. It sounds like it might also solve my trouble I have with trying to program a Miller-Rabin routine into my CUDA stuff recently - never did get that working.
EdH is offline   Reply With Quote
Old 2014-12-13, 22:45   #42
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

2×1,607 Posts
Default

I seem to have __int128 available to me via gcc in linux, so I started rewriting your code. I didn't have too much time and then I thought, if I'm going to the bother, maybe I should just go back to the Moews' paper, especially since I don't have an understanding of inline assembly and my assembly knowledge is too old to make much use of for anything like this. This will be a good way to exercise the little knowledge I have and hopefully expand it.

Thanks, again...
EdH is offline   Reply With Quote
Old 2014-12-22, 02:14   #43
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

C8E16 Posts
Default

Yet, another:
Code:
23255440525768 = 2E3.11.23.97.137.864613
27258491133752 = 2E3.23.277.967.553067
26321320852168 = 2E3.17.107.1201.1506059
26466564087032 = 2E3.521.28879.219881
Thanks, all...
EdH is offline   Reply With Quote
Old 2015-01-09, 11:58   #44
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

233 Posts
Default

Unfortunately I do not have enough computer power to do a exhaustive search of aliquot cycles in a reasonable range. So I played a little bit with my program to see what can be done with it relatively quickly.
Firstly if the search is restricted to odd numbers only then it goes much faster: It took about 12.3 secs per 10^8 on one core of my laptop - about 100 times faster than for even numbers. I checked all odd numbers between 10e13 and 12e13.
Then I also checked all 15-digit odd numbers of the form
3a1 * 5a2 * ... * 29a9 * n
with n up to around 6e7. I am still running a program to extend the full search for n up to about 12e8. However now as the new term starts I will not be able to pay too much attention on it and I am not sure that I will actually complete the search.
I did also some other funny checks. No new cycles of length more than two were found, I'm afraid. On the other hand 137 new amicable pairs, not presented in Pedersen's tables were found. I attach the file with them here.
I also found an inaccuracy in Mathworld article about amicable pairs. It is said that the smallest known pair with elements coprime to 6 has 32 digits. However in Pedersens list there is a pair
Quote:
5480828320492525=5^2*7^2*11*13*19*31*17*23*103*1319
5786392931193875=5^3*7*11*13*19*31*37*43*61*809
which has only 16 digits - twice less.
Attached Files
File Type: txt newfound_druz.txt (14.7 KB, 86 views)
Drdmitry is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Carmichael numbers and Devaraj numbers devarajkandadai Number Theory Discussion Group 0 2017-07-09 05:07
6 digit numbers and the mersenne numbers henryzz Math 2 2008-04-29 02:05
LLT numbers, linkd with Mersenne and Fermat numbers T.Rex Math 4 2005-05-07 08:25

All times are UTC. The time now is 17:45.

Fri Jul 3 17:45:24 UTC 2020 up 100 days, 15:18, 2 users, load averages: 1.72, 1.64, 1.63

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.