mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2021-03-31, 15:36   #1046
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

5×137 Posts
Default

Quote:
Originally Posted by kruoli View Post
Here I have my trial factoring tool for \(\sigma(n^m)\) for very large \(m\). I wrote it in C#, wanted to use .NET Core originally, but found .NET Framework easier to use on Linux with Mono. I have no experience with .NET Core on Linux.
It should be reasonably fast, but has tons of room for improvement, both algorithmically and programming-language wise.

The attachment contains both the source and an executable for usage on both Windows and Linux 64 bit, but might also run on 32 bit OSes (untested).

Thank you very much Oliver !
I manage to get the program to work and it seems to work even with bases that are not prime numbers.
The program is remarkably fast.
I did several tests. I will be doing more extensive testing in the next few days.
I don't know yet how to do it myself, but if you have a little time, it would be very useful for our work, please, to add a few lines of code so that at the end, the program shows us on a single line the complete divisor in the form of a product, like this :
"d = p1^a1 * p2^a2 * p3^a3 ..." which is the product of all the prime factors found taking into account their multiplicity.
So, it will be very easy to test the abundance of this divisor d.
Many thanks for all !

garambois is online now   Reply With Quote
Old 2021-03-31, 16:04   #1047
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

30016 Posts
Default

Quote:
Originally Posted by garambois View Post
Thank you very much Oliver ! […] Many thanks for all !
You are welcome.

Quote:
Originally Posted by garambois View Post
[…] it seems to work even with bases that are not prime numbers.
Yes, I forgot to mention it explicitly, the base can be any whole number from 2 to 1060, currently, but this might be expandable with some additional code.

Quote:
Originally Posted by garambois View Post
I don't know yet how to do it myself, but if you have a little time, it would be very useful for our work, please, to add a few lines of code so that at the end, the program shows us on a single line the complete divisor in the form of a product, like this :
"d = p1^a1 * p2^a2 * p3^a3 ..." which is the product of all the prime factors found taking into account their multiplicity.
So, it will be very easy to test the abundance of this divisor d.
I can do that, but since the program is not doing a full factorization (only up to a certain limit given as command line parameter), the line will not be complete. For abundance, we do not need a full factorization. If I understand correctly, for my example above you would expect d = 3^5 * 19^2 * 29^2 * [left out] * 967847 * 982801 * 991453 * remainder, correct?

But for small exponents, we could have a full factorization. But in this case, yafu will be much more efficient in factoring such numbers.

Last fiddled with by kruoli on 2021-03-31 at 16:31 Reason: Additional information. Removed bogus words. Spelling.
kruoli is online now   Reply With Quote
Old 2021-03-31, 16:15   #1048
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

5·137 Posts
Default

Quote:
Originally Posted by kruoli View Post
I can do that, but since the program is not doing a full factorization (only up to a certain limit given as command line parameter), the line will not be complete. For abudance, we do not need a full factorization. If I understand correctly, for my example above you would expect d = 3^5 * 19^2 * 29^2 * [left out] * 967847 * 982801 * 991453 * remainder, correct?

But for small exponents, we could have a full factorization. But in this case, yafu will be much more efficient in factoring such numbers.
Yes, this is exactly what we need !
Of course, I understood that your program is to be used only for very very large exponents.
And of course, we will never have full factorization in these extreme cases.
For much smaller exponents, there will be yafu ...
garambois is online now   Reply With Quote
Old 2021-03-31, 17:19   #1049
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

68510 Posts
Default

Sorry, I just realized that I forgot to attach the file in post #1045 !
Here it is ...
Attached Files
File Type: gz conjectures3.html.tar.gz (5.7 KB, 38 views)
garambois is online now   Reply With Quote
Old 2021-03-31, 20:03   #1050
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

28×3 Posts
Default

This is a new version of my program with the output format suggested by garambois. To return to the old format, add -v as the first argument.
Attached Files
File Type: 7z patf.7z (14.7 KB, 41 views)
kruoli is online now   Reply With Quote
Old 2021-04-01, 17:44   #1051
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

5×137 Posts
Default

