project_euler.problem_124.sol1

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

Ordered Radicals

Functions

generate_n(factors, n_max, n, res)	Generates all numbers n that can be constructed out of 'factors', with any
generate_primes(→ list[int])	Calculates the list of primes up to and including n.
generate_rads(factors_all, n_max, n, res, factors_prev)	Generates all rads and associated factors, e.g., rad = factor_1 * ... * factor_k.
solution(→ int)	Loops over sorted 'rads' and generates all numbers 'n' for rad.

Module Contents

project_euler.problem_124.sol1.generate_n(factors: list[int], n_max: int, n: int, res: set[int])

Generates all numbers n that can be constructed out of ‘factors’, with any multiplicity, but that do no exceed ‘n_max’.

>>> generate_n([2], 10, 1, set())

project_euler.problem_124.sol1.generate_primes(n: int) → list[int]

Calculates the list of primes up to and including n.

>>> generate_primes(6)
[2, 3, 5]

project_euler.problem_124.sol1.generate_rads(factors_all: list[int], n_max: int, n: int, res: dict, factors_prev: list[int])

Generates all rads and associated factors, e.g., rad = factor_1 * … * factor_k. Output is stored in ‘res’ dict argument.

>>> generate_rads([2], 10, 1, {}, [])

project_euler.problem_124.sol1.solution(n_max: int = 100000, k: int = 10000) → int

Loops over sorted ‘rads’ and generates all numbers ‘n’ for rad. Keeps track of total number of n, and when k falls inside some rad, it sorts all ‘n’ for it and picks up associated n.

>>> solution(10, 6)
9
>>> solution(10, 9)
7