Golf the repeated totient function

Question

You will take two positive integers n and x as input, and output Euler's totient function (number of positive integers less than x co-prime to x) applied n times.

Testcases

n x   result
1 10  4
2 10  2
3 10  1
1 100 40
2 100 16
3 100 8
4 100 4
5 100 2
6 100 1

Answer 1

05AB1E, 2 bytes

Code:

FÕ

Explanation:

F   # Do the following n times:
 Õ  #   ..Calculate the totient

Uses the CP-1252 encoding. Try it online!.

Answer 2

Python 2, 84 78 70 bytes

n,x=input();exec('k=m=1;'+'x-=(x%k<m%k)*x/k;m*=k*k;k+=1;'*x)*n;print x

Thanks to @xnor for golfing off 8 bytes!

Test it on Ideone.

Background

By Euler's product formula,

where φ denotes Euler's totient function and p varies only over prime numbers.

To identify primes, we use a corollary of Wilson's theorem:

How it works

After reading the input, we construct and execute a certain string. The executed code is roughly equivalent to the following.

r = range(x)
for _ in range(n):
    k = 1
    m = 1
    for _ in r:
        x -= (x % k < m % k) * x / k
        m *= k**2
        k += 1

The inner loop will set x = φ(x), so executing it n times stores the desired output in x.

At all times, the variable m will be equal to the square of the factorial of k - 1. In fact, we set k = 1 and m = 0!² = 1 at the beginning of the inner loop.

k varies from its initial value 1 to the initial value of x and is incremented each time the sinner loop is executed. m is updated accordingly by multiplying it by the "old" value of k².

For the actual calculation of x, recall that m%k will yield 1 if m is prime and 0 if not. This means that x%k<m%k will yield True if and only if both k is a prime number and x is divisible by k.

In this case, (x%k<m%k)*x/k yields x / k, and subtracting it from x replaces its previous value with x(1 - 1/k), as in Euler's product formula. Otherwise, (x%k<m%k)*x/k yields 0 and x remains unchanged.

Answer 3

Actually, 4 bytes

`▒`n

Try it online!

This program takes x as the first input, and n as the second input.

Explanation:

`▒`n
`▒`n  call the following function n times:
 ▒      totient(x)

Answer 4

Mathematica, 17 bytes

EulerPhi~Nest~##&

An unnamed function which takes x as the first argument and n as the second. Here EulerPhi~Nest~## is short for Nest[EulerPhi, ##] and then ## expands to a sequence of both arguments so we get Nest[EulerPhi, x, n]. And EulerPhi is of course the totient function.

Answer 5

Jelly, 3 bytes

ÆṪ¡

Expects x as the first argument and n as the second.

Try it online!

This is as straightforward as it gets: ÆṪ is the built-in totient function and ¡ applies this function as many times as the second argument.

Answer 6

MATL, 5 bytes

:"_Zp

Try it online!

:        % Take n implicitly. Generate vector [1 2 ... n]
"        % For each loop, that is, repeat n times
  _Zp    %   Euler's totient function. Takes x implicitly first time
         % End for. Display implicitly

---

Without using Euler's totient function: 9 bytes

:"t:Zd1=s

Try it online!

:        % Take n implicitly. Generate range [1 2 ... n]
"        % For each loop, that is, repeat n times
  t      %   Duplicate. Takes x implicitly first time. Call that t
  :      %   Range [1 2 ... t]
  Zd     %   GCD of t and [1 2 ... t], elementwise
  1=s    %   How many times the result equals 1: Euler's totient
         % End for. Display implicitly

Answer 7

J, 6 4 bytes

5&p:

Straight-forward approach. Nests the totient function n times on an initial value of x.

Usage

   f =: 5&p:
   5 f 100
2

Explanation

Normally, 5&p: is a monad that computes the totient of its argument. However, when used dyadically, it nests itself on an initial value of its LHS according to the number of times on its RHS.

Answer 8

PARI/GP, 33 bytes

Straightforward iteration:

f(n,x)=for(i=1,x,n=eulerphi(n));n

Straightforward recursion:

f(n,x)=if(x,n,f(eulerphi(n),x-1))

Answer 9

Haskell, 49 46 44 40 bytes

Thanks @xnor for another again named solution:

x%0=x
x%n=sum[1|1<-gcd x<$>[1..x]]%(n-1)

Old version:

The following is an unnamed pointless function that takes two arguments: (Thanks @Lynn for another two bytes!)

