The totient function \$\phi(n)\$, also called Euler's totient function, is defined as the number of positive integers \$\le n\$ that are relatively prime to (i.e., do not contain any factor in common with) \$n\$, where \$1\$ is counted as being relatively prime to all numbers. (from WolframMathworld)


Given an integer \$N > 1\$, output the lowest integer \$M > N\$, where \$\phi(N) = \phi(M)\$. If \$M\$ does not exist, output a non-ambiguous non-positive-integer value to indicate that M does not exist (e.g. 0, -1, some string).

Note that \$\phi(n) \geq \sqrt n\$ for all \$n > 6\$


Where M exists
 15 -> 16  (8)
 61 -> 77  (60)
 465 -> 482 (240)
 945 -> 962 (432) 

No M exists
 12  (4)
 42 (12)
 62 (30)

Standard loopholes apply, shortest answer in bytes wins.


  • 1
    \$\begingroup\$ obviously related \$\endgroup\$
    – Giuseppe
    Commented Dec 4, 2019 at 20:27
  • \$\begingroup\$ M for 8 is 10 - both have phi(x) = 4 \$\endgroup\$ Commented Dec 4, 2019 at 20:49
  • \$\begingroup\$ @NickKennedy thanks, missed that \$\endgroup\$
    – frank
    Commented Dec 4, 2019 at 20:53
  • 2
    \$\begingroup\$ Is it permissible to return the input where there is no M? \$\endgroup\$ Commented Dec 4, 2019 at 21:13
  • 4
    \$\begingroup\$ This is A066659. \$\endgroup\$
    – Arnauld
    Commented Dec 5, 2019 at 1:17

12 Answers 12


JavaScript (ES6),  83 ... 76  74 bytes

Returns true if \$M\$ does not exist.

Derived from this answer by xnor.


Try it online!


Computing \$\phi(n)\$

This is based on the formula:


which implies:


But in the JS implementation, we actually compute:

$$\begin{align}P(n)&=\sum_{d=1}^{n-1}1-\delta_{d|n}P(d)\\ &=n-1-\sum_{d|n,d<n}P(d)\end{align}$$

It leads to the same results, except \$P(1)=0\$ instead of \$\phi(1)=1\$. This is fine because we don't need to support \$n=1\$, as per the challenge rules. And this allows us to do the following recursive call:

P(n % d ? 1 : d)

which evaluates to \$0\$ if \$d\$ is not a divisor of \$n\$.

Wrapper code

At each iteration, we compute \$p=P(n)\$. The result of the first iteration is saved into \$q\$. We then increment \$n\$ until \$p=q\$ (success) or \$p>q^2\$ (failure).


Jelly,  11  10 bytes


A monadic Link accepting a positive integer which yields a non-negative integer (0 if no \$M\$ exists).

Try it online!


r²ÆṪẹḢ$+⁸Ḣ - Link: integer, n
 ²         - (n) squared
r          - (n) inclusive range (n²)
  ÆṪ       - Euler totient (vectorises)
      $    - last two links as a monad:
     Ḣ     -   head    - i.e. yield totient(n)
                           and leave [totient(n+1),...,totient(n²)]
    ẹ      -   indices of (i.e. a list of offsets to higher Ms)
        ⁸  - chain's left argument (n)
       +   - add (vectorises) (i.e. a list of higher Ms)
         Ḣ - head (note head-ing an empty list yields zero)
  • \$\begingroup\$ Thanks guys. @Mr.Xcoder More 12s I got along the way: ²ÆṪ€ẹị@¥>Ƈ⁸Ḣ and ²ÆṪ€=ÆṪT>Ƈ⁸Ḣ \$\endgroup\$ Commented Dec 4, 2019 at 22:50
  • \$\begingroup\$ @Mr.Xcoder Oh, but TIO \$\endgroup\$ Commented Dec 4, 2019 at 22:52
  • \$\begingroup\$ Sighs. Just when I thought I found a 9. \$\endgroup\$
    – Mr. Xcoder
    Commented Dec 4, 2019 at 22:54

Perl 6, 57 52 bytes

-5 bytes using the .& operator thanks to Jo King

{first *.&($!={grep 1,($_ Xgcd^$_)})==.$!,$_^..$_²}

Try it online!

Returns Nil if no solution was found.


{                                                 }  # Anonymous block
                       $_ Xgcd^$_     # gcds of m and 0..m-1
               grep 1,                # Filter 1s
              {                   }   # Totient function
          ($!=                     )  # Assign to $!
 first                                   ,$_^..$_²  # First item of n+1..n² where
       *.&                          ==.$!           # ϕ(m) == ϕ(n)

Jelly, 13 12 bytes


Try it online!

A monadic link taking an integer and returning the next integer with shared totient or zero.


Main link (takes integer argument z)

r²           | Range from z to z ** 2 inclusive
  ÆṪ         | Totient function of each
       $     | Following as a monad
    =€Ḣ      | - Check whether each equal to the first, popping the first before doing so
        T    | Truthy indices
         +⁸  | Plus z
           Ḣ | - Head (returns 0 if the previous link yielded an empty list)

05AB1E, 11 10 9 7 bytes


-1 byte with help from @ExpiredData.
-2 bytes thanks to @Grimmy.

Outputs -1 if no \$m\$ exists.

Try it online or verify all test cases.


L        # Push a list in the range [1, (implicit) input-integer n]
 +       # Add the (implicit) input-integer n to each to make the range [n+1, 2n]
  .Δ     # Get the first value of this list which is truthy for
         # (or results in -1 if none are truthy):
    ‚    #  Pair the current value with the (implicit) input-integer n
     Õ   #  Get the Euler's totient of both
      Ë  #  Check whether both are equal to each other
         # (after which the result is output implicitly)

