.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/number_theory/primality/plot_02_lucas_lehmer.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_number_theory_primality_plot_02_lucas_lehmer.py>`
        to download the full example code.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_number_theory_primality_plot_02_lucas_lehmer.py:


Mersenne primes and the Lucas-Lehmer test
===================================================

The Lucas-Lehmer test decides whether :math:`M_p = 2^p - 1` is prime
with only :math:`p - 2` modular squarings. This script rediscovers
every Mersenne prime with exponent below 1300 -- including
:math:`M_{521}` through :math:`M_{1279}`, found by Raphael Robinson on
the SWAC computer in 1952 -- and plots the exponents, which grow roughly
geometrically.

.. GENERATED FROM PYTHON SOURCE LINES 14-19

.. code-block:: Python

    import matplotlib.pyplot as plt
    import numpy as np

    from mathematicskit.number_theory import lucas_lehmer, sieve_of_eratosthenes








.. GENERATED FROM PYTHON SOURCE LINES 20-22

Search every prime exponent below 1300
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 22-28

.. code-block:: Python


    exponents = [int(p) for p in sieve_of_eratosthenes(1300) if lucas_lehmer(int(p))]
    print("Mersenne prime exponents:", exponents)
    print(f"M_1279 has {len(str(2**1279 - 1))} decimal digits")
    print("M_11 = 2047 = 23 * 89 is composite:", not lucas_lehmer(11))





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    Mersenne prime exponents: [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279]
    M_1279 has 386 decimal digits
    M_11 = 2047 = 23 * 89 is composite: True




.. GENERATED FROM PYTHON SOURCE LINES 29-31

Exponents grow geometrically
-----------------------------------------------------

.. GENERATED FROM PYTHON SOURCE LINES 31-38

.. code-block:: Python


    fig, ax = plt.subplots()
    ax.semilogy(np.arange(1, len(exponents) + 1), exponents, "o-")
    ax.set_xlabel("n (n-th Mersenne prime)")
    ax.set_ylabel("exponent p")
    ax.set_title("Mersenne prime exponents below 1300")
    plt.show()



.. image-sg:: /api/gallery/number_theory/primality/images/sphx_glr_plot_02_lucas_lehmer_001.png
   :alt: Mersenne prime exponents below 1300
   :srcset: /api/gallery/number_theory/primality/images/sphx_glr_plot_02_lucas_lehmer_001.png
   :class: sphx-glr-single-img






.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.241 seconds)


.. _sphx_glr_download_api_gallery_number_theory_primality_plot_02_lucas_lehmer.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_02_lucas_lehmer.ipynb <plot_02_lucas_lehmer.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_02_lucas_lehmer.py <plot_02_lucas_lehmer.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_02_lucas_lehmer.zip <plot_02_lucas_lehmer.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_