Refactoring of `is_perfect` and `is_mersenne_prime` #25881

haru-44 · 2023-11-07T12:31:19Z

Removed _ismersenneprime and _isperfect. These are functions for computing and storing Mersenne primes and perfect numbers, but no longer refer directly to values. That is, they are now determined by finding an exponent and determining if it exists in MERSENNE_PRIME_EXPONENTS.

References to other Issues or PRs

Brief description of what is fixed or changed

Other comments

Release Notes

ntheory
- Removed _ismersenneprime and _isperfect.

Removed `_ismersenneprime` and `_isperfect`. These are functions for computing and storing Mersenne primes and perfect numbers, but no longer refer directly to values. That is, they are now determined by finding an exponent and determining if it exists in `MERSENNE_PRIME_EXPONENTS`.

sympy-bot · 2023-11-07T12:31:27Z

✅

Hi, I am the SymPy bot. I'm here to help you write a release notes entry. Please read the guide on how to write release notes.

Your release notes are in good order.

Here is what the release notes will look like:

ntheory
- Removed _ismersenneprime and _isperfect. (#25881 by @haru-44 and @smichr)

This will be added to https://github.com/sympy/sympy/wiki/Release-Notes-for-1.13.

Click here to see the pull request description that was parsed.

Removed `_ismersenneprime` and `_isperfect`. These are functions for computing and storing Mersenne primes and perfect numbers, but no longer refer directly to values. That is, they are now determined by finding an exponent and determining if it exists in `MERSENNE_PRIME_EXPONENTS`.

<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->


#### Brief description of what is fixed or changed


#### Other comments


#### Release Notes

<!-- Write the release notes for this release below between the BEGIN and END
statements. The basic format is a bulleted list with the name of the subpackage
and the release note for this PR. For example:

* solvers
  * Added a new solver for logarithmic equations.

* functions
  * Fixed a bug with log of integers. Formerly, `log(-x)` incorrectly gave `-log(x)`.

* physics.units
  * Corrected a semantical error in the conversion between volt and statvolt which
    reported the volt as being larger than the statvolt.

or if no release note(s) should be included use:

NO ENTRY

See https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more
information on how to write release notes. The bot will check your release
notes automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
* ntheory
  * Removed `_ismersenneprime` and `_isperfect`.
<!-- END RELEASE NOTES -->

Update

The release notes on the wiki have been updated.

github-actions · 2023-11-07T13:36:31Z

Benchmark results from GitHub Actions

Lower numbers are good, higher numbers are bad. A ratio less than 1
means a speed up and greater than 1 means a slowdown. Green lines
beginning with + are slowdowns (the PR is slower then master or
master is slower than the previous release). Red lines beginning
with - are speedups.

Significantly changed benchmark results (PR vs master)

Significantly changed benchmark results (master vs previous release)

| Change   | Before [a00718ba]    | After [b45fd026]    |   Ratio | Benchmark (Parameter)                                                |
|----------|----------------------|---------------------|---------|----------------------------------------------------------------------|
| -        | 127±2ms              | 80.5±2ms            |    0.63 | integrate.TimeIntegrationRisch02.time_doit(10)                       |
| +        | 34.3±0.6μs           | 56.0±1μs            |    1.63 | integrate.TimeIntegrationRisch03.time_doit(1)                        |
| -        | 10.3±0.4ms           | 5.15±0.1ms          |    0.5  | logic.LogicSuite.time_load_file                                      |
| -        | 129±4ms              | 45.9±0.9ms          |    0.36 | polys.TimeGCD_GaussInt.time_op(1, 'dense')                           |
| -        | 43.8±2ms             | 27.8±0.5ms          |    0.64 | polys.TimeGCD_GaussInt.time_op(1, 'expr')                            |
| -        | 130±5ms              | 45.1±0.7ms          |    0.35 | polys.TimeGCD_GaussInt.time_op(1, 'sparse')                          |
| -        | 447±6ms              | 200±5ms             |    0.45 | polys.TimeGCD_GaussInt.time_op(2, 'dense')                           |
| -        | 448±8ms              | 199±2ms             |    0.44 | polys.TimeGCD_GaussInt.time_op(2, 'sparse')                          |
| -        | 1.16±0.01s           | 596±10ms            |    0.51 | polys.TimeGCD_GaussInt.time_op(3, 'dense')                           |
| -        | 1.14±0.02s           | 589±20ms            |    0.52 | polys.TimeGCD_GaussInt.time_op(3, 'sparse')                          |
| -        | 905±20μs             | 462±5μs             |    0.51 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(1, 'dense')            |
| -        | 3.22±0.09ms          | 1.85±0.1ms          |    0.57 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(2, 'dense')            |
| -        | 10.1±0.08ms          | 4.92±0.08ms         |    0.49 | polys.TimeGCD_LinearDenseQuadraticGCD.time_op(3, 'dense')            |
| -        | 814±30μs             | 386±8μs             |    0.47 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(1, 'dense')               |
| -        | 2.64±0.07ms          | 1.09±0.02ms         |    0.41 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(2, 'dense')               |
| -        | 8.15±0.2ms           | 2.68±0.06ms         |    0.33 | polys.TimeGCD_QuadraticNonMonicGCD.time_op(3, 'dense')               |
| -        | 681±20μs             | 340±10μs            |    0.5  | polys.TimeGCD_SparseGCDHighDegree.time_op(1, 'dense')                |
| -        | 4.38±0.2ms           | 1.89±0.05ms         |    0.43 | polys.TimeGCD_SparseGCDHighDegree.time_op(3, 'dense')                |
| -        | 17.2±0.4ms           | 6.85±0.3ms          |    0.4  | polys.TimeGCD_SparseGCDHighDegree.time_op(5, 'dense')                |
| -        | 655±20μs             | 273±6μs             |    0.42 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(1, 'dense')            |
| -        | 4.54±0.04ms          | 1.43±0.02ms         |    0.31 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(3, 'dense')            |
| -        | 16.6±0.4ms           | 4.49±0.3ms          |    0.27 | polys.TimeGCD_SparseNonMonicQuadratic.time_op(5, 'dense')            |
| -        | 1.74±0.02ms          | 675±20μs            |    0.39 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'dense')           |
| -        | 2.90±0.06ms          | 826±20μs            |    0.28 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(3, 'sparse')          |
| -        | 10.5±0.6ms           | 2.95±0.08ms         |    0.28 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'dense')           |
| -        | 14.6±0.3ms           | 2.51±0.06ms         |    0.17 | polys.TimePREM_LinearDenseQuadraticGCD.time_op(5, 'sparse')          |
| -        | 454±7μs              | 104±3μs             |    0.23 | polys.TimePREM_QuadraticNonMonicGCD.time_op(1, 'sparse')             |
| -        | 5.83±0.3ms           | 635±30μs            |    0.11 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'dense')              |
| -        | 7.19±0.5ms           | 494±30μs            |    0.07 | polys.TimePREM_QuadraticNonMonicGCD.time_op(3, 'sparse')             |
| -        | 12.0±0.2ms           | 2.16±0.1ms          |    0.18 | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'dense')              |
| -        | 14.6±0.7ms           | 1.39±0.05ms         |    0.09 | polys.TimePREM_QuadraticNonMonicGCD.time_op(5, 'sparse')             |
| -        | 651±20μs             | 418±6μs             |    0.64 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(1, 'dense')  |
| -        | 3.57±0.05ms          | 2.36±0.06ms         |    0.66 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(2, 'dense')  |
| -        | 8.23±0.2ms           | 4.94±0.2ms          |    0.6  | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(2, 'sparse') |
| -        | 20.3±0.6ms           | 10.2±0.2ms          |    0.5  | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'dense')  |
| -        | 36.3±0.6ms           | 15.0±0.2ms          |    0.41 | polys.TimeSUBRESULTANTS_LinearDenseQuadraticGCD.time_op(3, 'sparse') |
| -        | 8.58±0.2ms           | 1.46±0.05ms         |    0.17 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(1, 'sparse')    |
| -        | 20.4±0.6ms           | 11.1±0.2ms          |    0.54 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(2, 'sparse')    |
| -        | 183±3ms              | 42.4±0.9ms          |    0.23 | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'dense')     |
| -        | 296±3ms              | 89.2±2ms            |    0.3  | polys.TimeSUBRESULTANTS_QuadraticNonMonicGCD.time_op(3, 'sparse')    |
| -        | 298±2μs              | 175±9μs             |    0.59 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(1, 'dense')      |
| -        | 618±10μs             | 346±5μs             |    0.56 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(1, 'sparse')     |
| -        | 7.34±0.4ms           | 1.35±0.02ms         |    0.18 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'dense')      |
| -        | 10.2±0.7ms           | 630±20μs            |    0.06 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(3, 'sparse')     |
| -        | 36.2±2ms             | 4.51±0.1ms          |    0.12 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'dense')      |
| -        | 40.4±2ms             | 1.05±0.03ms         |    0.03 | polys.TimeSUBRESULTANTS_SparseGCDHighDegree.time_op(5, 'sparse')     |
| -        | 838±60μs             | 214±6μs             |    0.26 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(1, 'sparse') |
| -        | 8.26±0.2ms           | 993±10μs            |    0.12 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'dense')  |
| -        | 9.23±0.2ms           | 209±4μs             |    0.02 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(3, 'sparse') |
| -        | 23.3±0.8ms           | 2.22±0.07ms         |    0.1  | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'dense')  |
| -        | 24.6±0.7ms           | 217±5μs             |    0.01 | polys.TimeSUBRESULTANTS_SparseNonMonicQuadratic.time_op(5, 'sparse') |
| -        | 224±6μs              | 128±4μs             |    0.57 | solve.TimeMatrixOperations.time_rref(3, 0)                           |
| -        | 429±10μs             | 153±5μs             |    0.36 | solve.TimeMatrixOperations.time_rref(4, 0)                           |
| -        | 43.9±1ms             | 18.6±0.9ms          |    0.42 | solve.TimeSolveLinSys189x49.time_solve_lin_sys                       |

