-
Notifications
You must be signed in to change notification settings - Fork 6
/
549 Divisibility of factorials.pl
77 lines (54 loc) · 1.13 KB
/
549 Divisibility of factorials.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
# Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 17 September 2016
# Website: https://github.com/trizen
# https://projecteuler.net/problem=549
# Runtime: 6 min 33.61s
use utf8;
use 5.010;
use strict;
use integer;
use ntheory qw(
vecmax
vecsum
is_prime
factorial
sum_primes
factor_exp
forcomposites
);
my $limit = 10**8;
my %cache;
sub smarandache {
my ($n) = @_;
return $n if is_prime($n);
my @f = factor_exp($n);
my $Ω = vecsum(map { $_->[1] } @f);
(@f == $Ω)
&& return $f[-1][0];
if (@f == 1) {
my $ϕ = $f[0][0];
($Ω <= $ϕ)
&& return $ϕ * $Ω;
exists($cache{$n})
&& return $cache{$n};
my $m = $ϕ * $Ω;
my $f = factorial($m - $ϕ);
while ($f % $n == 0) {
$m -= $ϕ;
$f /= $m;
}
return ($cache{$n} = $m);
}
vecmax(map {
$_->[1] == 1 ? $_->[0]
: smarandache($_->[0]**$_->[1])
} @f);
}
my $sum = 0;
forcomposites {
$sum += smarandache($_);
} $limit;
$sum += sum_primes($limit);
say $sum;