# Golf the repeated totient function

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

• Commented Jun 16, 2016 at 9:49
• You know, people who does not use the proper name (totient) makes it hard to find. Commented Jun 16, 2016 at 9:51
• I found both of those by searching for totient Commented Jun 16, 2016 at 10:04
• @PeterTaylor I see. I only searched the question. Commented Jun 16, 2016 at 10:08
• 1) The repeated application is completely unnecessary for this challenge, 2) That's a sigma, not a phi, right? Commented Jun 16, 2016 at 10:10

# 05AB1E, 2 bytes

Code:

FÕ


Explanation:

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


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

• You beat me by 30 seconds. Should have done the explanation faster :P Commented Jun 16, 2016 at 9:45
• @Emigna First post a minimal answer, then add the explanation :-) Commented Jun 16, 2016 at 9:50
• We have a winner here... Commented Jun 16, 2016 at 18:45

# Python 2, 8478 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

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!2 = 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 k2.

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.

• That nested string execution looks neat... do you mind adding an explanation? Commented Jun 16, 2016 at 16:33
• I've edited my answer. Commented Jun 16, 2016 at 17:04
• Another beautiful mathematical solution! It looks like you can do x-=x/k*(x%k<m%k) for x=[x,x/k*~-k][x%k<m%k].
– xnor
Commented Jun 17, 2016 at 0:55
• The exec should work as exec("..."+"..."*x)*n, since there's no harm in using the too-high initial x as the count for each inner loop.
– xnor
Commented Jun 17, 2016 at 1:05
• @xnor That's very clever and saved a lot of bytes. Thank you! Commented Jun 17, 2016 at 1:34

## 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)

• This messes with my brain ▒_▒ Commented Jun 16, 2016 at 10:51
• Is this actually 4 bytes? >_> Commented Jun 16, 2016 at 22:40
• @Geobits You're seriously very funny.
– user45941
Commented Jun 16, 2016 at 22:48

## 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.

## 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.

# 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


# 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.

# 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))


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. • It's shorter to recurse than to iterate x%0=x;x%n=sum[1|t<-[1..x],gcd x t<2]%(n-1). The list comp can be done as [1|1<-gcd x<$>[1..x]].
– xnor
Commented Jun 16, 2016 at 20:55
• Ah I always forget about the <$>, thanks! Commented Jun 16, 2016 at 21:08 # 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.  ## 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))))) ==  # Julia, 36 bytes n\x=n>0?~-n\sum(k->gcd(k,x)<2,1:x):x  Try it online! ## 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; # 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

• So just to confirm... I shouldn't have to cite PPCG in my production Perl? Commented Jun 16, 2016 at 21:50
• @NoOneIsHere Please tell me that you aren't going to use this in production. Also this is Perl 6, usually Perl means Perl 5. I would probably use sub φ ( Int \n ) { sum ^n .race.map: -> \k { k gcd n == 1 } } say φ 36 # 12 ( I'm sure there is a better algorithm though ) Commented Jun 17, 2016 at 18:52
• I was joking. I can't read or comprehend Perl. Commented Jun 17, 2016 at 19:02
• @NoOneIsHere Why not? Perl 6 is easier to read and comprehend than Python Commented Jun 17, 2016 at 19:19