Totient function

The Euler totient function is built-in as Number.euler_phi(), but we can easily re-implement it using its multiplicative property: phi(p^k) = (p-1)*p^(k-1).

func 𝜑(n) {
    n.factor_exp.prod {|p|
        (p[0]-1) * p[0]**(p[1]-1)
    }
}

for n in (1..25) {
    var totient = 𝜑(n)
    printf("𝜑(%2s) = %3s%s\n", n, totient, totient==(n-1) ? ' - prime' : '')
}

[100, 1_000, 10_000, 100_000].each {|limit|
    var pi = (1..limit -> count_by {|n| 𝜑(n) == (n-1) })
    say "Number of primes <= #{limit}: #{pi}"
}

Output:

Number of primes <= 100: 25
Number of primes <= 1000: 168
Number of primes <= 10000: 1229
Number of primes <= 100000: 9592