# 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. Commented Jun 22, 2016 at 7:14
• Disallowing built-ins apparently has no impact on the answers. Commented Jun 22, 2016 at 7:39
• @JuliePelletier Why is that? My Mathematica answer would otherwise have been 19 bytes shorter: EulerPhi Commented Jun 22, 2016 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. Commented Jun 22, 2016 at 7:44

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

• You can alternatively use ;╗R╜g1=MΣ for the same byte count
– user45941
Commented Jun 22, 2016 at 8:50

## JavaScript (ES6), 67 bytes

f=n=>[...Array(n)].reduce(r=>r+=g(n,++i)<2,i=0,g=(a,b)=>b?g(b,a%b):a)


## Batch, 151145 144 bytes

@echo off
set t=
for /l %%i in (1,1,%1)do call:g %1 %%i
echo %t%
exit/b
:g
set/ag=%1%%%2
if not %g%==0 call:g %2 %g%
if %2%==1 set/at+=1


Edit: Saved 4 bytes by removing unnecessary spaces. Saved 1 byte by using +=. Saved 1 byte by clearing t as += will interpret that as 0 anyway. Saved 1 byte thanks to @EʀɪᴋᴛʜᴇGᴏʟғᴇʀ.

# Pari/GP, 24 bytes

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


Try it online!

# TI-84 BASIC, 19 bytes

Prompt A:sum(seq(1=gcd(A,B),B,1,A


# Japt-mx, 2 bytes

jN


Try it here

• ?? How it works ?? Commented Dec 8, 2019 at 20:51

# JavaScript (Node.js), 42 bytes

n=>(g=k=>k&&((k/n|0)*k%n>n-2)+g(k-1))(n*n)


Try it online!

Direct port of Dennis' solution (<- also see the explanation in that answer) to JavaScript.

Alternatives:

n=>(g=k=>k&&g(k-1)+!(~((k/n|0)*k)%n))(n*n)
n=>(g=k=>k&&g(k-1)+!(((k/n|0)*k-1)%n))(n*n)
n=>(g=k=>k&&g(k-1)+!((k/n|0)*k%n-n+1))(n*n)
f=(n,k=0)=>k<n*n&&((k/n|0)*k%n>n-2)+f(n,k+1)

• I think this can be useful in other challenges, since it's shorter than all the existing JavaScript answers. Commented Jul 26, 2020 at 3:10

# Vyxals, 5 bytes

ɾ$ġ1=  Try it Online! No totient builtin Inclusive range, swap with input, gcd, equal to 1, sum # Thunno 2L, 3 bytes æĠḅ  Try it online! #### Explanation æĠḅ # Implicit input æ # Filter by: Ġ # GCD with input ḅ # Equals one? # Length of list # Implicit output  ## Hoon, 56 bytes |= a/@ (lent (skim (gulf 1 a) |=(@ =(1 d:(egcd +< a)))))  Measure the length of the list [1...a] after keeping all the elements where GCD(i, a) == 1 # Arturo, 34 bytes $->n[enumerate..1n'x->2>gcd@[x,n]]


Try it

# ><> (Fish), 76 bytes

0i::?v~~n;
v&~$1\:&:&:&%?v$:&:&%?
/~v?:-2&      <
r \1+\20.
1.   \6
\+r1-20.


Try it

# SageMath, 41 bytes

Run it on SageMathCell!

f=lambda n:sum(gcd(i,n)<2 for i in[1..n])


# Nekomata, 4 bytes

RG1Ĉ


Attempt This Online!

RG1Ĉ
R       Range from 1 to input
G      GCD
1Ĉ    Count 1s