Quote:
Originally Posted by kruoli View Post
This is a new version of my program with the output format suggested by garambois. To return to the old format, add -v as the first argument.

OK, many thanks Oliver.
Everything seems to work perfectly !
I will be doing some testing over the next week and will let you know if I have any problems.
Just a detail, I am unable to run the program with the -v argument.
But I don't necessarily think I need it, because the new display of the result suits me much more.

Your program makes it possible to have all the prime numbers even up to 10 ^ 9 in a few tens of minutes if the base is not too large and that with exponents of the order of 1,000,000 !
And I tried a very large exponent for base 3 : 3 ^ 5 * 5 ^ 3 * 7 ^ 2 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47 and we are very very far from having an abundant d !!!

Another detail : it seems impossible to enter the exponent in the form of a product of prime factors as in the example above, it must be calculated before to have the exponent in the form of a single number to be able to enter it in the program.
Very often, when we want to try exponents, we enter them as products of prime numbers, because we "construct" them.
But this is really a detail and it is very fast to build the exponent with another program in parallel ;-)
garambois is online now   Reply With Quote
Old 2021-04-01, 21:39   #1052
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

28×3 Posts
Default

Quote:
Originally Posted by garambois View Post
Just a detail, I am unable to run the program with the -v argument.
Whoops, that was an error on my side. I have fixed it in the attached version. I removed the one-factor-per-line-format. Instead, -v will only give additional timing and factor count information.

Quote:
Originally Posted by garambois View Post
Your program makes it possible to have all the prime numbers even up to 10 ^ 9 in a few tens of minutes if the base is not too large and that with exponents of the order of 1,000,000 !
If somebody is eager to implement it with primesieve and GMP, this will run in seconds for sure! I updated my code with multithreading, so it should be somewhat faster (it will scale about linear to the available physical cores).

Quote:
Originally Posted by garambois View Post
Another detail : it seems impossible to enter the exponent in the form of a product of prime factors as in the example above, it must be calculated before to have the exponent in the form of a single number to be able to enter it in the program.
Very often, when we want to try exponents, we enter them as products of prime numbers, because we "construct" them.
Yes, I did not plan for that originally. It simply expected a string of decimal digits. Now, with this version, you can enter e.g. patf 3 "3 ^ 5 * 5 ^ 3 * 7 ^ 2 * 11 * 13 * 17 * 19 * 23 * 29 * 31 * 37 * 41 * 43 * 47" 1000000000. The quotation marks are important here! And only the exponent can be in this form. Please have no value start with the digit 0. BigInteger of C# handles such numbers octally by default.
Attached Files
File Type: 7z patf1.1.0.7z (17.3 KB, 39 views)

Last fiddled with by kruoli on 2021-04-01 at 21:40 Reason: Grammar.
kruoli is online now   Reply With Quote
Old 2021-04-02, 13:27   #1053
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

5·137 Posts
Default

Everything seems to be working very, very well.
On the other hand, this leads me to ask you a question before continuing my tests :
Please, what is the size limit for the exponents ?
Because for bases 3 and 5 it seems extremely, but then really extremely difficult to find an exponent "i" that assures us an abundant s(3^i) or s(5^i).
After an hour of different tests, I entered these parameters in the program :
Code:
mono patf.exe -v 3 "3 ^ 20 * 5 ^ 18 * 7 ^ 16 * 11 ^ 14 * 13 ^ 12 * 17 ^ 10 * 19 ^ 8 * 23 ^ 6 * 29 ^ 4 * 31 ^ 2 * 37 * 41 * 43 * 47 * 53 * 59 * 61 * 67 * 71 * 73 * 79 * 83 * 89 * 97" 100000
The response was almost instantaneous.
It was then that I realized that this exponent had 129 digits !
It's hard to believe that the program can handle exponents of this size !

Note : I must limit the last parameter of the program to 100,000, otherwise it becomes time consuming to test the abundance of d with Sage. But it would seem that it is not very useful to consider larger prime numbers : it does not influence too much the abundance of the number ...
garambois is online now   Reply With Quote
Old 2021-04-02, 14:27   #1054
kruoli
 
kruoli's Avatar
 
