Aliquot 3-cycle

"""Verifier for "Aliquot 3-cycle" (statement in sociable_3_cycle.json).

Background: s(n), the aliquot sum of n, is the sum of the divisors of n other
than n itself, i.e. s(n) = sigma(n) - n where sigma(n) is the sum of all
divisors. For example s(12) = 1 + 2 + 3 + 4 + 6 = 16. Repeatedly applying s
can return to the starting number:
  - cycle of length 1: perfect numbers, e.g. s(6) = 6;
  - cycle of length 2: amicable pairs, e.g. s(220) = 284 and s(284) = 220;
  - cycles of lengths 4, 5, 6, 8, 9 and 28 are known too.

Problem: find a cycle of length 3, i.e. three distinct positive integers with

    s(n1) == n2,   s(n2) == n3,   s(n3) == n1

No such cycle has ever been found.

Computing sigma(n) requires the prime factorisation of n, which the verifier
cannot find for large n. So the solver supplies the factorisation of every
number, and the verifier checks it: every listed factor must be a proven
prime, and their product must be exactly n.

Expected submission: a JSON object with a list of CYCLE_LEN entries, each
holding a number and its factorisation as [prime, exponent] pairs:

    {"cycle": [
      {"n": "12", "factors": [["2", "2"], ["3", "1"]]},
      {"n": "16", "factors": [["2", "4"]]},
      {"n": "15", "factors": [["3", "1"], ["5", "1"]]}
    ]}

What the verifier checks, in order:
  1. The payload is at most MAX_BYTES characters and is a JSON object with
     exactly the key "cycle".
  2. "cycle" is a list of exactly CYCLE_LEN entries.
  3. For each entry: it is an object with exactly the keys "n" and "factors";
     n is a well-formed decimal string of at most MAX_DIGITS digits; the
     factorisation is valid (see _parse_factorisation) and multiplies out to
     exactly n. sigma(n), and so s(n) = sigma(n) - n, is computed from it.
  4. The numbers are pairwise distinct (skipped when CYCLE_LEN is 1).
     Without this, the perfect number 6 repeated three times would pass.
  5. Each number maps to the next one: s(c[0]) == c[1], s(c[1]) == c[2], and
     s(c[last]) == c[0] to close the cycle.
"""
import json
import math

from sympy import isprime

# Length of the cycle to find. The tests set it to 1 (perfect numbers) and
# 2 (amicable pairs) to check that known cycles are accepted.
CYCLE_LEN = 3
# Maximum number of digits of each n.
MAX_DIGITS = 10_000
# Maximum number of digits of each prime in a factorisation. Below about
# 3.3 * 10**24, sympy's isprime gives a proven answer rather than a probable one.
MAX_PRIME_DIGITS = 24
# Maximum size of the whole submission, in characters.
MAX_BYTES = 200_000


# ---------------------------------------------------------------------------
# Input-parsing helpers. The same code is copied into every verifier that
# needs it, so that each file works on its own.
# ---------------------------------------------------------------------------

def _parse_int(s, max_digits, allow_neg=False):
    """Convert a strictly formatted decimal string to an int, or raise ValueError.

    Accepted: "0", "42", and "-42" when allow_neg is True.
    Rejected: anything that is not a string (for example a JSON number), "",
    "+42", " 42", "007", "-0", non-ASCII digits such as "٣", and strings with
    more than max_digits digits.
    """
    # Cheap length check before any real work: at most max_digits digits,
    # plus one character for an optional minus sign.
    if not isinstance(s, str) or len(s) > max_digits + 1:
        raise ValueError
    # Split off the sign. A "-" is only allowed where negative values make sense.
    neg = s.startswith("-")
    if neg and not allow_neg:
        raise ValueError
    body = s[1:] if neg else s
    # What remains must be 1 to max_digits ASCII digits with no leading zero
    # ("0" on its own is fine). isascii() is needed because isdigit() also
    # accepts digits from other scripts.
    if not (body.isascii() and body.isdigit()) or len(body) > max_digits or (len(body) > 1 and body[0] == "0"):
        raise ValueError
    # "-0" is not a canonical way to write zero.
    if neg and body == "0":
        raise ValueError
    # Python (3.11 and later) refuses int() on strings longer than 4300 digits
    # by default, so the number is built from chunks of 4000 digits.
    n = 0
    for i in range(0, len(body), 4000):
        chunk = body[i:i + 4000]
        n = n * 10 ** len(chunk) + int(chunk)
    return -n if neg else n


