# Calculate Euler's totient function in the domain ^x*$ with the ECMAScript subset of regex functionality
# N = input number; no need to anchor, because we return a value for all inputs
x$|                              # return 1 for an input of 1, because the algorithm below would return 0
(?=
    (?=                          # Calculate the largest prime factor of N
        (                        # Repeatedly divide tail by its smallest prime factor
            (?=(xx+)(\2+$))
            \3
        )*
        (x*)                     # \4 = largest prime factor of N
    )
    (
        (xx+?)                   # \6 = smallest prime factor of N which must be < \4;
                                 # seed the loop: tail -= \6 < \4 ? \6 : 0
        (?=
            \6*(?=\6$)
            (?!\4)               # Assert that \6 < \4
        )
    )?
    # For each prime factor P of N, starting with the smallest, multiply by (P-1)/P
    (
        (?=
            (x*?)\4*(?=\4$)      # \8 = tail % \4 == \4 - {current smallest prime factor of N that hasn't been handled yet}; tail = \4
            \8x(x*)              # P = current smallest prime factor of N that hasn't been handled yet; \9 = P-1
        )
        (?=
            (x(x*))              # \10 = tail / P; \11 = \10-1
            (?=\10*$)            # we can skip the test for divisibility by \9, because P is prime
            (\9\11*$)            # \12 = tool to make tail = \10
        )
        (
            \10(x*$\8)           # if \8 == 0, then let \14 = tail-\10 == phi(N), and exit the loop
        |
            .*(?=\12\9$)         # tail = (tail+P) - ((tail+P) / P)
            (
                (\9xx+?)         # \16 = next smallest prime factor of N, such that P < \16 < \4;
                                 # set up the next iteration: tail -= \16 < \4 ? \16 : 0
                (?=
                    \16*(?=\16$)
                    (?!
                        \4           # Assert that \16 < \4
                    |
                        (xx+)\17+$   # Assert that \16 is prime
                    )
                )
            )?
        )
    )*
)
\14