-
Notifications
You must be signed in to change notification settings - Fork 6
/
795 Alternating GCD Sum.pl
105 lines (76 loc) · 2 KB
/
795 Alternating GCD Sum.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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#!/usr/bin/perl
# Author: Trizen
# Date: 02 May 2022
# https://github.com/trizen
# Alternating GCD Sum
# https://projecteuler.net/problem=795
# Formula:
# g(4) = 6
# g(n) = -n, if n is odd
# g(2^k * n) = (g2(2^k) - 2^k) * Prod_{p^e | n} g2(p^e), where n is odd
# where:
# g2(n) = A078430(n)
# = Sum_{d|n} d * phi(n/d) * f(n/d)
# where:
# f(n) = A000188(n)
# = Prod_{p^e | n} p^floor(e/2)
# Then:
# G(n) = Sum_{k=1..n} g(k)
# See also:
# https://oeis.org/A078430 -- Sum of gcd(k^2,n) for 1 <= k <= n.
# https://oeis.org/A199084 -- Sum_{k=1..n} (-1)^(k+1) gcd(k,n).
# https://oeis.org/A000188 -- Number of solutions to x^2 == 0 (mod n).
# Runtime: ~22 seconds.
use 5.020;
use strict;
use warnings;
use ntheory qw(:all);
use experimental qw(signatures);
sub f ($n) { # OEIS: A000188
vecprod(map { ($_->[1] == 1) ? 1 : powint($_->[0], $_->[1] >> 1) } factor_exp($n));
}
my %cache;
sub g2 ($n) { # OEIS: A078430
if (is_prime($n)) {
return ($n + ($n - 1));
}
if (exists $cache{$n}) {
return $cache{$n};
}
my $sum = 0;
foreach my $d (divisors($n)) {
my $nod = divint($n, $d);
$sum = addint($sum, vecprod($d, euler_phi($nod), f($nod)));
}
$cache{$n} = $sum;
}
sub g ($n) {
return 6 if $n == 4;
if ($n % 2 == 1) { # n is odd
return -$n;
}
if (is_prime($n >> 1)) {
return $n - 1;
}
my $v = valuation($n, 2);
my $t = $n >> $v;
my $w = g2(1 << $v) - (1 << $v);
return $w if ($t == 1);
return mulint($w, vecprod(map { g2(powint($_->[0], $_->[1])) } factor_exp($t)));
}
sub G ($n) {
my $sum = 0;
foreach my $k (1 .. $n) {
$sum += g($k);
}
return $sum;
}
use Test::More tests => 7;
is(g(2 * 47), 93);
is(g(97), -97);
is(g(3 * 31), -93);
is(G(100), 7111);
is(G(200), 36268);
is(G(300), 89075);
is(G(1234), 2194708);
say G(12345678);