6
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ Extremely closely related, almost as closely related. \$\endgroup\$ – Peter Taylor Jun 16 '16 at 9:49
  • \$\begingroup\$ You know, people who does not use the proper name (totient) makes it hard to find. \$\endgroup\$ – Leaky Nun Jun 16 '16 at 9:51
  • 1
    \$\begingroup\$ I found both of those by searching for totient \$\endgroup\$ – Peter Taylor Jun 16 '16 at 10:04
  • \$\begingroup\$ @PeterTaylor I see. I only searched the question. \$\endgroup\$ – Leaky Nun Jun 16 '16 at 10:08
  • 5
    \$\begingroup\$ 1) The repeated application is completely unnecessary for this challenge, 2) That's a sigma, not a phi, right? \$\endgroup\$ – Sp3000 Jun 16 '16 at 10:10

14 Answers 14

8
\$\begingroup\$

05AB1E, 2 bytes

Code:

Explanation:

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

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

\$\endgroup\$
  • 1
    \$\begingroup\$ You beat me by 30 seconds. Should have done the explanation faster :P \$\endgroup\$ – Emigna Jun 16 '16 at 9:45
  • 4
    \$\begingroup\$ @Emigna First post a minimal answer, then add the explanation :-) \$\endgroup\$ – Luis Mendo Jun 16 '16 at 9:50
  • \$\begingroup\$ We have a winner here... \$\endgroup\$ – Leaky Nun Jun 16 '16 at 18:45
5
\$\begingroup\$

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,

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:

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.

\$\endgroup\$
  • \$\begingroup\$ That nested string execution looks neat... do you mind adding an explanation? \$\endgroup\$ – Yytsi Jun 16 '16 at 16:33
  • 1
    \$\begingroup\$ I've edited my answer. \$\endgroup\$ – Dennis Jun 16 '16 at 17:04
  • \$\begingroup\$ 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]. \$\endgroup\$ – xnor Jun 17 '16 at 0:55
  • \$\begingroup\$ 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. \$\endgroup\$ – xnor Jun 17 '16 at 1:05
  • \$\begingroup\$ @xnor That's very clever and saved a lot of bytes. Thank you! \$\endgroup\$ – Dennis Jun 17 '16 at 1:34
4
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ This messes with my brain ▒_▒ \$\endgroup\$ – Bassdrop Cumberwubwubwub Jun 16 '16 at 10:51
  • \$\begingroup\$ Is this actually 4 bytes? >_> \$\endgroup\$ – Geobits Jun 16 '16 at 22:40
  • \$\begingroup\$ @Geobits You're seriously very funny. \$\endgroup\$ – Mego Jun 16 '16 at 22:48
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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))
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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]]. \$\endgroup\$ – xnor Jun 16 '16 at 20:55
  • \$\begingroup\$ Ah I always forget about the <$>, thanks! \$\endgroup\$ – flawr Jun 16 '16 at 21:08
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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)))))
  ==
\$\endgroup\$
0
\$\begingroup\$

Julia, 36 bytes

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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;

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ So just to confirm... I shouldn't have to cite PPCG in my production Perl? \$\endgroup\$ – NoOneIsHere Jun 16 '16 at 21:50
  • \$\begingroup\$ @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 ) \$\endgroup\$ – Brad Gilbert b2gills Jun 17 '16 at 18:52
  • \$\begingroup\$ I was joking. I can't read or comprehend Perl. \$\endgroup\$ – NoOneIsHere Jun 17 '16 at 19:02
  • 1
    \$\begingroup\$ @NoOneIsHere Why not? Perl 6 is easier to read and comprehend than Python \$\endgroup\$ – Brad Gilbert b2gills Jun 17 '16 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.