def _load(solution, keys, max_bytes):
    """Parse the submission as a JSON object with exactly the given keys, or raise."""
    # Refuse oversized payloads before handing them to the JSON parser.
    if not isinstance(solution, str) or len(solution) > max_bytes:
        raise ValueError
    d = json.loads(solution)
    # It must be an object (not a list, string or number) whose keys are
    # exactly the expected ones: nothing missing, nothing extra.
    if not isinstance(d, dict) or set(d) != set(keys):
        raise ValueError
    return d


def _parse_factorisation(factors, max_prime_digits, max_bits):
    """Validate a claimed prime factorisation and return it as a list of (p, e) ints.

    `factors` is a JSON list of [p, e] pairs of decimal strings, meaning
    n = p1**e1 * p2**e2 * ... (the empty list stands for n = 1). Each p must
    be a prime of at most max_prime_digits digits and may appear only once;
    each exponent e must be between 1 and 999999. Raises ValueError otherwise.

    max_bits guards against absurd inputs such as [["2", "999999"]], whose
    product would have a million bits. Every prime p is at least
    2**(bit length of p - 1), so the product is at least 2**bits, where bits
    is the running total of e * (bit length of p - 1). Once that total exceeds
    max_bits (the size of the number the factorisation is meant to reproduce),
    the factorisation cannot be right and is rejected. Callers can therefore
    multiply the returned pairs out without risk.
    """
    if not isinstance(factors, list):
        raise ValueError
    pairs, seen, bits = [], set(), 0
    for item in factors:
        # Each item must be a two-element list [p, e].
        if not (isinstance(item, list) and len(item) == 2):
            raise ValueError
        p = _parse_int(item[0], max_prime_digits)
        e = _parse_int(item[1], 6)
        # p must be at least 2 and not repeated; e must be at least 1.
        if p < 2 or p in seen or e < 1:
            raise ValueError
        # Size guard first (cheap), then the proven primality test.
        bits += e * (p.bit_length() - 1)
        if bits > max_bits or not isprime(p):
            raise ValueError
        seen.add(p)
        pairs.append((p, e))
    return pairs


# ---------------------------------------------------------------------------
# The actual check.
# ---------------------------------------------------------------------------

def _check(solution):
    # Step 1: read the JSON object with its single key "cycle".
    sol = _load(solution, ("cycle",), MAX_BYTES)

    # Step 2: "cycle" must be a list with exactly CYCLE_LEN entries.
    cycle = sol["cycle"]
    if not isinstance(cycle, list) or len(cycle) != CYCLE_LEN:
        return False

    # Step 3: validate each entry and compute its aliquot sum s(n).
    ns, ss = [], []  # the numbers, and their aliquot sums
    for entry in cycle:
        if not isinstance(entry, dict) or set(entry) != {"n", "factors"}:
            return False
        n = _parse_int(entry["n"], MAX_DIGITS)
        pairs = _parse_factorisation(entry["factors"], MAX_PRIME_DIGITS, n.bit_length())
        # The claimed factorisation must multiply out to exactly n.
        if math.prod(p ** e for p, e in pairs) != n:
            return False
        # sigma is multiplicative, and for a prime power
        # sigma(p**e) = 1 + p + ... + p**e = (p**(e+1) - 1) / (p - 1).
        sigma = math.prod((p ** (e + 1) - 1) // (p - 1) for p, e in pairs)
        ns.append(n)
        ss.append(sigma - n)  # s(n) = sigma(n) - n

    # Step 4: the numbers must all be different (a length-1 cycle has only one).
    if CYCLE_LEN != 1 and len(set(ns)) != CYCLE_LEN:
        return False

    # Step 5: each number's aliquot sum must be the next number, wrapping
    # around from the last entry to the first.
    return all(ss[i] == ns[(i + 1) % CYCLE_LEN] for i in range(CYCLE_LEN))


def verify(solution: str, rng) -> bool:
    """Platform entry point: return True only for a valid, correct solution.

    `rng` (a numpy.random.Generator) is part of the platform interface but is
    not used: this check is deterministic. Any exception (malformed JSON, a bad
    number, ...) means the submission is rejected, so this function never raises.
    """
    try:
        return _check(solution) is True
    except Exception:
        return False