project_euler.problem_135.sol1
==============================

.. py:module:: project_euler.problem_135.sol1

.. autoapi-nested-parse::

   Project Euler Problem 135: https://projecteuler.net/problem=135

   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 * (1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n), so roughly
   O(nlogn) time complexity.



Functions
---------

.. autoapisummary::

   project_euler.problem_135.sol1.solution


Module Contents
---------------

.. py:function:: solution(limit: int = 1000000) -> int

   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