/
inverse_phi.pl
52 lines (40 loc) · 883 Bytes
/
inverse_phi.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#!/usr/bin/perl
# Least k such that phi(k) is an n-th power when k is the product of n distinct primes.
# https://oeis.org/A281069
use utf8;
use 5.020;
use strict;
use warnings;
use Math::GMPz;
use ntheory qw(:all);
use experimental qw(signatures);
sub a ($n) {
my @list;
foreach my $k (2 .. 1e9) {
is_smooth($k, 3) || next;
foreach my $v (inverse_totient(powint($k, $n))) {
if (is_almost_prime($n, $v) and is_square_free($v)) {
push @list, $v;
}
}
last if @list;
}
vecmin(@list);
}
foreach my $n (1 .. 20) {
say "a($n) <= ", a($n);
}
__END__
a(1) <= 3
a(2) <= 10
a(3) <= 30
a(4) <= 3458
a(5) <= 29526
a(6) <= 5437705
a(7) <= 91604415
a(8) <= 1190857395
a(9) <= 26535163830
a(10) <= 344957129790
a(11) <= 5703406198237930
a(12) <= 178435136773443810
a(13) <= 4961806417984478790