mersenneforum.org Aliquot sequences that start on the integer powers n^i
 Register FAQ Search Today's Posts Mark Forums Read

2021-03-31, 15:36   #1046
garambois

"Garambois Jean-Luc"
Oct 2011
France

24816 Posts

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

2021-03-31, 16:04   #1047
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

32·5·11 Posts

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

Quote:
 Originally Posted by garambois […] 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 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.

2021-03-31, 16:15   #1048
garambois

"Garambois Jean-Luc"
Oct 2011
France

23×73 Posts

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

2021-03-31, 17:19   #1049
garambois

"Garambois Jean-Luc"
Oct 2011
France

10010010002 Posts

Sorry, I just realized that I forgot to attach the file in post #1045 !
Here it is ...
Attached Files
 conjectures3.html.tar.gz (5.7 KB, 13 views)

2021-03-31, 20:03   #1050
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

32×5×11 Posts

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
 patf.7z (14.7 KB, 11 views)

2021-04-01, 17:44   #1051
garambois

"Garambois Jean-Luc"
Oct 2011
France

23×73 Posts

Quote:
 Originally Posted by kruoli 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 ;-)

2021-04-01, 21:39   #1052
kruoli

"Oliver"
Sep 2017
Porta Westfalica, DE

32·5·11 Posts

Quote:
 Originally Posted by garambois 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 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 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
 patf1.1.0.7z (17.3 KB, 15 views)

Last fiddled with by kruoli on 2021-04-01 at 21:40 Reason: Grammar.

 2021-04-02, 13:27 #1053 garambois     "Garambois Jean-Luc" Oct 2011 France 23·73 Posts 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 ...
 2021-04-02, 14:27 #1054 kruoli     "Oliver" Sep 2017 Porta Westfalica, DE 32×5×11 Posts 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).
2021-04-02, 19:50   #1055
Happy5214

"Alexander"
Nov 2008
The Alamo City

5×112 Posts

Quote:
 Originally Posted by garambois 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
 conjectures4.tar.gz (5.6 KB, 10 views)

2021-04-03, 14:12   #1056
garambois

"Garambois Jean-Luc"
Oct 2011
France

23·73 Posts

Quote:
 Originally Posted by Happy5214 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
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 !
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".

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack FactorDB 46 2021-02-21 10:46 schickel FactorDB 18 2013-06-12 16:09 garambois Aliquot Sequences 34 2012-06-10 21:53 Andi47 FactorDB 21 2011-12-29 21:11 schickel mersennewiki 0 2008-12-30 07:07

All times are UTC. The time now is 22:05.

Fri May 14 22:05:31 UTC 2021 up 36 days, 16:46, 0 users, load averages: 4.32, 3.68, 3.47