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.Sat, 20 Nov 2021 21:48:51 +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?Max AlekseyevSat, 20 Nov 2021 21:48:51 +0100https://ask.sagemath.org/question/59852/