Re: unordered but memory-friendly fordiv() (without calling to divisors())

[Max Alekseyev <maxale@gmail.com>]

PS#2. We can do much better than forvec() if we view the divisors of a given number as a tree rooted at divisor 1, where each node with divisor d  has children with divisors p*d for various primes p >= largest prime factor of d. Then traversing the tree nodes in DFS fashion will help to drastically reduce the number of multiplications needed to produce the divisor values (as going from a parent node to a child node requires just one multiplication). 

Formally speaking the divisors of any number form a recursively enumerable set, and its structure can be exploited to produce the divisor values efficiently. (Perhaps, this is already done internally by the divisors() function.)

Regards,

Max

On Fri, Oct 28, 2022 at 4:24 PM Max Alekseyev <maxale@gmail.com> wrote:

Can we have a variant of fordiv() / fordivfactored() that will not call to divisors() but generate the divisors on-fly at the cost of not enforcing them be in order?

The problem with divisors() is that it stores all the divisors in memory, which may be quite expensive, while this is only needed only if one wants to iterate over the divisors in order. If order of divisors is not important, then there is no need to store them all and thus save memory.

And having parfordiv() would be also a valuable addition.

PS. I realize that I can generate divisors manually via forvec() or alike, but it'd be really nice to have it as a built-in feature.

Thank you!

Max