GCD Sum
April 22, 2016
Today’s exercise is inspired by A018804: Find the sum of the greatest common divisors gcd(k, n) for 1 ≤ k ≤ n.
Your task is to write a function that finds the sum of the greatest common divisors. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python, bruteforce solution:
In Python, td_factors is from Programming Praxis primes essay and divisor_gen generates all divisors.
def totient(n): product = n for prime in set(td_factors(n)): product -= product // prime return product def sumgcd(n): return sum(d * totient(n // d) for d in divisor_gen(n))http://oeis.org/A018804 also tells us that sumgcd (or Pillai’s arithmetic function) is multiplicative (f is multiplicative if f(nm) = f(n)f(m) for coprime n and m) and that its value for p^e is p^(e-1)*((p-1)e+p), for prime p – this suffices to calculate the function for any n, given a prime factorization. Here we use the Python primefac library, converting the output to prime-exponent pairs, and use that to define a generic multiplicative function. Fairly snappy, even for “colossally abundant” numbers with lots of divisors (has anyone seen the Ramanujan film yet?):
Here is an alternative in Julia, without invoking a bunch of packages to do all the hard work:
function gcd_(x::Int64, y::Int64)
m = min(x,y)
for d in m:-1:1
if (x%d == 0) && (y%d == 0)
return d
end
end
end
function gcd_sum(n::Int64)
s = n + 1
for k = 2:(n-1)
s += gcd(k,n)
end
return s
end
@Zack: https://en.support.wordpress.com/code/posting-source-code/
@matthew: This CSS add-on doesn’t support formatting for Julia…
Here’s a Java solution that is similar in spirit to Sieve of Eratosthenes.
static long gcdSum(int n) { int[] array = new int[n+1]; // array[0] ignored for (int i = 1; i <= n/2; i++) { if (n % i == 0) { for (int j = i; j <= n; j += i) { array[j] = i; } } } long sum = n; for (int i = 1; i < n; i++) { sum += array[i]; } return sum; }@Zack: you can just leave out the language specification, which will preserve indentation at least, eg “
” at the end:
function gcd_(x::Int64, y::Int64) m = min(x,y) for d in m:-1:1 if (x%d == 0) && (y%d == 0) return d end end end function gcd_sum(n::Int64) s = n + 1 for k = 2:(n-1) s += gcd(k,n) end return s endGah, I was attempting to show the formatting commands
[code]and[/code]– I had a notion they only applied when on a new line, but evidently not. Using HTML entities for the square brackets here.