Most answers use \$n^2\$ as the range to check in, but this answer uses \$2n\$ instead to save a byte. If we look at the Mathematica implementation on the oeis sequence A066659 we can see it also uses the range \$[n+1, 2n+1)\$ to check in.

  • 1
    \$\begingroup\$ Maybe this 10 bytes is easier to work with? It feels like I'm missing an obvious way to remove a byte \$\endgroup\$ Commented Dec 5, 2019 at 12:14
  • 1
    \$\begingroup\$ @ExpiredData Ah, nice! I had something similar at first, except that I had instead of ¦¬. You can remove the s by using ¬QÏ instead. :) Thanks, this is now the 9-byter: nŸDÕ¬QϦн \$\endgroup\$ Commented Dec 5, 2019 at 14:25
  • 1
    \$\begingroup\$ conveniently defaults to -1 when no result is found, saving one byte: nŸ¦.Δ‚ÕË. \$\endgroup\$
    – Grimmy
    Commented Dec 5, 2019 at 15:28
  • 1
    \$\begingroup\$ The Mathematica snippet on the OEIS page for this sequence suggests that testing up to 2n is enough. If this is true, L+.Δ‚ÕË saves another byte. \$\endgroup\$
    – Grimmy
    Commented Dec 5, 2019 at 15:32
  • \$\begingroup\$ @Grimmy Oh, very nice! And nicely spotted of the \$<2n\$ in the Mathematica implementation of the oeis sequence! :) \$\endgroup\$ Commented Dec 5, 2019 at 19:47

Gaia, 11 bytes


Try it online!

:s		| push n,n^2
  U		| push range [n, n + 1, ..., n^2]
   t¦		| calculate [phi(n),phi(n+1), ..., phi(n^2)]
     ṇ		| push [phi(n+1), phi(n+2), ..., phi(n^2)], phi(n)
      =∆	| find 1-based index of first in the list equal to phi(n), returning 0 if none
	:	| dup the index
	 +¿	| if the index is falsey, do nothing (leaving 0 on the stack)
		| otherwise add (implicitly) n
		| and implicitly print top of stack

Python 2, 115 bytes

lambda N:next((j for j in range(N+1,max(6,t(N)**2))if t(j)==t(N)),0)
t=lambda n:sum(k/n*k%n>n-2for k in range(n*n))

Try it online!

Returns 0 for falsey. The totient function t is based on Dennis's answer to a previous question.

Times out on TIO for N=62.


Ruby, 70 68 bytes


Try it online!

Returns nil if not found.

  • \$\begingroup\$ Downvoted because... ? \$\endgroup\$
    – G B
    Commented Dec 6, 2019 at 6:49
  • \$\begingroup\$ I accidentally fat-fingered a downvote in the mobile app when you first posted. I can't undo it unless you make an edit. Make one, and tag me in a comment, and i will reverse it. Sorry about that! \$\endgroup\$
    – JPeroutek
    Commented Feb 12, 2020 at 16:39
  • \$\begingroup\$ @JPeroutek done \$\endgroup\$
    – G B
    Commented Feb 20, 2020 at 15:10
  • \$\begingroup\$ @G B fixed! sorry about that! \$\endgroup\$
    – JPeroutek
    Commented Feb 20, 2020 at 15:42

Python 3, 160 121 bytes

Saved 39 bytes thanks to @JoKing!

Returns None if no \$M\$ exists:

import math
t=lambda n:sum(math.gcd(i,n)<2for i in range(n))
def s(x):
 while n<x*x:
  if t(n)==t(x):return n

Try it online!

If throwing an exception is allowed when no \$M\$ exists:

Python 3, 145 114 bytes

Saved 31 bytes thanks to @JoKing!

lambda n:[t(i+1)for i in range(n,n*n)].index(t(n))-~n
import math
t=lambda n:sum(math.gcd(i,n)<2for i in range(n))

Try it online!


Python 3, 97 bytes

lambda x,n=1:[n>x*x,x+n][t(x+n)==t(x)]or s(x,n+1)
t=lambda n:sum(k//n*k%n>n-2for k in range(n*n))

Try it online!

Totient function taken from Chas Brown's answer, originally from Dennis.Returns True for cases where M doesn't exist, though if that doesn't satisfy you, a far less efficient version that returns False is only two bytes longer.


J, 42 31 bytes

(1{]) ::0[([+[:I.{=}.)5 p:i.@*:

Try it online!

Returns 0 if no \$M\$ exists.

Explanation :

(of the previous version)

The argument is n

                              @*:   find n^2 and   
                            i.      make a list 0..n^2-1
                           +        to each number in the list add
                          ]         the argument (n) -> list n..n^2+n-1
                      5 p:          find the totient of each number in the above list
                    @(           )  use the above result as an argument for 
          (        )                the next verb 
                =                   compare
                 {.                 the head of the list
               ]                    with each number in the list  
           [:I.                     get the indices where the above is true
 (    ) ::0                         try the verb in parentheses and return 0 if it failed
   1{]                              get the second (0-based indexing) element
  +                                 and add n to it

Japt, 21 19 bytes

ôU ÅæÈo èjX ¥Uo èjU

Try it

ôU                      range [input ...input + input]
   Å                    cut off first element 
      æÈ                return the first element to return a truty value when passed to:
        o               range [0... next element]
          è             number of elements that are..
           jX           coprime to next element.
              ¥         equal to
               Uo èjU   num of coprimes of input 

Outputs null if no \$m\$ exists.

Thanks to @Shaggy for reminding me of ô() which gives the range needed

  • 1
    \$\begingroup\$ 19 bytes \$\endgroup\$
    – Shaggy
    Commented Dec 9, 2019 at 9:12

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.