Fast sieve for sum of Euler totient values (phi) values from 1 to 'n'

Question

I wanted to optimize the sieve method for computing Euler's Totient (Phi) values from 1 to n. Basically, i came across this Quora comment :https://www.quora.com/What-is-the-fastest-function-to-calculate-phi-I-for-1-I-n (2nd solution that avoids division), but I am unable to wrap my head around the algorithm mentioned by the person. Any help appreciated.

Answer 1

Let's do it for $n=10.$ Start with $m=2$ and compute $\phi(m^k)$ for as high as you need. We get $\phi(2)=(2-1)=1,$ $\phi(4)= 2(2-1) = 2$ and similarly, $\phi(8) = 4.$ Then we need to multiply the entry of every multiple of $8$ by $\phi(8)=4.$ That's just $8.$ Then, we multiply the entry of every multiple of $4$ that is not a multiple of $8$ by $\phi(4)=2.$ Then we multiply every multiple of $2$ that is not a multiple of $4$ by $\phi(2)=1.$ So we have $$ \begin{pmatrix}2 & 3 & 4 & 5 &6 &7 &8 &9 & 10\\ 1&1&2&1&1&1&4&1&1\end{pmatrix}.$$ (where we invisibly multiplied entries $2,$ $6,$ and $10$ by $1$.) Now we go to the next entry that is still a one... that's $m=3.$ We have $\phi(3)=2$ and $\phi(9)=6.$ So we multiply the $9$ entry by $6$ (since it's the only multiple of $9$ on the list). And we multiply $3$ and $6$ (the multiples of $3$ that aren't multiples of $9$) by $2,$ giving $$ \begin{pmatrix}2 & 3 & 4 & 5 &6 &7 &8 &9 & 10\\ 1&2&2&1&2&1&4&6&1\end{pmatrix}.$$ Now on to $m=5.$ We have $\phi(5)=4,$ and we multiply the $5$ and $10$ by $4,$ giving $$ \begin{pmatrix}2 & 3 & 4 & 5 &6 &7 &8 &9 & 10\\ 1&2&2&4&2&1&4&6&4\end{pmatrix}.$$ Finally for $m=7,$ we have $\phi(7)=6$ and so we get
$$ \begin{pmatrix}2 & 3 & 4 & 5 &6 &7 &8 &9 & 10\\ 1&2&2&4&2&6&4&6&4\end{pmatrix}.$$

This is my interpretation of what they're saying but I actually don't really like it cause the whole 'skipping the multiples of the higher power' thing seems like a headache to code up. Instead, I'd simply multiply all multiples of $2$ on the list by $1,$ then all the multiples of $4$ by $2,$ then all the multiples of $8$ by $2,$ then all the multiples of $16$ by $2,$ etc. Then I'd multiply all the multiples of $3$ by $2,$ then all the multiples of $9$ by $3,$ then all the multiples of $27$ by $3,$ etc. I think that's much more straightforward and also only uses multiplication.

(EDIT Actually, perhaps I've missed the point of the way they do it: their way does do fewer multiplications since they pre-multiply, say $\phi(27)$ together once, where as I do it once for every multiple of $27$ on the list.)

Here is a (hastily done) implementation of my way in python

def totients(n):
    result = [1] * (n+1)
    for m in range(2,n+1):
        # if not a prime, skip
        if result[m] != 1:
            continue

        # multiply all multiples of m by m-1
        thing = m-1
        i = m
        while i <= n:
            result[i] *= thing
            i += m

        # multiply all multiples of higher powers by m
        v=m
        thing = m
        while True:
            v *= m
            if v > n:
                break
            i = v
            while i <= n:
                result[i] *= thing
                i += v
    return result


print(totients(40))

>python totients.py 
[1, 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16]