Max Alekseyev on Fri, 28 Oct 2022 23:31:21 +0200
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: unordered but memory-friendly fordiv() (without calling to divisors())
- To: firstname.lastname@example.org
- Subject: Re: unordered but memory-friendly fordiv() (without calling to divisors())
- From: Max Alekseyev <email@example.com>
- Date: Fri, 28 Oct 2022 17:29:42 -0400
- Delivery-date: Fri, 28 Oct 2022 23:31:21 +0200
- Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :from:to:cc:subject:date:message-id:reply-to; bh=TqAKsp1Cdz1JGrdypQ5PCQQ+g3iHDk0obvhyXV7kKjM=; b=VO7P7uXDr1wfA6y9JvS1KOHU1tqQkamb1N9hOHXObRTNhtFLNfsX2J8Aaai8E42hIX MHbMNLGnbB50jAs3LL5bWLwYhN7tKeM7iXdhGTfmb2CGQmXHoNf6PkP4/KmxBHkPNNwN 2byTQkxaO2JN7PJ4naFOvGODswEw52GV6T4jJEt017nNf/VvBAScoIaLeCorjaugEuh0 CJ0lZRJERIq3NxN7k0YabNdNTaY3zYG1/FNLD8kjPlVvZMmriOn+180VElV2nxIcWp6H VAIau+J8Bwd9QU+ygcBrUUUgGTtUTJmLi4w5327Hl+mUc2qM3Bv2mRLKJXb6NmPLGNYK wcMw==
- In-reply-to: <CAJkPp5OdpHQLeKK=iwDJbPXXRfaNou8P0cT89WWL+=URANFL=A@mail.gmail.com>
- References: <CAJkPp5OdpHQLeKK=iwDJbPXXRfaNou8P0cT89WWL+=URANFL=A@mail.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.)
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.