project euler problem 135 https projecteuler netproblem135 given the positive integers x y and z are consecutive terms of an arithmetic progression the least value of the positive integer n for which the equation x2 y2 z2 n has exactly two solutions is n 27 342 272 202 122 92 62 27 it turns out that n 1155 is the least value which has exactly ten solutions how many values of n less than one million have exactly ten distinct solutions taking x y z of the form a d a a d respectively the given equation reduces to a 4d a n calculating no of solutions for every n till 1 million by fixing a and n must be a multiple of a total no of steps n 11 12 13 14 1n so roughly onlogn time complexity returns the values of n less than or equal to the limit have exactly ten distinct solutions solution100 0 solution10000 45 solution50050 292 returns the values of n less than or equal to the limit have exactly ten distinct solutions solution 100 0 solution 10000 45 solution 50050 292 d must be divisible by 4 since x y z are positive integers so z 0 a d and 4d a
def solution(limit: int = 1000000) -> int:
    
    limit = limit + 1
    frequency = [0] * limit
    for first_term in range(1, limit):
        for n in range(first_term, limit, first_term):
            common_difference = first_term + n / first_term
            if common_difference % 4:  
                continue
            else:
                common_difference /= 4
                if (
                    first_term > common_difference
                    and first_term < 4 * common_difference
                ):  
                    frequency[n] += 1  

    count = sum(1 for x in frequency[1:limit] if x == 10)

    return count


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