(!!).iterate(\y->sum[1|t<-[1..y],gcd y t<2])

To use it, you can e.g. assign it a name (f=(!!).(...) and then call it via f 10 1 (as an example for the first test case).

Explanation: The lambda function (\y->sum[1|t<-[1..y],gcd y t<2]) is the totient function. iterate f x produces an infinite list [x,f(x),f(f(x)),f(f(f(x))),...] and !! is just for accessing this list at a specific index.

Older version:

x#n=(iterate(\y->sum[1|t<-[1..y],gcd y t<2])x)!!n

Usage e.g. for the first test case: 10#1.

Answer 10

CJam, 20 bytes

q~{_mf1|1-{1$\/-}/}*

Try it online!

How it works

q~                    Read and evaluate all input. Pushes x and n.
  {               }*  Repeat n times:
   _mf                  Compute the prime factorization of a copy of x.
      1|1-              Add and remove 1 from the prime factorization.
                        | deduplicates and - handles the edge case 1mf -> [1].
          {     }/      For each remaining prime p:
           1$             Push a copy of x.
             \/           Swap with p and divide, pushing x/p.
               -          Subtract from x, pushing x-x/p.

Answer 11

Hoon, 84 bytes

|*((pair) ?~(p q $(p (dec p), q (lent (skim (gulf 1 q) |=(@ =(1 d:(egcd +< q))))))))

Ungolfed:

|*  (pair)
  ?~  p
    q
  %=  $
    p  (dec p)
    q  (lent (skim (gulf 1 q) |=(@ =(1 d:(egcd +< q)))))
  ==

Answer 12

Julia, 36 bytes

n\x=n>0?~-n\sum(k->gcd(k,x)<2,1:x):x

Try it online!

Answer 13

Javascript, 88 95

g=(a,b)=>b?g(b,a%b):a==1
t=(x,n=x,o=0)=>n?t(x,--n,o+g(x,n)):o
f=(n,x)=>n?f(n-1,t(x)):x

The first function returns true/false if the greatest commom divisor is 1. The second function calculates the totient. The third function is a simple recursion to do the totient n times.

I took this idea from the wikipedia link:

It can be defined more formally as the number of integers k in the range 1 ≤ k ≤ n for which the greatest common divisor gcd(n, k) = 1;

Answer 14

Perl 6,  47 45 44 43 42 41  39 bytes

{($^x,{+(^$^x .grep: {$_ gcd$x==1})}...*)[$^n]}
{($^x,{+(^$^x Xgcd $x).grep: *==1}...*)[$^n]}
{($^x,{+grep *==1,(^$^x Xgcd $x)}...*)[$^n]}
{($^x,{+grep *==1,(^$^x Xgcd$x)}...*)[$^n]}
{($^x,{+grep 2>*,(^$^x Xgcd$x)}...*)[$^n]}
{($^x,{+grep 2>*,(^$_ Xgcd$_)}...*)[$^n]}
{($^x,{sum 2 X>(^$_ Xgcd$_)}...*)[$^n]}

Explanation:

{ # parameters are $n,$x ( declared as placeholder parameters )
  (

    $^x, # seed sequence generator with second argument

    { # parameter is $_
      sum
        2
        X[>] # crossed compared using &infix«>»
        (
          0 ..^ $_ # from 0 up to and excluding the parameter
          X[gcd]   # cross apply &infix:<gcd> with:
          $_       # the parameter
        )
    }

    ...  # keep applying that block

    *    # forever

  )[ $^n ] # grab the one at the index indicated by the first argument
}

Test:

use v6.c;
use Test;

my @tests = (
  (1, 10) =>  4,
  (2, 10) =>  2,
  (3, 10) =>  1,
  (1,100) => 40,
  (2,100) => 16,
  (3,100) =>  8,
  (4,100) =>  4,
  (5,100) =>  2,
  (6,100) =>  1,
);

plan +@tests;

my &repeated-totient = {($^x,{sum 2 X>(^$_ Xgcd$_)}...*)[$^n]}

for @tests -> $_ ( :key(@input), :value($expected) ) {
  is repeated-totient(|@input), $expected, .gist
}

1..9
ok 1 - (1 10) => 4
ok 2 - (2 10) => 2
ok 3 - (3 10) => 1
ok 4 - (1 100) => 40
ok 5 - (2 100) => 16
ok 6 - (3 100) => 8
ok 7 - (4 100) => 4
ok 8 - (5 100) => 2
ok 9 - (6 100) => 1