Return the sum of N(n) for 1 <= n <= n_limit. >>> solution(1000,5) 222 >>> solution(1000,10) 249 >>> solution(10000,10) 2383
(t_limit: int = 1000000, n_limit: int = 10)
| 22 | |
| 23 | |
| 24 | def solution(t_limit: int = 1000000, n_limit: int = 10) -> int: |
| 25 | """ |
| 26 | Return the sum of N(n) for 1 <= n <= n_limit. |
| 27 | |
| 28 | >>> solution(1000,5) |
| 29 | 222 |
| 30 | >>> solution(1000,10) |
| 31 | 249 |
| 32 | >>> solution(10000,10) |
| 33 | 2383 |
| 34 | """ |
| 35 | count: defaultdict = defaultdict(int) |
| 36 | |
| 37 | for outer_width in range(3, (t_limit // 4) + 2): |
| 38 | if outer_width * outer_width > t_limit: |
| 39 | hole_width_lower_bound = max( |
| 40 | ceil(sqrt(outer_width * outer_width - t_limit)), 1 |
| 41 | ) |
| 42 | else: |
| 43 | hole_width_lower_bound = 1 |
| 44 | |
| 45 | hole_width_lower_bound += (outer_width - hole_width_lower_bound) % 2 |
| 46 | |
| 47 | for hole_width in range(hole_width_lower_bound, outer_width - 1, 2): |
| 48 | count[outer_width * outer_width - hole_width * hole_width] += 1 |
| 49 | |
| 50 | return sum(1 for n in count.values() if 1 <= n <= n_limit) |
| 51 | |
| 52 | |
| 53 | if __name__ == "__main__": |