August 26, 2024
P37 - Calculate Euler's totient function phi(m) (improved).
See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36, then the function phi(m) can be efficiently calculated as follows:
Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula: phi(m) = (p1-1)*p1^(m1-1) * (p2-1)*p2^(m2-1) * (p3-1)*p3^(m3-1) * ...
kotlin
package org.kotlin99.arithmetic
import com.natpryce.hamkrest.assertion.assertThat
import com.natpryce.hamkrest.equalTo
import org.junit.Test
import org.kotlin99.common.tail
import kotlin.math.pow
fun Int.totient2(): Int {
fun totient(primeFactors: List<Pair<Int, Int>>): Double =
if (primeFactors.isEmpty()) 1.0
else {
val (p, m) = primeFactors.first()
(p - 1) * p.toDouble().pow(m.toDouble() - 1) * totient(primeFactors.tail())
}
return totient(this.primeFactorMultiplicity()).toInt()
}
class P37Test {
@Test fun `calculate Euler's totient function (improved)`() {
assertThat(10.totient2(), equalTo(4))
assertThat(10090.totient2(), equalTo(4032))
}
}
Be first to comment