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.Fri, 19 Nov 2021 03:13:56 +0100multiplicative functions for factored integershttps://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/Since integer factorization is rather expensive computationally, its result sometimes represent quite a valuable piece of information that we do not want to recompute. Sage provides `Factorization` object for dealing factored integer (and more generally rational) numbers, and even supports multiplication / division of such integers - like `factor(1000) / factor(10)`.
However, while it is easy to compute multiplicative functions for a given `Factorization` object, such standard multiplicative functions as `number_of_divisors()`, `sigma()`, `divisors()`, etc. are missing for `Factorization` objects. Also, `factor()` function should also trivially work for them, returning just the given `Factorization` object (currently we get a weird error like `TypeError: unable to factor 2 * 5`).
Do I miss something here?Thu, 18 Nov 2021 17:50:14 +0100https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/Answer by Max Alekseyev for <p>Since integer factorization is rather expensive computationally, its result sometimes represent quite a valuable piece of information that we do not want to recompute. Sage provides <code>Factorization</code> object for dealing factored integer (and more generally rational) numbers, and even supports multiplication / division of such integers - like <code>factor(1000) / factor(10)</code>.</p>
<p>However, while it is easy to compute multiplicative functions for a given <code>Factorization</code> object, such standard multiplicative functions as <code>number_of_divisors()</code>, <code>sigma()</code>, <code>divisors()</code>, etc. are missing for <code>Factorization</code> objects. Also, <code>factor()</code> function should also trivially work for them, returning just the given <code>Factorization</code> object (currently we get a weird error like <code>TypeError: unable to factor 2 * 5</code>).</p>
<p>Do I miss something here?</p>
https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?answer=59828#post-id-59828Added this RFE as https://trac.sagemath.org/ticket/32900Fri, 19 Nov 2021 03:13:56 +0100https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?answer=59828#post-id-59828Answer by slelievre for <p>Since integer factorization is rather expensive computationally, its result sometimes represent quite a valuable piece of information that we do not want to recompute. Sage provides <code>Factorization</code> object for dealing factored integer (and more generally rational) numbers, and even supports multiplication / division of such integers - like <code>factor(1000) / factor(10)</code>.</p>
<p>However, while it is easy to compute multiplicative functions for a given <code>Factorization</code> object, such standard multiplicative functions as <code>number_of_divisors()</code>, <code>sigma()</code>, <code>divisors()</code>, etc. are missing for <code>Factorization</code> objects. Also, <code>factor()</code> function should also trivially work for them, returning just the given <code>Factorization</code> object (currently we get a weird error like <code>TypeError: unable to factor 2 * 5</code>).</p>
<p>Do I miss something here?</p>
https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?answer=59820#post-id-59820Great idea. Please open a ticket for that if there is not already one.
One thing to decide is, for partial factorisations such as:
sage: f = Factorization([(10, 1), (20, 1)])
sage: f
10 * 20
whether `f.factor()` and `factor(f)` should factor them further.
Somewhat related:
- [Sage Trac ticket 18917: Speed up NumberField.zeta()](https://trac.sagemath.org/ticket/18917)
- [Sage Trac ticket 31686: Speed up factoring finite field multiplicative order](https://trac.sagemath.org/ticket/31686)Thu, 18 Nov 2021 18:34:41 +0100https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?answer=59820#post-id-59820Comment by slelievre for <p>Great idea. Please open a ticket for that if there is not already one.</p>
<p>One thing to decide is, for partial factorisations such as:</p>
<pre><code>sage: f = Factorization([(10, 1), (20, 1)])
sage: f
10 * 20
</code></pre>
<p>whether <code>f.factor()</code> and <code>factor(f)</code> should factor them further.</p>
<p>Somewhat related:</p>
<ul>
<li><a href="https://trac.sagemath.org/ticket/18917">Sage Trac ticket 18917: Speed up NumberField.zeta()</a></li>
<li><a href="https://trac.sagemath.org/ticket/31686">Sage Trac ticket 31686: Speed up factoring finite field multiplicative order</a></li>
</ul>
https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?comment=59824#post-id-59824I would run `is_prime` on each factor.
The `factor` method for factorisations could offer
an optional argument `check=True` that could be set
to `False` if one knows the factors to be prime.Thu, 18 Nov 2021 19:16:56 +0100https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?comment=59824#post-id-59824Comment by Max Alekseyev for <p>Great idea. Please open a ticket for that if there is not already one.</p>
<p>One thing to decide is, for partial factorisations such as:</p>
<pre><code>sage: f = Factorization([(10, 1), (20, 1)])
sage: f
10 * 20
</code></pre>
<p>whether <code>f.factor()</code> and <code>factor(f)</code> should factor them further.</p>
<p>Somewhat related:</p>
<ul>
<li><a href="https://trac.sagemath.org/ticket/18917">Sage Trac ticket 18917: Speed up NumberField.zeta()</a></li>
<li><a href="https://trac.sagemath.org/ticket/31686">Sage Trac ticket 31686: Speed up factoring finite field multiplicative order</a></li>
</ul>
https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?comment=59822#post-id-59822Is there a way to quickly recognize whether a given factorization is partial or complete?Thu, 18 Nov 2021 18:42:17 +0100https://ask.sagemath.org/question/59819/multiplicative-functions-for-factored-integers/?comment=59822#post-id-59822