2
$\begingroup$

This question arises from Project Euler 153. That problem asks for the sum of all complex divisors of all natural numbers up to a maximum, where a complex divisor is a complex number of the form a + b*i where a is a positive integer and b is an integer. I have solved the problem for divisors where b is zero (real divisors) so I only need to solve it for true complex divisors now.

I have simplified the problem as follows:

All true complex numbers with a positive real part can be written as $k(a \pm bi)$ with a, b, and k positive integers and a and b coprime. Then there are two cases:

$a \neq b$:

$k(a - bi) \vert x$

Multiply through by the conjugate

$k(a^2 + b^2) \vert x(a + bi)$

Since a and b are coprime, $a + bi$ can be dropped.

$k(a^2 + b^2) \vert x$

Let $c = a^2 + b^2$

The sum of divisors of numbers less than n that are multiples of the complex number is $$\sum \left\lfloor{n \over kc}\right\rfloor 2k(a + b)$$ because for every k there are $\left\lfloor{n \over kc} \right\rfloor$ multiples of $a + bi$, $a - bi$, $b - ai$, and $b + ai$. This last part allows us to only consider coprime pairs where a < b (so I can use Fairy sequences in my program).

$a = b$:

This case is exactly the same except since $a = b = 1$, $b \pm ai$ is the same as $a \pm bi$ so there is no need to count it twice and the sum is just $$\sum \left\lfloor{n \over 2k}\right\rfloor 2k$$

The overall sum is therefore $$ \left( \sum \left\lfloor{n \over 2k}\right\rfloor 2k \right) + \left( \sum_{a \perp b \wedge a < b} \sum_k \left\lfloor{n \over kc}\right\rfloor 2k(a + b)\right) $$

However, this does not work. I've tested my program for n = 10 where the correct result should be 74 (161, found on this site, minus 87, the sum of the real divisors), but I get 88. Is my analysis incorrect or is there an error in my program? I'm not sure about dropping $a + bi$: I know it would work for real numbers if their gcd is a unit like a b and i, but maybe not for complex numbers.

$\endgroup$
1
  • $\begingroup$ It turns out this analysis is correct I just forgot to actually use the function based on it. Interestingly, the sum of multiples of the complex number dividing numbers less than n is equal to the sum of the real divisors of n divided by the magnitude of the complex number. $\endgroup$
    – hacatu
    Commented Oct 31, 2015 at 5:07

0

You must log in to answer this question.