-
Notifications
You must be signed in to change notification settings - Fork 0
/
search.pl
45 lines (33 loc) · 900 Bytes
/
search.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
#!/usr/bin/perl
# Numbers which when chopped into one, two or more parts, added and squared result in the same number
# https://oeis.org/A104113
# Generate terms of the sequence.
# See also:
# https://projecteuler.net/problem=719
use 5.020;
use warnings;
use ntheory qw(:all);
use experimental qw(signatures);
sub isok ($i, $j, $d, $e, $n, $sum = 0) {
if ($sum + join('', @{$d}[$i .. $e]) < $n) {
return 0;
}
my $new_sum = $sum + join('', @{$d}[$i .. $j]);
if ($new_sum > $n) {
return 0;
}
if ($new_sum == $n and $j >= $e) {
return 1;
}
if ($j + 1 <= $e) {
isok($j + 1, $j + 1, $d, $e, $n, $new_sum) && return 1;
isok($i, $j + 1, $d, $e, $n, $sum) && return 1;
}
return 0;
}
foreach my $n (2 .. 1e7) {
my @d = todigits($n * $n);
if (isok(0, 0, \@d, $#d, $n)) {
say $n * $n;
}
}