mersenneforum.org Multiplication method for factoring natural numbers
 Register FAQ Search Today's Posts Mark Forums Read

 2019-04-07, 16:35 #34 ThiloHarich     Nov 2005 101 Posts Sorry. The sum of all divisors - not only the prime divisors I thought of - can be higher then the number itself. So I misinterpreted your model. So yes abundant numbers https://en.wikipedia.org/wiki/Abundant_number are good candidates. But for example 105 and 15 are no such numbers but are good 'k'. Last fiddled with by ThiloHarich on 2019-04-07 at 17:01
2019-04-07, 17:03   #35
nesio

Apr 2019

2016 Posts

Quote:
 Originally Posted by ThiloHarich Sorry. The sum of all divisors - not the prime divisors I thought of - can be higher then the number itself. So I misinterpreted your model. So yes abundant numbers https://en.wikipedia.org/wiki/Abundant_number are good candidates. But for example 105 and 15 are no such numbers but are good 'k'.
Sum means here the amount, quantity.

Last fiddled with by nesio on 2019-04-07 at 17:11 Reason: grammar correction

2019-04-07, 18:16   #36
Till

"Tilman Neumann"
Jan 2016
Germany

6648 Posts

Quote:
 Originally Posted by nesio Sum means here the amount, quantity.

We have some language problems here. Just to clarify:

12 has divisors 1, 2, 3, 4, 6, 12. Is 6 the result you mean, or is it 28?

Quote:
 Originally Posted by ThiloHarich why should my model be very rough?
The rough model is the one he proposed, not yours:

Quote:
 Originally Posted by nesio You can check this rough (very rough) model of m on your source data of n: maximum(S/(m^1/3)) and m < n^1/3, where S - the sum of all divisors of m. Here are S and m^1/3 have equal weights in maximum function. What will be?
I interprete this as follows:

The quality of a multiplier m is about S/(m^1/3), where we consider m < n^1/3 only.

S might be
a) the sum of divisors of m, or
b) the number of disivors of m.
My first question in this post aims to clarify which of the two options is the correct one.

nesio, do I get that right so far?

Last fiddled with by Till on 2019-04-07 at 18:19 Reason: make clear that only one option for S is correct

 2019-04-07, 18:31 #37 nesio   Apr 2019 25 Posts A rough model of m: Find the maximum of (S/(m^1/3)) when m < n^1/3, where S - the number of all divisors of m (excluding 1 and m). Here are S and m^1/3 have equal weights in maximize function.
2019-04-07, 18:43   #38
Till

"Tilman Neumann"
Jan 2016
Germany

22×109 Posts

Quote:
 Originally Posted by nesio S - the number of all divisors of m (excluding 1 and m).

Ok, now we understand that one.

Quote:
 Originally Posted by nesio A rough model of m: Find the maximum of (S/(m^1/3)) when m < n^1/3, where S - the number of all divisors of m (excluding 1 and m). Here are S and m^1/3 have equal weights in maximize function.

I'ld say this is not a model of m, but a procedure to choose the best m. A model would give a kind of score to any m. (at least)

Quote:
 Originally Posted by nesio What will be?

A simple weighting function giving a "plus" for smooth m, a "minus" for big m.

This is no rocket science. We tested dozens of ways to arrange k's according to such principles, and many other constellations...

 2019-04-07, 19:04 #39 nesio   Apr 2019 2016 Posts Is it working on your data and what are the results? Last fiddled with by nesio on 2019-04-07 at 19:11 Reason: lang
 2019-04-07, 19:39 #40 Till     "Tilman Neumann" Jan 2016 Germany 22×109 Posts Unfortunately, none of our attempts to sort k's by such measures worked well. I believe that you did not try an efficient implementation yet. Theory (aka computational complexity, counting iterations being a simplified version of) and reality (measuring speed) are quite different for "small" factoring algorithms. After all, this is the only reason why Lehman or Hart algorithms have a right to exist. Otherwise NFS would wipe out all other algorithms at any number scale. If you try to optimize Hart/Lehman for small n, say n<=60 bit, then you will realize that instructions that are very fast on that number scale have a big or even decisive impact on the general performance. Complexity theory is often not strong enough to capture such influences. Storing the sqrts of k or of km is such a point. Without it, you will not be able to get a really fast Hart/Lehman implementation. Using congruences is a theoretical improvement, but also necessary. You can disprove my assumption that you did not try an efficient implementation yet by posting a fast piece of software ;-)
 2019-04-07, 21:29 #41 nesio   Apr 2019 3210 Posts For example such rough model (procedure) gives these values m from n n m 555 6 5555 12 55555 36 555555 60 5555555 120 55555555 360 555555555 720 5555555555 1680 55555555555 2520 555555555555 5040 5555555555555 5040 55555555555555 5040 555555555555555 5040 It is light and quite workable way for m in "multiplication method" we hope. Til! Our work is a research and a paper about Recursive Multiplication algorithm and its relation to Simple Multiplication algorithm. Your work is improving Lehman and Harts algorithms. You asked us about our vision regarding m. We wrote then. Something does not suit you in our discussion? Let's not continue to cross the red and wet ;-) We think you and Thilo should write a paper about your work that may be interesting not only in that forum. Last fiddled with by nesio on 2019-04-07 at 21:30 Reason: lang
 2019-04-08, 06:18 #42 Till     "Tilman Neumann" Jan 2016 Germany 22·109 Posts Hi nesio, sorry if I have been unpatient. I do not understand Russian, so I cannot get all information from your paper. And it took some time to get some interesting information from you. I will try to implement your particular proposition of sorting m by Code: score(m) = S(m) / n^(1/3) with S(m) = sum of divisors(m) without 1 and m this evening. Maybe we made an error so far in our evaluations of the smoothness of m's. We will see. You said that the computation of score(m) above is a very rough model. What would a more elaborate model look like?
2019-04-08, 06:39   #43
chalsall
If I May

"Chris Halsall"
Sep 2002

3×31×103 Posts

Quote:
 Originally Posted by Till What would a more elaborate model look like?
Just to share, it's been wonderful watching you two work with each other. Inspiring!

 2019-04-08, 09:27 #44 ThiloHarich     Nov 2005 101 Posts - Choosing the right m depends on the implementation. Til and me used some adjustments/improvements for odd multipliers m -> in our algorithm the good multipliers are not only even, best multipliers are odd. the numbers from nesio model : 6,12,36,60,120,360,720,1680,... do not appear in the list of good multipliers for this tuned algorithm in the top - the number of divisors is the product of the exponents + 1 of its prime factors If the exponents are all 1 then this is just 2^(number of prime factors of m). Having a factor with an exponent greater then one reduces the number of divisors. -> it looks like a good measure for good multipliers. But our best multiplier 315 = 3^2 * 5 * 7 has an exponent 2. When finding the best multipliers for numbers starting at 2^54 (and only factoring numbers with factors above n^1/3) I get a complete different list then when factoring numbers starting at 2^55. Last fiddled with by ThiloHarich on 2019-04-08 at 09:33

 Similar Threads Thread Thread Starter Forum Replies Last Post datblubat Computer Science & Computational Number Theory 6 2018-12-25 17:29 Dubslow Aliquot Sequences 6 2018-05-15 15:59 SPWorley Math 5 2009-08-18 17:27 philmoore Math 131 2006-12-18 06:27 Pax_Vitae Miscellaneous Math 15 2005-11-14 12:41

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

Mon May 17 00:17:35 UTC 2021 up 38 days, 18:58, 0 users, load averages: 1.33, 1.57, 1.62