"Oliver"
Sep 2017
Porta Westfalica, DE

28·3 Posts
Default

The exponent is not limited in size by my program. Instead, it is limited by Microsoft's (or the mono team's) implementation of BigInteger. Modular exponentation is extremely efficient, especially for small modulos. And our modulos are quite small. I ran some test to show you why the size does not matter as much as you think:
Code:
ModPow(2, 10^2, 1277) took 0 ms.
ModPow(2, 10^4, 1277) took 0 ms.
ModPow(2, 10^8, 1277) took 0 ms.
ModPow(2, 10^16, 1277) took 0 ms.
ModPow(2, 10^32, 1277) took 0 ms.
ModPow(2, 10^64, 1277) took 0 ms.
ModPow(2, 10^128, 1277) took 0 ms.
ModPow(2, 10^256, 1277) took 0 ms.
ModPow(2, 10^512, 1277) took 0 ms.
ModPow(2, 10^1024, 1277) took 0 ms.
ModPow(2, 10^2048, 1277) took 0 ms.
ModPow(2, 10^4096, 1277) took 0 ms.
ModPow(2, 10^8192, 1277) took 0 ms.
ModPow(2, 10^16384, 1277) took 1 ms.
ModPow(2, 10^32768, 1277) took 2 ms.
ModPow(2, 10^65536, 1277) took 5 ms.
ModPow(2, 10^131072, 1277) took 10 ms.
ModPow(2, 10^262144, 1277) took 20 ms.
ModPow(2, 10^524288, 1277) took 39 ms.
ModPow(2, 10^1048576, 1277) took 82 ms.
ModPow(2, 10^2, 2^31-1) took 0 ms.
ModPow(2, 10^4, 2^31-1) took 0 ms.
ModPow(2, 10^8, 2^31-1) took 0 ms.
ModPow(2, 10^16, 2^31-1) took 0 ms.
ModPow(2, 10^32, 2^31-1) took 0 ms.
ModPow(2, 10^64, 2^31-1) took 0 ms.
ModPow(2, 10^128, 2^31-1) took 0 ms.
ModPow(2, 10^256, 2^31-1) took 0 ms.
ModPow(2, 10^512, 2^31-1) took 0 ms.
ModPow(2, 10^1024, 2^31-1) took 0 ms.
ModPow(2, 10^2048, 2^31-1) took 0 ms.
ModPow(2, 10^4096, 2^31-1) took 0 ms.
ModPow(2, 10^8192, 2^31-1) took 0 ms.
ModPow(2, 10^16384, 2^31-1) took 1 ms.
ModPow(2, 10^32768, 2^31-1) took 2 ms.
ModPow(2, 10^65536, 2^31-1) took 6 ms.
ModPow(2, 10^131072, 2^31-1) took 12 ms.
ModPow(2, 10^262144, 2^31-1) took 23 ms.
ModPow(2, 10^524288, 2^31-1) took 47 ms.
ModPow(2, 10^1048576, 2^31-1) took 95 ms.
ModPow(2, 10^2, 2^63-1) took 0 ms.
ModPow(2, 10^4, 2^63-1) took 0 ms.
ModPow(2, 10^8, 2^63-1) took 0 ms.
ModPow(2, 10^16, 2^63-1) took 0 ms.
ModPow(2, 10^32, 2^63-1) took 0 ms.
ModPow(2, 10^64, 2^63-1) took 0 ms.
ModPow(2, 10^128, 2^63-1) took 0 ms.
ModPow(2, 10^256, 2^63-1) took 0 ms.
ModPow(2, 10^512, 2^63-1) took 0 ms.
ModPow(2, 10^1024, 2^63-1) took 0 ms.
ModPow(2, 10^2048, 2^63-1) took 0 ms.
ModPow(2, 10^4096, 2^63-1) took 0 ms.
ModPow(2, 10^8192, 2^63-1) took 1 ms.
ModPow(2, 10^16384, 2^63-1) took 2 ms.
ModPow(2, 10^32768, 2^63-1) took 4 ms.
ModPow(2, 10^65536, 2^63-1) took 10 ms.
ModPow(2, 10^131072, 2^63-1) took 24 ms.
ModPow(2, 10^262144, 2^63-1) took 43 ms.
ModPow(2, 10^524288, 2^63-1) took 97 ms.
ModPow(2, 10^1048576, 2^63-1) took 169 ms.
Doubling the exponent of the exponent (!) will increase the execution time by only a factor of 2. Increasing the modulo to four full bytes will only increase the time marginally. Increasing the modulo to eight bytes will about double the time required.

