ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 23 Nov 2021 01:46:23 +0100efficient generation of unitary divisorshttps://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:
def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
For comparison, the naive approach by filtering the divisors of $n$ would be:
def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
From theoretical perspective, `unitary_divisors1(n)` is much more efficient than `unitary_divisors2(n)` for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice `unitary_divisors1(n)` loses badly to `unitary_divisors2(n)` when $n$ is square-free (in which case every divisor of $n$ is unitary):
sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
In this example with `N` being the product of first 20 primes, `unitary_divisors1(N)` is over 40 times slower than `unitary_divisors2(N)`.
Is there a way to generate unitary divisors that works with efficiency close to `divisors(n)` when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?Sat, 20 Nov 2021 21:48:51 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/Comment by John Palmieri for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59897#post-id-59897In fact `Subsets` uses `itertools` in its implementation, so directly using `itertools` might be the right choice. The `Subsets` iterator puts a few layers on top of `itertools.combination`, and maybe that's what makes it a bit slower.Tue, 23 Nov 2021 01:46:23 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59897#post-id-59897Comment by John Palmieri for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59896#post-id-59896I don't know the `Subsets` code. It looks like all you need from that is to iterate over all subsets, which the `itertools` powerset recipe provides, and it looks like it's faster. I wouldn't be surprised if `Subsets` could be made faster, for example by writing it in Cython, but I don't know if anyone is working on it.Tue, 23 Nov 2021 01:44:22 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59896#post-id-59896Comment by Max Alekseyev for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59892#post-id-59892Can `Subsets` construction be improved? I'd prefer to rely on its efficient implementation rather than trying to optimize simple stuff here and there.Mon, 22 Nov 2021 21:17:40 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59892#post-id-59892Comment by John Palmieri for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59857#post-id-59857I wonder if something from the Python `itertools` module would be faster.Sun, 21 Nov 2021 01:17:30 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59857#post-id-59857Comment by Max Alekseyev for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59855#post-id-59855What should I use instead of Subsets? Maybe Gray code?Sat, 20 Nov 2021 23:44:47 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59855#post-id-59855Comment by John Palmieri for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59854#post-id-59854Essentially all of the time in `unitary_divisors1` is spent in `[... for f in Subsets(factor(n))]`: on my machine, `[f for f in Subsets(factor(N))]` took about the same amount of time as `unitary_divisors1(N)`. Assembling and iterating over the subsets of size 20 is just going to take a while. Maybe the `Subsets` iterator could be made more efficient.Sat, 20 Nov 2021 23:03:47 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59854#post-id-59854Answer by Max Alekseyev for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?answer=59859#post-id-59859My best shot so far is iterating over the divisors of the radical of $n$ and saturating prime powers in them:
def unitary_divisors4(n):
fn = factor(n)
D = [(p,k-1) for p,k in fn if k>1]
return sorted( prod(p^k for p,k in D if d%p==0)*d for d in divisors(prod(p for p,_ in fn)) )Sun, 21 Nov 2021 03:00:40 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?answer=59859#post-id-59859Comment by slelievre for <p>My best shot so far is iterating over the divisors of the radical of $n$ and saturating prime powers in them:</p>
<pre><code>def unitary_divisors4(n):
fn = factor(n)
D = [(p,k-1) for p,k in fn if k>1]
return sorted( prod(p^k for p,k in D if d%p==0)*d for d in divisors(prod(p for p,_ in fn)) )
</code></pre>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59895#post-id-59895Fully agree. A few more things to try...
With `fn = factor(n)`, you can use `fn.radical_value()` to get the radical
(but `prod(p for p, _ in fn)` works too, of course, and may be faster).
Using `fn = list(factor(n))` may win over `fn = factor(n)`
(but then there's no `fn.radical_value()`).
Using `sorted([a for a in b])` may be faster than `sorted(a for a in b)`.
Above all, `subsets` is a lot faster than `Subsets`.
One more variation:
def unitary_divisors7(n):
return sorted([prod(p^k for p, k in f)
for f in subsets(factor(n))])Tue, 23 Nov 2021 01:23:13 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59895#post-id-59895Comment by Max Alekseyev for <p>My best shot so far is iterating over the divisors of the radical of $n$ and saturating prime powers in them:</p>
<pre><code>def unitary_divisors4(n):
fn = factor(n)
D = [(p,k-1) for p,k in fn if k>1]
return sorted( prod(p^k for p,k in D if d%p==0)*d for d in divisors(prod(p for p,_ in fn)) )
</code></pre>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59890#post-id-59890Since we need factorization of $n$ anyway, it's worth to use it for computing the radical (rather than calling function `radical`, which would internally factor `n` again) and factorization of `n // r`.Mon, 22 Nov 2021 21:12:02 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59890#post-id-59890Comment by slelievre for <p>My best shot so far is iterating over the divisors of the radical of $n$ and saturating prime powers in them:</p>
<pre><code>def unitary_divisors4(n):
fn = factor(n)
D = [(p,k-1) for p,k in fn if k>1]
return sorted( prod(p^k for p,k in D if d%p==0)*d for d in divisors(prod(p for p,_ in fn)) )
</code></pre>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59870#post-id-59870Possible variations using `radical(n)` for `prod(p for p, _ in factor(n))`:
def unitary_divisors5(n):
fn = factor(n)
D = [(p, k - 1) for p, k in fn if k > 1]
return sorted(d*prod(p^k for p, k in D if d % p == 0) for d in divisors(radical(n)))
def unitary_divisors6(n):
r = radical(n)
D = factor(n // r) # or list(factor(n // r))
return sorted(d*prod(p^k for p, k in D if d % p == 0) for d in divisors(r))
Computing both `radical(n)` and `factor(n)` or `factor(n // r)`
might end up being a waste of time though...
Not sure whether using `x.radical()`, `x.factor()`, `x.divisors()`
instead of `radical(x)`, `factor(x)`, `divisors(x)` would gain anything
(assuming only Sage integers, never Python integers, are used).Sun, 21 Nov 2021 20:12:59 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59870#post-id-59870Answer by John Palmieri for <p>A divisor $d\mid n$ is called unitary if it is coprime to its cofactor, i.e. $\gcd(d,\frac{n}d)=1$. Since for each prime power $p^k\| n$, we either have $p^k\|d$ or $p\nmid d$, which lead to the following seemingly-efficient code to generate all unitary divisors:</p>
<pre><code>def unitary_divisors1(n):
return sorted( prod(p^k for p,k in f) for f in Subsets(factor(n)) )
</code></pre>
<p>For comparison, the naive approach by filtering the divisors of $n$ would be:</p>
<pre><code>def unitary_divisors2(n):
return [d for d in divisors(n) if gcd(d,n//d)==1]
</code></pre>
<p>From theoretical perspective, <code>unitary_divisors1(n)</code> is much more efficient than <code>unitary_divisors2(n)</code> for powerful/squareful numbers $n$ and should be comparable for square-free numbers $n$. However, in practice <code>unitary_divisors1(n)</code> loses badly to <code>unitary_divisors2(n)</code> when $n$ is square-free (in which case every divisor of $n$ is unitary):</p>
<pre><code>sage: N = prod(nth_prime(i) for i in (1..20))
sage: %time len(unitary_divisors1(N))
CPU times: user 26.8 s, sys: 64 ms, total: 26.9 s
Wall time: 26.9 s
1048576
sage: %time len(unitary_divisors2(N))
CPU times: user 672 ms, sys: 16 ms, total: 688 ms
Wall time: 688 ms
1048576
</code></pre>
<p>In this example with <code>N</code> being the product of first 20 primes, <code>unitary_divisors1(N)</code> is over 40 times slower than <code>unitary_divisors2(N)</code>.</p>
<p>Is there a way to generate unitary divisors that works with efficiency close to <code>divisors(n)</code> when $n$ is squarefree or almost squarefree, and takes advantage of the known structure of unitary divisors?</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?answer=59858#post-id-59858This is not a great answer but it's too long to fit in a comment. With `N` as in the question, it's faster than `unitary_divisors1` but slower than `unitary_divisors2`. Partly taken from the top-ranked answer at https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset, also appearing as the powerset recipe at https://docs.python.org/3/library/itertools.html#recipes.
sage: from itertools import chain, combinations
sage: def unitary_divisors3(n):
....: s = factor(n)
....: C = chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
....: return sorted(prod(p^k for p,k in f) for f in C)
....:
sage: %time L = len(unitary_divisors1(N))
CPU times: user 34.1 s, sys: 242 ms, total: 34.3 s
Wall time: 44.1 s
sage: %time L = len(unitary_divisors2(N))
CPU times: user 1.26 s, sys: 54.2 ms, total: 1.31 s
Wall time: 1.53 s
sage: %time L3 = len(unitary_divisors3(N))
CPU times: user 4.64 s, sys: 74.2 ms, total: 4.71 s
Wall time: 5.88 s
(My system is pretty heavily loaded right now; the timings for the first two were much faster earlier, but these are good for comparisons regardless.)Sun, 21 Nov 2021 01:25:52 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?answer=59858#post-id-59858Comment by Max Alekseyev for <p>This is not a great answer but it's too long to fit in a comment. With <code>N</code> as in the question, it's faster than <code>unitary_divisors1</code> but slower than <code>unitary_divisors2</code>. Partly taken from the top-ranked answer at <a href="https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset">https://stackoverflow.com/questions/1...</a>, also appearing as the powerset recipe at <a href="https://docs.python.org/3/library/itertools.html#recipes">https://docs.python.org/3/library/ite...</a>.</p>
<pre><code>sage: from itertools import chain, combinations
sage: def unitary_divisors3(n):
....: s = factor(n)
....: C = chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
....: return sorted(prod(p^k for p,k in f) for f in C)
....:
sage: %time L = len(unitary_divisors1(N))
CPU times: user 34.1 s, sys: 242 ms, total: 34.3 s
Wall time: 44.1 s
sage: %time L = len(unitary_divisors2(N))
CPU times: user 1.26 s, sys: 54.2 ms, total: 1.31 s
Wall time: 1.53 s
sage: %time L3 = len(unitary_divisors3(N))
CPU times: user 4.64 s, sys: 74.2 ms, total: 4.71 s
Wall time: 5.88 s
</code></pre>
<p>(My system is pretty heavily loaded right now; the timings for the first two were much faster earlier, but these are good for comparisons regardless.)</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59891#post-id-59891I think testing for square-freeness/-fulness require factorization of a number, and since we need factorization of `n` anyway, it makes sense to use it as much as possible (rather than calling Sage functions that would internally factor `n` again).Mon, 22 Nov 2021 21:15:31 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59891#post-id-59891Comment by John Palmieri for <p>This is not a great answer but it's too long to fit in a comment. With <code>N</code> as in the question, it's faster than <code>unitary_divisors1</code> but slower than <code>unitary_divisors2</code>. Partly taken from the top-ranked answer at <a href="https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset">https://stackoverflow.com/questions/1...</a>, also appearing as the powerset recipe at <a href="https://docs.python.org/3/library/itertools.html#recipes">https://docs.python.org/3/library/ite...</a>.</p>
<pre><code>sage: from itertools import chain, combinations
sage: def unitary_divisors3(n):
....: s = factor(n)
....: C = chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
....: return sorted(prod(p^k for p,k in f) for f in C)
....:
sage: %time L = len(unitary_divisors1(N))
CPU times: user 34.1 s, sys: 242 ms, total: 34.3 s
Wall time: 44.1 s
sage: %time L = len(unitary_divisors2(N))
CPU times: user 1.26 s, sys: 54.2 ms, total: 1.31 s
Wall time: 1.53 s
sage: %time L3 = len(unitary_divisors3(N))
CPU times: user 4.64 s, sys: 74.2 ms, total: 4.71 s
Wall time: 5.88 s
</code></pre>
<p>(My system is pretty heavily loaded right now; the timings for the first two were much faster earlier, but these are good for comparisons regardless.)</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59861#post-id-59861How fast is Sage at testing whether something is squarefree or similar? You could have several cases for your function depending on properties of `n`. Certainly in the code I was looking at, factoring `n` was not the slowest part, so this might make sense.Sun, 21 Nov 2021 04:15:02 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59861#post-id-59861Comment by Max Alekseyev for <p>This is not a great answer but it's too long to fit in a comment. With <code>N</code> as in the question, it's faster than <code>unitary_divisors1</code> but slower than <code>unitary_divisors2</code>. Partly taken from the top-ranked answer at <a href="https://stackoverflow.com/questions/1482308/how-to-get-all-subsets-of-a-set-powerset">https://stackoverflow.com/questions/1...</a>, also appearing as the powerset recipe at <a href="https://docs.python.org/3/library/itertools.html#recipes">https://docs.python.org/3/library/ite...</a>.</p>
<pre><code>sage: from itertools import chain, combinations
sage: def unitary_divisors3(n):
....: s = factor(n)
....: C = chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
....: return sorted(prod(p^k for p,k in f) for f in C)
....:
sage: %time L = len(unitary_divisors1(N))
CPU times: user 34.1 s, sys: 242 ms, total: 34.3 s
Wall time: 44.1 s
sage: %time L = len(unitary_divisors2(N))
CPU times: user 1.26 s, sys: 54.2 ms, total: 1.31 s
Wall time: 1.53 s
sage: %time L3 = len(unitary_divisors3(N))
CPU times: user 4.64 s, sys: 74.2 ms, total: 4.71 s
Wall time: 5.88 s
</code></pre>
<p>(My system is pretty heavily loaded right now; the timings for the first two were much faster earlier, but these are good for comparisons regardless.)</p>
https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59860#post-id-59860Thanks. This loses a bit to `unitary_divisors4` from my answer for squarefree $n$, but a bit better for squareful ones.Sun, 21 Nov 2021 03:03:52 +0100https://ask.sagemath.org/question/59852/efficient-generation-of-unitary-divisors/?comment=59860#post-id-59860