Full benchmark results can be found as artifacts in GitHub Actions
(click on checks at the top of the PR).

smichr · 2023-11-07T14:58:04Z

sympy/ntheory/factor_.py

@@ -2468,60 +2442,37 @@ def is_perfect(n):
    .. [2] https://en.wikipedia.org/wiki/Perfect_number

    """
+    n = as_int(abs(n))


Use of abs is going to allow this to give an answer when the assumption system would say there should be none (since negatives are not prime).

This would also be a change in behavior from master where is_perfect(-28) -> False

smichr · 2023-11-07T19:17:47Z

sympy/ntheory/factor_.py

-    if _ismersenneprime(n):
-        return True
-    if not isprime(n):
+    n = as_int(abs(n))


ditto here with sign -is_mersenne_prime(-7) -> False.

sympy/ntheory/factor_.py

haru-44 · 2023-11-07T22:34:12Z

As you pointed out, it was not correct to take absolute values. But is that fix as intended?
I believe that negative numbers should always return False.

smichr · 2023-11-08T04:10:07Z

All negatives (and those less than the first number of the type) return False

>>> any(is_perfect(i) for i in range(-1,6))
False
>>> any(is_mersenne_prime(i) for i in range(-1,3))
False

haru-44 · 2023-11-08T10:28:19Z

In the merged code, the results of -n and -n equal.

>>> is_perfect(-28)
True

The following condition would be appropriate.

n = as_int(n)
if n <= 1:
    return False

smichr · 2023-11-08T14:36:46Z

Thanks for the demonstration. I'll open a PR for that.

smichr reviewed Nov 7, 2023

View reviewed changes

sympy/ntheory/factor_.py Outdated Show resolved Hide resolved

smichr reviewed Nov 7, 2023

View reviewed changes

sympy/ntheory/factor_.py Outdated Show resolved Hide resolved

return False for negative ints

2183799

smichr enabled auto-merge November 7, 2023 22:08

smichr merged commit 9554f76 into sympy:master Nov 7, 2023

haru-44 deleted the is_perfect_is_mersenne branch November 14, 2023 13:47

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Uh oh!

Refactoring of `is_perfect` and `is_mersenne_prime` #25881

Refactoring of `is_perfect` and `is_mersenne_prime` #25881

Uh oh!

haru-44 commented Nov 7, 2023

Uh oh!

sympy-bot commented Nov 7, 2023 •

edited

Loading

Uh oh!

github-actions bot commented Nov 7, 2023 •

edited

Loading

Uh oh!

smichr Nov 7, 2023

Uh oh!

smichr Nov 7, 2023

Uh oh!

smichr Nov 7, 2023

Uh oh!

Uh oh!

Uh oh!

haru-44 commented Nov 7, 2023

Uh oh!

smichr commented Nov 8, 2023

Uh oh!

haru-44 commented Nov 8, 2023

Uh oh!

smichr commented Nov 8, 2023

Uh oh!

Uh oh!

Uh oh!

Refactoring of is_perfect and is_mersenne_prime #25881

Refactoring of is_perfect and is_mersenne_prime #25881

Uh oh!

Conversation

haru-44 commented Nov 7, 2023

References to other Issues or PRs

Brief description of what is fixed or changed

Other comments

Release Notes

Uh oh!

sympy-bot commented Nov 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions bot commented Nov 7, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

smichr Nov 7, 2023

Choose a reason for hiding this comment

Uh oh!

smichr Nov 7, 2023

Choose a reason for hiding this comment

Uh oh!

smichr Nov 7, 2023

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

haru-44 commented Nov 7, 2023

Uh oh!

smichr commented Nov 8, 2023

Uh oh!

haru-44 commented Nov 8, 2023

Uh oh!

smichr commented Nov 8, 2023

Uh oh!

Uh oh!

Refactoring of `is_perfect` and `is_mersenne_prime` #25881

Refactoring of `is_perfect` and `is_mersenne_prime` #25881

sympy-bot commented Nov 7, 2023 •

edited

Loading

github-actions bot commented Nov 7, 2023 •

edited

Loading