The computation of 10n takes way longer than the modular exponentiation in my test (not shown here).
kruoli is online now   Reply With Quote
Old 2021-04-02, 19:50   #1055
Happy5214
 
Happy5214's Avatar
 
"Alexander"
Nov 2008
The Alamo City

23×97 Posts
Default

Quote:
Originally Posted by garambois View Post
OK, done.
Please, if someone can check the proofs of conjectures (2) and (138), if it fits like this ?
I still left the links to the posts.
Moreover, I don't know how we usually do it : do I have to add the names of the people who made the demonstrations each time, which seems correct to me ? (conjecture 2: henryzz and warachwe ; conjecture 3: henryzz, warachwe, Happy5214 ; other conjectures : Happy5214)
For conjecture 138, should I add the proof of Happy5214 from post #960 ?

I tried to do this, but what bothers me is that in this case the write size of the titles "Conjectures (134)" to "Conjectures (139)" is then larger than the write size of the titles "Conjectures (1)" to "Conjectures (133)".
However, there is no reason that the size of these titles should be different, in my opinion.

I'm really sorry, but I don't understand what to do here ?

I hope this is good now, because I only half understand the usefulness of sections and how they work !

Are you talking about the ampersands that are in the links that lead to other sites ?
Because here too I do not understand what to do ?

The simplest is perhaps that for this kind of details which I do not know, you make the modifications directly on the attached file and that you rename it "conjectures4" in order to send it back to me.
Only do this if it is important to you, because personally, I am more than satisfied with the page as it is in this version 3 ...
And I'm sorry to take your time like this, because I think you have a lot of other things to do !
Eventually, I want to use MathJax and TeX if possible to render the proofs, so I'll hold off on editing them for now. I fixed the ampersands and headers (I promoted everything to h3 and deleted the base-level headers). I also fixed the formatting for the proof and remark headers, so you don't need the <br> tags. I've attached it here. It's good enough to post for now.
Attached Files
File Type: gz conjectures4.tar.gz (5.6 KB, 33 views)
Happy5214 is offline   Reply With Quote
Old 2021-04-03, 14:12   #1056
garambois
 
garambois's Avatar
 
"Garambois Jean-Luc"
Oct 2011
France

10101011012 Posts
Default

Quote:
Originally Posted by Happy5214 View Post
Eventually, I want to use MathJax and TeX if possible to render the proofs, so I'll hold off on editing them for now. I fixed the ampersands and headers (I promoted everything to h3 and deleted the base-level headers). I also fixed the formatting for the proof and remark headers, so you don't need the <br> tags. I've attached it here. It's good enough to post for now.

OK, thank you very much Alexander for all of your help.
The page is finally accessible from my website and I am very happy to have this new page which recapitulates all the conjectures !
To access, click here :
http://www.aliquotes.com/conjectures_mersenneforum.html

Please, would it be possible for an administrator to add a link to this page in the very first post of the topic, a sentence like that, or something better formulated for an English speaker ;-) :
"Access the regularly updated page which summarizes all the conjectures published on this topic by clicking here".
garambois is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Broken aliquot sequences fivemack FactorDB 46 2021-02-21 10:46
Broken aliquot sequences schickel FactorDB 18 2013-06-12 16:09
A new theorem about aliquot sequences garambois Aliquot Sequences 34 2012-06-10 21:53
poaching aliquot sequences... Andi47 FactorDB 21 2011-12-29 21:11
New article on aliquot sequences schickel mersennewiki 0 2008-12-30 07:07

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


Mon Dec 6 18:04:00 UTC 2021 up 136 days, 12:32, 0 users, load averages: 1.86, 1.82, 1.80

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.