project euler problem 207 https projecteuler netproblem207 problem statement for some positive integers k there exists an integer partition of the form 4t 2t k where 4t 2t and k are all positive integers and t is a real number the first two such partitions are 41 21 2 and 41 5849625 21 5849625 6 partitions where t is also an integer are called perfect for any m 1 let pm be the proportion of such partitions that are perfect with k m thus p6 12 in the following table are listed some values of pm p5 11 p10 12 p15 23 p20 12 p25 12 p30 25 p180 14 p185 313 find the smallest m for which pm 112345 solution equation 4t 2t k solved for t gives t log2sqrt4k12 12 for t to be real valued sqrt4k1 must be an integer which is implemented in function checktrealk for a perfect partition t must be an integer to speed up significantly the search for partitions instead of incrementing k by one per iteration the next valid k is found by k i2 1 4 with an integer i and k has to be a positive integer if this is the case a partition is found the partition is perfect if t os an integer the integer i is increased with increment 1 until the proportion perfect partitions total partitions drops under the given value check if t fpositiveinteger log2sqrt4positiveinteger12 12 is a real number checkpartitionperfect2 true checkpartitionperfect6 false find m for which the proportion of perfect partitions to total partitions is lower than maxproportion solution1 5 true solution12 10 true solution3 13 185 true if candidate is an integer then there is a partition for k check if t f positive_integer log2 sqrt 4 positive_integer 1 2 1 2 is a real number check_partition_perfect 2 true check_partition_perfect 6 false find m for which the proportion of perfect partitions to total partitions is lower than max_proportion solution 1 5 true solution 1 2 10 true solution 3 13 185 true if candidate is an integer then there is a partition for k
import math


def check_partition_perfect(positive_integer: int) -> bool:
    

    exponent = math.log2(math.sqrt(4 * positive_integer + 1) / 2 + 1 / 2)

    return exponent == int(exponent)


def solution(max_proportion: float = 1 / 12345) -> int:
    

    total_partitions = 0
    perfect_partitions = 0

    integer = 3
    while True:
        partition_candidate = (integer**2 - 1) / 4
        
        if partition_candidate == int(partition_candidate):
            partition_candidate = int(partition_candidate)
            total_partitions += 1
            if check_partition_perfect(partition_candidate):
                perfect_partitions += 1
        if perfect_partitions > 0:
            if perfect_partitions / total_partitions < max_proportion:
                return int(partition_candidate)
        integer += 1


if __name__ == "__main__":
    print(f"{solution() = }")