CF 102697070 - Mersenne Primes

Rating: -
Tags: -
Solve time: 2m 2s
Verified: yes

Solution

Problem Understanding

A Mersenne number has the form

[ M_p = 2^p - 1. ]

The input contains the exponent (p), and the task is to decide whether (M_p) is actually prime. The required output is the lowercase word true when it is prime and false otherwise. The official problem specifically asks for the Lucas-Lehmer primality test, because directly constructing a huge number and testing it with ordinary trial division quickly becomes infeasible. The statement also warns that intermediate values may exceed 32-bit or 64-bit integers, so arbitrary-precision arithmetic is required.

The official constraints do not give a numerical upper bound for (p). What they do make clear is that the intended method must work with numbers whose size can exceed standard machine integers, under a one-second time limit and 256 MB of memory. In Python, this means we should use its arbitrary-precision integers directly and avoid any algorithm that tries to enumerate divisors of (2^p-1). The Lucas-Lehmer test performs (p-2) modular iterations, and every value remains below (2^p-1), so the memory requirement is proportional to the size of the Mersenne number rather than to its numerical value.

There are several small cases that can make a careless implementation fail. For (p=2), the number is (2^2-1=3), which is prime, so the output for input 2 is true. A loop written as for _ in range(p - 2) handles this naturally by performing zero iterations, but only if the initial value is treated correctly.

For a composite exponent, the Mersenne number cannot be prime. For example, input 4 gives

[ 2^4-1=15, ]

so the correct output is false. An implementation that blindly assumes every input exponent is prime and runs the Lucas-Lehmer recurrence can violate the theorem's precondition.

The distinction between a prime exponent and a Mersenne prime is another common trap. Input 11 has a prime exponent, but

[ 2^{11}-1=2047=23\cdot89, ]

so the correct output is false. Simply testing whether (p) is prime is not sufficient.

Finally, the intermediate sequence can be much larger than 64-bit integers even when the final answer is only one Boolean value. For example, (p=61) produces a Mersenne number with 61 bits. A C++ solution would need a big-integer library, while Python's built-in int already provides the required arithmetic.

Approaches

The most direct approach is to construct (M_p=2^p-1), then test it with ordinary primality testing. Trial division is correct because a composite integer must have a divisor no larger than its square root. The problem is the size of that square root. Since

[ \sqrt{2^p-1}\approx2^{p/2}, ]

the worst case requires on the order of (2^{p/2}) divisibility checks. Even (p=61) already means checking on the scale of billions of possible divisors, so this approach is completely unsuitable.

A better approach comes from the special structure of Mersenne numbers. For a prime exponent (p), the Lucas-Lehmer theorem says that (M_p=2^p-1) is prime exactly when a particular recurrence ends at zero modulo (M_p). Start with (s_0=4), and repeatedly calculate

[ s_{i+1}=(s_i^2-2)\bmod M_p. ]

After exactly (p-2) iterations, (M_p) is prime if and only if the resulting value is zero. The official problem is explicitly designed around this test.

The brute-force method works because it tries to establish primality from the definition, but it fails because the number being tested has exponentially many possible values relative to (p). The Lucas-Lehmer observation lets us replace that enormous search with only (p-2) modular squarings. The arithmetic is still performed on a (p)-bit integer, but that is vastly smaller than examining (2^{p/2}) possible divisors.

Before applying the recurrence, we can reject composite (p). If (p) is composite, (2^p-1) is also composite. Checking whether (p) itself is prime costs only (O(\sqrt p)), which is negligible compared with the Lucas-Lehmer work for large prime exponents. The special case (p=2) is accepted immediately.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	(O(2^{p/2})) divisibility checks	(O(p)) bits	Too slow
Optimal	(O(p)) big-integer iterations	(O(p)) bits	Accepted

The (O(p)) description counts Lucas-Lehmer iterations and treats each arbitrary-precision arithmetic operation as one operation. In a bit-level model, the cost is higher because squaring a (p)-bit integer is not constant time, but the crucial improvement is replacing exponential iteration count with linear iteration count.

Algorithm Walkthrough

Read the exponent (p). We only have one test case because the input consists of a single integer.
If (p=2), print true immediately. The corresponding Mersenne number is (3), which is prime, and the Lucas-Lehmer recurrence is normally defined separately for this smallest exponent.
Check whether (p) is prime. If it is composite, print false.

This rejection follows from the factorization

[ 2^{ab}-1=(2^a)^b-1, ]

which is divisible by (2^a-1) whenever (p=ab). Thus a composite exponent can never produce a prime Mersenne number. 4. Construct the Mersenne number as m = (1 << p) - 1. The left shift creates exactly (2^p), and subtracting one gives (2^p-1). 5. Initialize the Lucas-Lehmer state with s = 4. This is the fixed starting value specified by the theorem. 6. Repeat the recurrence exactly (p-2) times. In every iteration replace s with

[ (s^2-2)\bmod m. ]

The modulo operation is performed after squaring so that the stored state never needs to grow beyond the modulus itself. Without the modulo operation, the intermediate integer would grow explosively from one iteration to the next. 7. Print true if the final value of s is zero, and false otherwise. For a prime exponent, the Lucas-Lehmer theorem makes this zero test both necessary and sufficient for (M_p) to be prime.

Why it works: after the initialization, the variable s is exactly the corresponding term of the Lucas-Lehmer sequence modulo (M_p). Each loop iteration applies the recurrence defining the next term, so after (p-2) iterations it contains (s_{p-2}\bmod M_p). The Lucas-Lehmer theorem states that for prime (p>2), (2^p-1) is prime exactly when (s_{p-2}=0\pmod{M_p}). Composite exponents were already rejected separately, and (p=2) was handled directly. Every possible input consequently reaches the correct Boolean result.

