gcd_primes_count_euler_phi_like.sf

#!/usr/bin/ruby

for n in (2..50) {
    var sum = 0
    var arr = []
    for m in (1 .. n) {
        var k = n
        k /= gcd(k, m)
        if (k.is_prime) {
            arr << k
            sum += 1;
        }
    }

    var prev = 0
    var table = []
    for k in (arr) {
        if (prev != k) {
            table << [k, 0]
        }
        table[-1][-1] += 1
        prev = k
    }

    say "L(#{n}) = #{table.map{_[1]}.sum}"
}

__END__
L(2) = 1
L(3) = 2
L(4) = 1
L(5) = 4
L(6) = 3
L(7) = 6
L(8) = 1
L(9) = 2
L(10) = 5
L(11) = 10
L(12) = 3
L(13) = 12
L(14) = 7
L(15) = 6
L(16) = 1
L(17) = 16
L(18) = 3
L(19) = 18
L(20) = 5
L(21) = 8
L(22) = 11
L(23) = 22
L(24) = 3
L(25) = 4
L(26) = 13
L(27) = 2
L(28) = 7
L(29) = 28
L(30) = 7
L(31) = 30
L(32) = 1
L(33) = 12
L(34) = 17
L(35) = 10
L(36) = 3
L(37) = 36
L(38) = 19
L(39) = 14
L(40) = 5
L(41) = 40
L(42) = 9
L(43) = 42
L(44) = 11
L(45) = 6
L(46) = 23
L(47) = 46
L(48) = 3
L(49) = 6
L(50) = 5