Witness me!

witness_me.py

#!/usr/bin/env python3
# Title: Witness me!
# Description: Calculates and counts all the liars below a given n value
# Author: Ryan Barnes
# Date: 2021-12-06
# License: MIT

from collections import Counter
from functools import partial
from itertools import chain


def witness_test(n, a):
    """Perform a witness test on a number"""

    if n > 2 and n % 2 == 0:
        # If the value is greater than 2 and even, we know it isn't prime
        return False
    else:
        # Calculate the d value
        d = n - 1
        while d % 2 == 0:
            d /= 2

        # Calculate the a^d mod n value
        result = pow(a, int(d), n)

        # Return whether the result +-1 mod n
        return result == 1 or result == n - 1


def most_common_liars_below(big_n, top=10):
    """Calculate all the liars below big_n"""
    liars = {}
    truthers = {}

    lower_n = 11
    upper_n = 2_152_302_898_747
    star_witnesses = (2, 3, 5, 7, 11)

    most_liars = (0, 0)

    for n in range(1, big_n):
        possible_liars = set()

        if upper_n > n > lower_n:
            # Do a quick test to skip prime numbers
            is_prime = all(map(partial(witness_test, n), star_witnesses))

            if is_prime:
                # Skip prime numbers, we only care about liars
                continue
        else:
            # Otherwise, assume it's prime and can will figure it out later
            is_prime = True

        for a in range(1, int(n / 2) + 1):
            # for every a below n, complete a witness test
            result = witness_test(n, a)

            if not result:
                # If the witness test fails, the number isn't prime
                is_prime = False
            else:
                # If it does fail and the number is prime, we have a liar!
                possible_liars.add(a)

        if possible_liars:
            possible_liars |= {n - x for x in possible_liars}

        if not is_prime and possible_liars:
            # If the number isn't prime then we can add it to the list
            liars[n] = possible_liars.copy()
            truthers[n] = {x for x in range(1, n) if x not in possible_liars}

            # Calculate the percentage of liars
            liar_percentage = len(liars[n]) / n

            # Track the largest percentage
            if most_liars[1] < liar_percentage:
                most_liars = (n, liar_percentage)

    # Pull together all the liars
    liar_count = Counter(chain(*liars.values()))

    # Print out the common liars in a nice format
    common_liars = liar_count.most_common(top)
    print(f"Top {top} liars under n of {big_n}:")
    for a, count in common_liars:
        print(f"{a: >10}: {count}")

    print(f"{most_liars[0]} has {most_liars[1]:.02%} liars!")


if __name__ == "__main__":
    most_common_liars_below(10_000)
    # Top 10 liars under n of 10000:
    #          1: 4380
    #        256: 615
    #         16: 591
    #         64: 530
    #         81: 520
    #          4: 519
    #        324: 494
    #        625: 489
    #       1024: 465
    #       1296: 451
    # 9973 has 49.99% liars!

    # I'm sure there are more ways to speed this up by caching some results
    # but there you have it, 256 is the liar liar, pants on fire