/
carmichael_rad(p-1)==rad(n-1)_cached.pl
77 lines (54 loc) · 1.65 KB
/
carmichael_rad(p-1)==rad(n-1)_cached.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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#!/usr/bin/perl
# Squarefree composite numbers m such that rad(p-1) = rad(m-1) for every prime p dividing m.
# https://oeis.org/A306479
# First few terms:
# 1729, 46657, 1525781251
# Additional terms (with possible gaps):
# 763546828801, 6031047559681, 184597450297471, 732785991945841, 18641350656000001, 55212580317094201
use 5.020;
use strict;
use warnings;
use experimental qw(signatures);
use Storable;
use POSIX qw(ULONG_MAX);
use Math::GMPz;
use Math::GMPq;
use Math::MPFR;
use ntheory qw(:all);
use Math::Prime::Util::GMP;
use experimental qw(signatures);
use List::Util qw(uniq);
my $carmichael_file = "cache/factors-carmichael.storable";
my $carmichael = retrieve($carmichael_file);
sub is_smooth_over_prod ($n, $k) {
state $g = Math::GMPz::Rmpz_init_nobless();
state $t = Math::GMPz::Rmpz_init_nobless();
Math::GMPz::Rmpz_set($t, $n);
Math::GMPz::Rmpz_gcd($g, $t, $k);
while (Math::GMPz::Rmpz_cmp_ui($g, 1) > 0) {
Math::GMPz::Rmpz_remove($t, $t, $g);
return 1 if Math::GMPz::Rmpz_cmp_ui($t, 1) == 0;
Math::GMPz::Rmpz_gcd($g, $t, $g);
}
return 0;
}
my $pm1 = Math::GMPz::Rmpz_init();
my $nm1 = Math::GMPz::Rmpz_init();
my @results;
while (my ($key, $value) = each %$carmichael) {
my @factors = split(' ', $value);
Math::GMPz::Rmpz_set_str($nm1, $key, 10);
Math::GMPz::Rmpz_sub_ui($nm1, $nm1, 1);
if (
vecall {
Math::GMPz::Rmpz_set_str($pm1, $_, 10);
Math::GMPz::Rmpz_sub_ui($pm1, $pm1, 1);
is_smooth_over_prod($nm1, $pm1);
}
@factors
) {
say $key;
}
}
__END__
# No Carmichael terms > 2^64 are known.