Python Solution

import sys
input = sys.stdin.readline

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2

    return True

def solve():
    p = int(input())

    if p == 2:
        print("true")
        return

    if not is_prime(p):
        print("false")
        return

    m = (1 << p) - 1
    s = 4

    for _ in range(p - 2):
        s = (s * s - 2) % m

    print("true" if s == 0 else "false")

if __name__ == "__main__":
    solve()

The is_prime function is only applied to the exponent, not to the enormous Mersenne number. It checks divisibility up to (\sqrt p), skipping even candidates after handling 2.

The expression (1 << p) - 1 is preferable to 2 ** p - 1 here because it directly expresses the binary structure of the Mersenne number. Python integers have arbitrary precision, so this expression and the subsequent squaring work even when the value no longer fits in 64 bits.

The loop runs p - 2 times, not p - 1 or p - 3. The Lucas-Lehmer theorem starts with (s_0=4) and requires (s_{p-2}), which is reached after exactly (p-2) recurrence applications.

The expression (s * s - 2) % m must keep the modulo operation inside the loop. Reducing only after all iterations would create numbers vastly larger than (M_p), making the implementation unusable.

Python's arbitrary-precision integers also avoid the overflow problem mentioned by the original statement.

Worked Examples

Sample 1

Input:

Here (p=7) is prime, so the Lucas-Lehmer test applies. The modulus is

[ M_7=2^7-1=127. ]

Iteration	(s) before	(s^2-2) modulo 127	(s) after
Initial	4		4
1	4	14	14
2	14	194	194 mod 127 = 67
3	67	4487	4487 mod 127 = 39
4	39	1519	1519 mod 127 = 122
5	122	14882	14882 mod 127 = 0

There are exactly (7-2=5) iterations, and the final state is zero. Hence (127) is prime and the output is true.

Sample 2

Input:

The exponent (15) is composite, so the algorithm rejects it before constructing (2^{15}-1).

Step	(p)	Prime exponent?	Result
Read input	15
Prime check	15	No, (15=3\cdot5)	`false`

The output is:

false

This trace demonstrates why testing the exponent first is useful. Since a composite exponent can never produce a prime Mersenne number, there is no reason to perform the Lucas-Lehmer recurrence.

Complexity Analysis

Measure	Complexity	Explanation
Time	(O(\sqrt p + p)) big-integer iterations	The exponent primality test costs (O(\sqrt p)), followed by (p-2) Lucas-Lehmer iterations
Space	(O(p)) bits	The modulus and Lucas-Lehmer state contain at most (p) bits

The official statement gives a one-second time limit and 256 MB of memory, but does not publish a numerical upper bound for (p) on the current problem page. The intended algorithm is nevertheless clear from the required Lucas-Lehmer test and the explicit warning about arbitrary precision. For the intended input range, the decisive improvement is that the algorithm performs (p-2) modular iterations rather than approximately (2^{p/2}) trial divisions.

Test Cases

The current Codeforces page provides the two samples 7 and 15, but no numerical maximum for (p), so a literal maximum-size test cannot be derived from the published statement. The custom suite below uses known Mersenne-prime exponents and nearby composite or non-Mersenne-prime cases to exercise the implementation.

import sys
import io

def is_prime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2

    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2

    return True

def mersenne_prime(p):
    if p == 2:
        return True

    if not is_prime(p):
        return False

    m = (1 << p) - 1
    s = 4

    for _ in range(p - 2):
        s = (s * s - 2) % m

    return s == 0

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    p = int(sys.stdin.readline())
    return "true\n" if mersenne_prime(p) else "false\n"

# Provided samples
assert run("7\n") == "true\n", "sample 1"
assert run("15\n") == "false\n", "sample 2"

# Minimum valid exponent
assert run("2\n") == "true\n", "p = 2"

# Small composite exponent
assert run("4\n") == "false\n", "composite exponent"

# Prime exponent, but not a Mersenne prime
assert run("11\n") == "false\n", "2^11 - 1 is composite"

# Larger known Mersenne-prime exponent
assert run("31\n") == "true\n", "p = 31"

# Larger boundary-style test with a prime exponent that is not a
# Mersenne-prime exponent
assert run("23\n") == "false\n", "2^23 - 1 is composite"

Test input	Expected output	What it validates
`2`	`true`	Smallest Mersenne prime and zero Lucas-Lehmer iterations
`4`	`false`	Composite exponent rejection
`11`	`false`	Prime exponent does not imply a Mersenne prime
`31`	`true`	Larger successful Lucas-Lehmer computation
`23`	`false`	Lucas-Lehmer detects a composite Mersenne number

Edge Cases

For 2, the input is:

The algorithm enters the explicit base case and prints true. Without this case, an implementation might try to use the general recurrence even though the theorem's iterative form is stated for prime exponents greater than two.

For a composite exponent such as:

the prime check fails because (4) is divisible by (2). The algorithm immediately prints false, which agrees with

[ 2^4-1=15. ]

A careless implementation that only checks the Lucas-Lehmer final state without respecting the prime-exponent condition could apply a theorem outside its stated domain.

For a prime exponent that does not produce a Mersenne prime, consider:

The exponent passes the primality check. The modulus becomes

[ 2^{11}-1=2047. ]

The Lucas-Lehmer recurrence is then executed for (11-2=9) iterations. Its final state is nonzero modulo (2047), so the program prints false. This catches the common mistake of returning true merely because (p) is prime.

For a successful larger case:

the exponent is prime and the modulus is

[ 2^{31}-1=2147483647. ]

The Lucas-Lehmer sequence reaches zero after (29) iterations, so the output is true. This case also exercises arbitrary-precision arithmetic at a size beyond signed 32-bit integers, matching the concern raised in the original statement.