-
Notifications
You must be signed in to change notification settings - Fork 0
/
prog.pl
85 lines (61 loc) · 1.59 KB
/
prog.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
78
79
80
81
82
83
84
85
#!/usr/bin/perl
# Even numbers k such that k^2 - 1 is a powerful number.
# https://oeis.org/A365983
# k^2 - 1 = (k-1)*(k+1), therefore both k-1 and k+1 must be odd powerful numbers.
# Known terms:
# 26, 70226, 130576328, 189750626, 512706121226, 13837575261124, 99612037019890, 1385331749802026
use 5.036;
use ntheory qw(:all);
sub divceil ($x, $y) { # ceil(x/y)
(($x % $y == 0) ? 0 : 1) + divint($x, $y);
}
sub odd_powerful_numbers ($A, $B, $k = 2) {
my @odd_powerful;
sub ($m, $r) {
if ($r < $k) {
push @odd_powerful, $m;
return;
}
my $from = 1;
my $upto = rootint(divint($B, $m), $r);
if ($r <= $k and $A > $m) {
$from = rootint(divceil($A, $m), $r);
}
foreach my $v ($from .. $upto) {
next if ($v % 2 == 0);
if ($r > $k) {
gcd($m, $v) == 1 or next;
is_square_free($v) or next;
}
my $t = mulint($m, powint($v, $r));
if ($r <= $k and $t < $A) {
next;
}
__SUB__->($t, $r - 1);
}
}->(1, 2 * $k - 1);
[sort { $a <=> $b } @odd_powerful];
}
my $lo = 2;
my $hi = 10*$lo;
while (1) {
my $arr = odd_powerful_numbers($lo - 2, $hi + 2, 2);
my ($x, $y) = ($arr->[0], $arr->[1]);
foreach my $v (@$arr) {
if (($v-2 == $x) or ($v-2 == $y)) {
say $v-1;
}
($x, $y) = ($y, $v);
}
$lo = $hi+1;
$hi = 2*$lo;
}
__END__
26
70226
130576328
189750626
512706121226
13837575261124
99612037019890
1385331749802026