# Background

Euler's totient function φ(n) is defined as the number of whole numbers less than or equal to n that are relatively prime to n, that is, the number of possible values of x in 0 < x <= n for which gcd(n, x) == 1. We've had a few totient-related challenges before, but never one which is just calculating it.

The mapping of the totient function onto the whole numbers is OEIS A000010.

# Challenge

Given an integer n > 0, calculate φ(n). You may take input through command-line arguments, standard input, function arguments, or anything else reasonable. You may give output through standard output, return values, or anything else reasonable. Anonymous functions are acceptable. You may assume that the input will not overflow your natural method of storing integers, e.g. int in C, but you must support inputs up to 255. If your language has a built-in totient function, you may not use it.

# Examples

φ(1) => 1
φ(2) => 1
φ(3) => 2
φ(8) => 4
φ(9) => 6
φ(26) => 12
φ(44) => 20
φ(105) => 48


• Well there was this the other day. I don't think the repeated application makes a sufficient difference, but if anything I'd close the other one, because I also don't think the repeated application adds anything. That said, the bigger difference is that that one allowed built-ins and this one doesn't. – Martin Ender Jun 22 '16 at 7:14
• Disallowing built-ins apparently has no impact on the answers. – Julie Pelletier Jun 22 '16 at 7:39
• @JuliePelletier Why is that? My Mathematica answer would otherwise have been 19 bytes shorter: EulerPhi – Martin Ender Jun 22 '16 at 7:40
• @JuliePelletier GCD is allowed because calculating GCD is not the intended problem to be solved. Sure, it might bump up the byte counts on these answers, but it doesn't make the challenge better. I'll edit to clarify. – jqblz Jun 22 '16 at 7:44

## Mathematica, 27 22 bytes

Range@#~GCD~#~Count~1&


An unnamed function that takes and returns an integer.

Not much to explain here, except that @ is prefix notation for function calls and ~...~ is (left-associative) infix notation, so the above is the same as:

Count[GCD[Range[#], #], 1] &


# J, 9 bytes

(-~:)&.q:


This is based on the Jsoftware's essay on totient functions.

Given n = p1e1p2e2 ∙∙∙ pkek where pk is a prime factor of n, the totient function φ(n) = φ(p1e1) ∙ φ(p2e2) ∙∙∙ φ(pkek) = (p1 - 1) p1e1 - 1 ∙ (p2 - 1) p2e2 - 1 ∙∙∙ (pk - 1) pkek - 1.

## Usage

   f =: (-~:)&.q:
(,.f"0) 1 2 3 8 9 26 44 105
1  1
2  1
3  2
8  4
9  6
26 12
44 20
105 48
f 12345
6576


## Explanation

(-~:)&.q:  Input: integer n
q:  Prime decomposition. Get the prime factors whose product is n
(   )&     Operate on them
~:         Nub-sieve. Create a mask where 1 is the first occurrence
of a unique value and 0 elsewhere
-           Subtract elementwise between the prime factors and the mask
&.q:  Perform the inverse of prime decomposition (Product of the values)

• Use the fact that totient is multiplicative to make another solution in J using recursion :) – Leaky Nun Jun 22 '16 at 10:29
• @LeakyNun I don't think there's an easy way to golf the factoring, since even using the iterative form [:*/@({.(^-(^<:)){:)2&p: needs 24 bytes, even using the builtin to get the the primes and their exponents. Or maybe there's a shorter way and I don't see it. – miles Jun 22 '16 at 10:59

# MATL, 7 bytes

t:Zd1=s


You can TryItOnline. Simplest idea, make a vector 1 to N, and taken gcd of each element with N (Zd does gcd). Then, find which elements are equal to 1, and sum the vector to get the answer.

• The builtin is _Zp for those wondering. – David Jun 22 '16 at 8:01

f n=sum[1|1<-gcd n<$>[1..n]]  Uses Haskell's pattern matching of constants. The tricks here are fairly standard for golfing, but I'll explain to a general audience. The expression gcd n<$>[1..n] maps gcd n onto [1..n]. In other words, it computes the gcd with n of each number from 1 to n:

[gcd n i|i<-[1..n]]


From here, the desired output is the number of 1 entries, but Haskell lacks a count function. The idiomatic way to filter to keep only 1's, and take the resulting length, which is much is too long for golfing.

Instead, the filter is simulated by a list comprehension [1|1<-l] with the resulting list l. Usually, list comprehensions bind values onto variable like in [x*x|x<-l], but Haskell allows a pattern to be matched against, in this case the constant 1.

So, [1|1<-l] generating a 1 on each match of 1, effectively extracting just the 1's of the original list. Calling sum on it gives its length.

• I think this is the first Haskell answer I actually understand. It's such a cool language, but it's so different from most others. – jqblz Jun 23 '16 at 7:17
• Wow, I expected that pattern matching had to be exhaustive in comprehension lists. Thanks for the trick. – Damien Jun 23 '16 at 8:54

## Python 2, 44 bytes

f=lambda n,d=1:d/n or-f(d)*(n%d<1)-~f(n,d+1)


Less golfed:

f=lambda n:n-sum(f(d)for d in range(1,n)if n%d<1)


Uses the formula that the Euler totients of the divisors of n have a sum of n:

The value of ϕ(n) can then be recursively computed as n minus the sum over nontrivial divisors. Effectively, this is doing Möbius inversion on the identity function. I used the same method in a golf to compute the Möbius function.

Thanks to Dennis for saving 1 byte with a better base case, spreading the initial value of +n into +1 for each of the n loops, done as -~.

# Jelly, 4 bytes

Rgċ1


Try it online!

### Explanation

Rgċ1   Main monadic chain. Argument: z

R      Yield [1 2 3 .. z].
g     gcd (of each) (with z).
ċ1   Count the number of occurrences of 1.


## With built-in

ÆṪ


Try it online!

### Explanation

ÆṪ   Main monadic chain. Argument: z

ÆṪ   Totient of z.


# Regex (ECMAScript), 131 bytes

At least -12 bytes thanks to Deadcode (in chat)

(?=((xx+)(?=\2+$)|x+)+)(?=((x*?)(?=\1*$)(?=(\4xx+?)(\5*(?!(xx+)\7+$)\5)?$)(?=((x*)(?=\5\9*$)x)(\8*)$)x*(?=(?=\5$)\1|\5\10)x)+)\10|x  Try it online! Output is the length of the match. ECMAScript regexes make it extremely hard to count anything. Any backref defined outside a loop will be constant during the loop, any backref defined inside a loop will be reset when looping. Thus, the only way to carry state across loop iterations is using the current match position. That’s a single integer, and it can only decrease (well, the position increases, but the length of the tail decreases, and that’s what we can do math to). Given those restrictions, simply counting coprime numbers seems impossible. Instead, we use Euler’s formula to compute the totient. Here’s how it looks like in pseudocode: N = input Z = largest prime factor of N P = 0 do: P = smallest number > P that’s a prime factor of N N = N - (N / P) while P != Z return N  There are two dubious things about this. First, we don’t save the input, only the current product, so how can we get to the prime factors of the input? The trick is that (N - (N / P)) has the same prime factors > P as N. It may gain new prime factors < P, but we ignore those anyway. Note that this only works because we iterate over the prime factors from smallest to greatest, going the other way would fail. Second, we have to remember two numbers across loop iterations (P and N, Z doesn’t count since it’s constant), and I just said that was impossible! Thankfully, we can swizzle those two numbers in a single one. Note that, at the start of the loop, N will always be a multiple of Z, while P will always be less than Z. Thus, we can just remember N + P, and extract P with a modulo. Here’s the slightly more detailed pseudo-code: N = input Z = largest prime factor of N do: P = N % Z N = N - P P = smallest number > P that’s a prime factor of N N = N - (N / P) + P while P != Z return N - Z  And here’s the commented regex: # \1 = largest prime factor of N # Computed by repeatedly dividing N by its smallest factor (?= ( (xx+) (?=\2+$) | x+ )+ )

(?=
# Main loop!
(
# \4 = N % \1, N -= \4
(x*?) (?=\1*$) # \5 = next prime factor of N (?= (\4xx+?) (\5* (?!(xx+)\7+$) \5)? $) # \8 = N / \5, \9 = \8 - 1, \10 = N - \8 (?= ((x*) (?=\5\9*$) x) (\8*) $) x* (?= # if \5 = \1, break. (?=\5$) \1
|
# else, N = (\5 - 1) + (N - B)
\5\10
)
x
)+
) \10


And as a bonus…

## Regex (ECMAScript 2018, number of matches), 23 bytes

x(?<!^\1*(?=\1*$)(x+x))  Try it online! Output is the number of matches. ECMAScript 2018 introduces variable-length look-behind (evaluated right-to-left), which makes it possible to simply count all numbers coprime with the input. It turns out this is independently the same method used by Leaky Nun's Retina solution, and the regex is even the same length (and interchangeable). I'm leaving it here because it may be of interest that this method works in ECMAScript 2018 (and not just .NET).  # Implicitly iterate from the input to 0 x # Don’t match 0 (?<! ) # Match iff there is no... (x+x) # integer >= 2... (?=\1*$)       # that divides the current number...
^\1*               # and also divides the input


## Pyke, 5 bytes

m.H1/


Try it here!

count(map(gcd, range(input)), 1)

• So many Python derivatives.. I like this one though. Interesting premise. – jqblz Jun 22 '16 at 8:15

# J, 11 bytes

+/@(1=+.)i.


## Usage

>> f =: +/@(1=+.)i.
>> f 44
<< 20


where >> is STDIN and << is STDOUT.

## Explanation

+/ @ ( 1 = +. ) i.
│
┌───────────┴┐
+/@(1=+.)      i.
│
┌─┼──┐
+/ @ 1=+.
┌─┼─┐
1 = +.

>> (i.) 44            NB. generate range
<< 0 1 2 3 4 ... 43
>> (+.i.) 44          NB. calculate gcd of each with input
<< 44 1 2 1 4 ... 1
>> ((1=+.)i.) 44      NB. then test if each is one (1 if yes, 0 if no)
<< 0 1 0 1 0 ... 1
>> (+/@(1=+.)i.) 44   NB. sum of all the tests
<< 20

• How did you get the vertical tree representation? I thought it only produced horizontal. – miles Jun 22 '16 at 8:51
• @miles I typed it myself. – Leaky Nun Jun 22 '16 at 9:01

# Python >=3.5, 7664 58 bytes

Thanks to LeakyNun for golfing off 12 (!) bytes.

Thanks to Sp3000 for golfing off 6 bytes.

import math
lambda n:sum(math.gcd(n,x)<2for x in range(n))


I love how readable Python is. This makes sense, even through the golfedness.

• lambda n:sum(gcd(n,x)<2for x in range(n)) – Leaky Nun Jun 22 '16 at 7:39
• Oh, Python finally added gcd to the math module! I didn't know it. – rubik Jun 23 '16 at 13:24

# Perl 6,  26 24  22 bytes

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

### Explanation:

{
[+] # reduce using &infix:<+>
2
X[>] # crossed compared using &infix:«>»
(
^$_ # up to the input ( excludes input ) X[gcd] # crossed using &infix:<gcd>$_     # the input
)
}


### Example:

#! /usr/bin/env perl6
use v6.c;

my &φ = {[+] 2 X>(^$_ Xgcd$_)};

say φ(1) # 1
say φ(2) # 1
say φ(3) # 2
say φ(8) # 4
say φ(9) # 6
say φ(26) # 12
say φ(44) # 20
say φ(105) # 48

say φ 12345 # 6576


# Brachylog, 25 bytes

:{:1e.$pdL,?$pd:LcCdC}fl.


### Explanation

Brachylog has no GCD built-in yet, so we check that the two numbers have no prime factors in common.

• Main predicate:

:{...}fl.             Find all variables which satisfy predicate 1 when given to it as
output and with Input as input.
Unify the Output with the length of the resulting list

• Predicate 1:

:1e.                  Unify Output with a number between Input and 1
$pdL L is the list of prime factors of Output with no duplicates , ?$pd:LcC     C is the concatenation of the list of prime factors of Input with
no duplicates and of L
dC   C with duplicates removed is still C


# Julia, 25 bytes

!n=sum(i->gcd(i,n)<2,1:n)


It's simple - the sum function allows you to give it a function to apply before summing - basically the equivalent of running map and then sum. This directly counts the number of relatively prime numbers less than n.

# Python 2, 57 bytes

f=lambda n,k=1,m=1:n*(k>n)or f(n-(n%k<m%k)*n/k,k+1,m*k*k)


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

At all times, the variable m will be equal to the square of the factorial of k - 1. In fact, we named arguments default to k = 1 and m = 0!2 = 1.

As long as k ≤ n, n*(k>n) evaluates to 0 and the code following or gets executed.

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, (n%k<m%k)*n/k yields n / k, and subtracting it from n replaces its previous value with n(1 - 1/k), as in Euler's product formula. Otherwise, (n%k<m%k)*n/k yields 0 and n remains unchanged.

After computing the above, we increment k and multiply m by the "old" value of k2, thus maintaining the desired relation between k and m, then call f recursively with the updated arguments.

Once k exceeds n, n*(k>n) evaluates to n, which is returned by the function.

# Ruby, 32 bytes

->n{(1..n).count{|i|i.gcd(n)<2}}


a lambda that takes an integer n, and returns the counts of how many integers in the range (1..n) are coprime with n.

• Hello, and welcome to PPCG! This is a great first post. – NoOneIsHere Jun 23 '16 at 18:43
• Welcome to Programming Puzzles and Code Golf! This is a great first solution, keep it up! – jqblz Jun 23 '16 at 18:43
• Thanks, not really that short, I wonder if it's possible to improve it. – Redouane Red Jun 23 '16 at 18:54

# Python 2, 44 bytes

lambda n:sum(k/n*k%n>n-2for k in range(n*n))


This uses the same method to identify coprimes as my answer to “Coprimes up to N”.

Try it online!

• With, I see, the slight adjustment of checking for a product of n-1 instead of 1, which makes it work for n==1. – Ørjan Johansen Feb 23 '19 at 0:49

# Pyth, 6 bytes

smq1iQ


Try it online!

/iLQQ1


Try it online!

## Explanation

smq1iQ     input as Q
smq1iQdQ   implicitly fill variables

m     Q   for d in [0 1 2 3 .. Q-1]:
iQd        gcd of Q and d
q1           equals 1? (1 if yes, 0 if no)
s          sum of the results

/iLQQ1     input as Q

iLQQ      gcd of each in [0 1 2 3 .. Q-1] with Q
/    1     count the number of occurrences of 1


## PowerShell v2+, 72 bytes

param($n)1..$n|%{$a=$_;$b=$n;while($b){$a,$b=$b,($a%$b)};$o+=!($a-1)};$o  PowerShell doesn't have a GCD function available to it, so I had to roll my own. This takes input $n, then ranges from 1 to $n and pipes those into a loop |%{...}. Each iteration we set two helper variables $a and $b and then execute a GCD while loop. Each iteration we're checking that $b is still non-zero, and then saving $a%$b to $b and the previous value of $b to $a for the next loop. We then accumulate whether $a is equal to 1 in our output variable $o. Once the for loop is done, we place $o on the pipeline and output is implicit.

As an example of how the while loop works, consider $n=20 and we're on $_=8. The first check has $b=20, so we enter the loop. We first calculate $a%$b or 8%20 = 8, which gets set to $b at the same time that 20 gets set to $a. Check 8=0, and we enter the second iteration. We then calculate 20%8 = 4 and set that to $b, then set $a to 8. Check 4=0, and we enter the third iteration. We calculate 8%4 = 0 and set that to $b, then set $a to 4. Check 0=0 and we exit the loop, so the GCD(8,20) is $a = 4. Thus, !($a-1) = !(4-1) = !(3) = 0 so $o += 0 and we don't count that one.

# Factor, 50 bytes

[ dup iota swap '[ _ gcd nip 1 = ] filter length ]


Makes a range (iota) n, and curries n into a function which gets gcd x n for all values of 0 <= x <= n, tests if the result is 1. Filter the original range on whether the result of gcd x n was 1, and take its length.

• [ dup iota swap '[ _ gcd nip 1 = ] map sum ] saves 6 bytes (I think - not very experienced with Factor). – jqblz Jun 24 '16 at 1:49
• @bkul Thanks for the suggestion! :D Unfortunately, there is no compatibility whatsoever between numbers and t/f (symbols) in Factor, so the only way to implement that would be with [ dup iota swap '[ _ gcd nip 1 = 1 0 ? ] map sum ], which is the same exact length as the current solution. – cat Jun 24 '16 at 1:58
• Ah, dang. Strong typing strikes again. – jqblz Jun 24 '16 at 1:59
• @bkul Well, I'm thankful for strong typing and TYPED: in real Factor code :P – cat Jun 24 '16 at 2:16

# Japt -mx, 7 5 bytes

yN ¥1


Run it online

-2 bytes thanks to Shaggy

• 5 bytes using -mx. – Shaggy Feb 23 '19 at 22:25
• @Shaggy Ah, nice. I tried an -m solution but forgot about -x. Thanks! – Oliver Feb 24 '19 at 2:31

# C (gcc), 67 65 bytes

f(x,a,b,y,z){for(z=y=x;a=y--;z-=b>1)for(b=x;a^=b^=a^=b%=a;);x=z;}


Try it online!

Edit: Removed temp variable.

Edit2: -1 thanks to @HowChen

Slightly less golfed

f(x,a,b,y,z){
// counts y NOT coprime with x and subtract
for(z=y=x;a=y--;z-=b>1)
// compute GCD
for(b=x;a^=b^=a^=b%=a;);
x=z;
}


# Retina, 36 29 bytes

7 bytes thanks to Martin Ender.

.+
$* (?!(11+)\1*$(?<=^\1+)).


Try it online!

## Explanation

There are two stages (commands).

### First stage

.+
$*  It is a simple regex substitution, converting the input to that many ones. For example, 5 would be converted to 11111. ### Second stage (?!(11+)\1*$(?<=^\1+)).


This regex tries to match the positions which satisfy the condition (co-prime with input), and then return the number of matches.

• Lookbehind does not backtrack unless inside a lookahead? – Leaky Nun Jun 22 '16 at 9:47
• Lookarounds don't backtrack in general. – Martin Ender Jun 22 '16 at 9:48
• Then how is it that the regex tested every divisor? – Leaky Nun Jun 22 '16 at 9:48
• Well they do backtrack as long as you don't leave them. As long as the engine is inside the lookaround it will try everything possible to make that lookaround match (or fail in the case of a negative lookaround). But once the lookaround is passed, the engine will not backtrack into it if anything after it fails (unless it then also starts to backtrack things in front of the lookaround and has to reevaluate everything anyway). – Martin Ender Jun 22 '16 at 9:50

## 05AB1E, 7 bytes

Lvy¹¿i¼


Explained

Lv        # for each x in range(1,n)
y¹¿     # GCD(x,n)
i¼   # if true (1), increase counter
# implicitly display counter


Try it online

Common Lisp, 58 bytes

(defun o(x)(loop for i from 1 to x if (=(gcd x i)1)sum 1))


This is a simple loop which counts up 1 to the given n and increments the sum if gcd = 1. I use the function name o since t is the true boolean value. Not nearly the shortest but fairly simple.

• Does CL not have some sort of anonymous function? – cat Jun 23 '16 at 22:17

# MATLAB / Octave, 21 bytes

@(n)sum(gcd(n,1:n)<2)


Creates an anonymous function named ans which can be called with the integer n as the only input: ans(n)

Online Demo

# APL, 7 bytes

+/1=⊢∨⍳


This is a monadic function train that takes an integer on the right. The approach here is the obvious one: sum (+/) the number of times the GCD of the input and the numbers from 1 to the input (⊢∨⍳) is equal to 1 (1=).

Try it here

\n->sum[1|x<-[1..n],gcd n x<2]


1 byte saved, thanks to @Damien.

Selects values with gcd = 1, maps each to 1, then takes the sum.

• You can replace ==1 by <2 – Damien Jun 23 '16 at 6:20

# JavaScript (ES6), 53 bytes

f=(n,k=n)=>k--&&(C=(a,b)=>b?C(b,a%b):a<2)(n,k)+f(n,k)


Try it online!

# Husk, 7 bytes

ṁo=1⌋¹ḣ


Try it online!

ṁo=1⌋¹ḣ
ṁ     ḣ     # sum of function applied to 1..input
o          # join 2 functions:
⌋¹      # greatest common divisor with input
=1        # equals 1


# Actually, 11 bytes

;╗R╜gM1@c


Try it online!

### Explanation

;╗R╜gM1@c   register stack             remarks

44
;                      44 44
╗            44       44
R           44       [1 2 3 .. 44]
M      44       10                for example
╜         44       10 44
g        44       2
44       [1 2 1 .. 44]     gcd of each with register
1     44       [1 2 1 .. 44] 1
@    44       1 [1 2 1 .. 44]
c   44       20                count


## With built-in

▒


Try it online!