35
\$\begingroup\$

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

Shortest answer in bytes wins. If your language uses an encoding other than UTF-8, mention it in your answer.

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

44 Answers 44

1
2
1
\$\begingroup\$

Actually, 11 bytes

;╗R`╜g`M1@c

Try it online!

Explanation

;╗R`╜g`M1@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!

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

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

Batch, 151 145 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ᴏʟғᴇʀ.

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 24 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

TI-84 BASIC, 19 bytes

Prompt A:sum(seq(1=gcd(A,B),B,1,A
\$\endgroup\$
1
\$\begingroup\$

Japt -mx, 2 bytes

jN

Try it here

\$\endgroup\$
1
  • \$\begingroup\$ ?? How it works ?? \$\endgroup\$
    – AZTECCO
    Dec 8, 2019 at 20:51
1
\$\begingroup\$

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)
\$\endgroup\$
1
  • \$\begingroup\$ I think this can be useful in other challenges, since it's shorter than all the existing JavaScript answers. \$\endgroup\$
    – DELETE_ME
    Jul 26, 2020 at 3:10
1
\$\begingroup\$

Vyxal s, 5 bytes

ɾ$ġ1=

Try it Online!

No totient builtin

Inclusive range, swap with input, gcd, equal to 1, sum

\$\endgroup\$
1
\$\begingroup\$

Thunno 2 L, 3 bytes

æĠḅ

Try it online!

Explanation

æĠḅ  # Implicit input
æ    # Filter by:
 Ġ   #  GCD with input
  ḅ  #  Equals one?
     # Length of list
     # Implicit output
\$\endgroup\$
0
\$\begingroup\$

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

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

Arturo, 34 bytes

$->n[enumerate..1n'x->2>gcd@[x,n]]

Try it

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

><> (Fish), 76 bytes

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

Try it

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

SageMath, 41 bytes

Run it on SageMathCell!

f=lambda n:sum(gcd(i,n)<2 for i in[1..n])
\$\endgroup\$
0
\$\begingroup\$

Nekomata, 4 bytes

RG1Ĉ

Attempt This Online!

RG1Ĉ
R       Range from 1 to input
 G      GCD
  1Ĉ    Count 1s
\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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