1234567891011121314151617181920212223242526272829303132333435363738 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 15 May 2021
- # https://github.com/trizen
- # Generate the smallest number that has at least n divisors.
- # See also:
- # https://oeis.org/A061799 -- Smallest number with at least n divisors.
- use 5.020;
- use warnings;
- use experimental qw(signatures);
- use ntheory qw(nth_prime);
- use Math::AnyNum qw(:overload);
- sub smallest_number_with_at_least_n_divisors ($threshold, $least_solution = Inf, $k = 1, $max_a = Inf, $sigma0 = 1, $n = 1) {
- if ($sigma0 >= $threshold) {
- return $n;
- }
- my $p = nth_prime($k);
- for (my $a = 1 ; $a <= $max_a ; ++$a) {
- $n *= $p;
- last if ($n > $least_solution);
- $least_solution = __SUB__->($threshold, $least_solution, $k + 1, $a, $sigma0 * ($a + 1), $n);
- }
- return $least_solution;
- }
- say smallest_number_with_at_least_n_divisors(60); #=> 5040
- say smallest_number_with_at_least_n_divisors(1000); #=> 245044800
|