malachite_nz/integer/factorization/
is_power.rs

1// Copyright © 2026 Mikhail Hogrefe
2//
3// This file is part of Malachite.
4//
5// Malachite is free software: you can redistribute it and/or modify it under the terms of the GNU
6// Lesser General Public License (LGPL) as published by the Free Software Foundation; either version
7// 3 of the License, or (at your option) any later version. See <https://www.gnu.org/licenses/>.
8
9use crate::integer::Integer;
10use crate::natural::Natural;
11use malachite_base::num::arithmetic::traits::{CheckedRoot, UnsignedAbs};
12use malachite_base::num::basic::traits::NegativeOne;
13use malachite_base::num::factorization::traits::{ExpressAsPower, IsPower, Primes};
14use malachite_base::num::logic::traits::SignificantBits;
15
16// A negative value is a perfect power exactly when its absolute value is a perfect $p$th power for
17// some odd prime $p$: if $x = a^b$ with $b > 1$ and $x < 0$ then $b$ is odd, so $b$ has an odd
18// prime factor $p$ and $x = (a^{b/p})^p$; conversely $|x| = c^p$ with $p$ odd gives $x = (-c)^p$.
19// Only exponents up to the bit length can work, since the smallest $p$th power above 1 is $2^p$.
20fn negative_power_root(abs: &Natural, exp: u64) -> Option<Natural> {
21    abs.checked_root(exp)
22}
23
24fn odd_prime_exponents(abs: &Natural) -> impl Iterator<Item = u64> {
25    u64::primes_less_than_or_equal_to(&abs.significant_bits()).skip(1)
26}
27
28impl IsPower for Integer {
29    /// Determines whether an [`Integer`] is a perfect power.
30    ///
31    /// A perfect power is any number of the form $a^x$ where $x > 1$, with $a$ and $x$ both
32    /// integers. In particular, 0 and 1 are considered perfect powers.
33    ///
34    /// A negative [`Integer`] can only be an odd perfect power, since an even power is
35    /// non-negative. For instance $-8 = (-2)^3$ is a perfect power but $-16$ is not, and $-1$ is,
36    /// being $(-1)^3$.
37    ///
38    /// # Worst-case complexity
39    /// $T(n) = O(n (\log n)^2 \log\log n)$
40    ///
41    /// $M(n) = O(n \log n)$
42    ///
43    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
44    ///
45    /// # Examples
46    /// ```
47    /// use malachite_base::num::basic::traits::{NegativeOne, One, Zero};
48    /// use malachite_base::num::factorization::traits::IsPower;
49    /// use malachite_nz::integer::Integer;
50    ///
51    /// assert_eq!(Integer::ZERO.is_power(), true);
52    /// assert_eq!(Integer::ONE.is_power(), true);
53    /// assert_eq!(Integer::from(8).is_power(), true);
54    /// assert_eq!(Integer::from(6).is_power(), false);
55    ///
56    /// assert_eq!(Integer::NEGATIVE_ONE.is_power(), true);
57    /// assert_eq!(Integer::from(-8).is_power(), true);
58    /// assert_eq!(Integer::from(-16).is_power(), false);
59    /// ```
60    fn is_power(&self) -> bool {
61        if *self >= 0 {
62            return self.unsigned_abs_ref().is_power();
63        }
64        let abs = self.unsigned_abs();
65        // -1 is (-1)^3, but its bit length admits no exponent below
66        abs == 1u32 || odd_prime_exponents(&abs).any(|p| negative_power_root(&abs, p).is_some())
67    }
68}
69
70impl ExpressAsPower for Integer {
71    /// Expresses an [`Integer`] as a perfect power if possible.
72    ///
73    /// Returns `Some((root, exponent))` where `root ^ exponent = self` and `exponent > 1`, or
74    /// `None` if the number cannot be expressed as a perfect power.
75    ///
76    /// The exponent returned for a negative [`Integer`] is always odd, since an even power is
77    /// non-negative.
78    ///
79    /// # Worst-case complexity
80    /// $T(n) = O(n (\log n)^2 \log\log n)$
81    ///
82    /// $M(n) = O(n \log n)$
83    ///
84    /// where $T$ is time, $M$ is additional memory, and $n$ is `self.significant_bits()`.
85    ///
86    /// # Examples
87    /// ```
88    /// use malachite_base::num::basic::traits::Two;
89    /// use malachite_base::num::factorization::traits::ExpressAsPower;
90    /// use malachite_nz::integer::Integer;
91    ///
92    /// assert_eq!(Integer::from(8).express_as_power(), Some((Integer::TWO, 3)));
93    /// assert_eq!(Integer::from(6).express_as_power(), None);
94    ///
95    /// assert_eq!(
96    ///     Integer::from(-8).express_as_power(),
97    ///     Some((Integer::from(-2), 3))
98    /// );
99    /// assert_eq!(Integer::from(-16).express_as_power(), None);
100    /// ```
101    fn express_as_power(&self) -> Option<(Self, u64)> {
102        if *self >= 0 {
103            return self
104                .unsigned_abs_ref()
105                .express_as_power()
106                .map(|(root, exp)| (Self::from(root), exp));
107        }
108        let abs = self.unsigned_abs();
109        if abs == 1u32 {
110            // -1 = (-1)^3
111            return Some((Self::NEGATIVE_ONE, 3));
112        }
113        odd_prime_exponents(&abs)
114            .find_map(|p| negative_power_root(&abs, p).map(|root| (-Self::from(root), p)))
115    }
116}
malachite_nz/integer/factorization/is_power.rs

malachite_nz/integer/factorization/
is_power.rs
