Factorization, Mobius and Euler Totient Function

759a⟨test factor 759a⟩≡   (753)  759b ⊳
testFactor1(): () == {
        import from I, SmallIntegerTools;
        t: T := 1;
        assertEquals(T, t, factor 1);
        assertEquals(I, 1, moebiusMu t);
        assertEquals(I, 1, eulerPhi t);
}

Uses I 47 and SmallIntegerTools 555.

759b⟨test factor 759a⟩+≡   (753)  ⊲759a  760a ⊳
testFactor2(): () == {
        import from I, SmallIntegerTools;
        t: T := power(2147483647, 1);
        assertEquals(T, t, factor 2147483647); -- 2^31-1
        assertEquals(I, -1, moebiusMu t);
        assertEquals(I, 2147483646, eulerPhi t);
}

Uses I 47 and SmallIntegerTools 555.

760a⟨test factor 759a⟩+≡   (753)  ⊲759b  760b ⊳
testFactor3(): () == {
        import from I, SmallIntegerTools;
        t: T := power(7, 1) * power(11, 1) * power(13, 1);
        assertEquals(T, t, factor 1001);
        assertEquals(I, -1, moebiusMu t);
        assertEquals(I, 6*10*12, eulerPhi t);
}

Uses I 47 and SmallIntegerTools 555.

760b⟨test factor 759a⟩+≡   (753)  ⊲760a  760c ⊳
testFactor4(): () == {
        import from I, SmallIntegerTools;
        t: T := power(127, 1) * power(9721, 1);
        assertEquals(T, t, factor 1234567);
        assertEquals(I, 1, moebiusMu t);
        assertEquals(I, 126*9720, eulerPhi t);
}

Uses I 47 and SmallIntegerTools 555.

760c⟨test factor 759a⟩+≡   (753)  ⊲760b  761a ⊳
testFactor5(): () == {
        import from I, SmallIntegerTools;
        t: T := power(2,1) * power(3,2) * power(47,1) * power(14593,1);
        assertEquals(T, t, factor 12345678);
        assertEquals(I, 0, moebiusMu t);
        assertEquals(I, 1*3*(3-1)*46*14592, eulerPhi t);
}

Uses I 47 and SmallIntegerTools 555.

761a⟨test factor 759a⟩+≡   (753)  ⊲760c
testFactor6(): () == {
        import from I, SmallIntegerTools;
        t: T := power(3,4) * power(11,2) * power(59,3);
        assertEquals(T, t, factor(3^4*11^2*59^3));
        assertEquals(I, 0, moebiusMu t);
        assertEquals(I, 3^3*(3-1)*11*(11-1)*59^2*(59-1), eulerPhi t);
}

Uses I 47 and SmallIntegerTools 555.

761b⟨test Euler totient 761b⟩≡   (753)
local multiply(k: T): I == { -- the inverse of factor: I -> T
        r: I := 1;
        for ep in k repeat {(e, p) := ep; r := r * p^e}
        r;
}
testEulerTotient(): () == BugWorkaround(
    T has with {divisors: % -> Generator %; /:(%, %) -> %}
){
        import from I, SmallIntegerTools;
        for m in 1..100 repeat {
                t: T := factor m;
                phim: I := 0;
                for d in divisors t | not zero?(mu:=moebiusMu d) repeat {
                        phim := phim + mu * multiply(t/d);
                }
                assertEquals(I, eulerPhi t, phim);
        }
}

Uses BugWorkaround 48, Generator 617, I 47, and SmallIntegerTools 555.

34.3 Factorization, Möbius and Euler Totient Function