## 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.

Advertisements

In Python, bruteforce solution:

In Python, td_factors is from Programming Praxis primes essay and divisor_gen generates all divisors.

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.

@Zack: you can just leave out the language specification, which will preserve indentation at least, eg “

” at the end:

Gah, 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.