Next Shared Totient

Question

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)

Challenge

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\$

Examples

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.

Related

Answer 1

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

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

Derived from this answer by xnor.

f=(n,q,P=(n,d=n)=>p=--d&&P(n,d)+1-P(n%d?1:d))=>P(n)^q?p>q*q||f(n+1,q||p):n

Try it online!

How?

Computing \$\phi(n)\$

This is based on the formula:

$$\sum_{d|n}\phi(d)=n$$

which implies:

$$\phi(n)=n-\sum_{d|n,d<n}\phi(d)$$

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).

Answer 2

Jelly,  11  10 bytes

r²ÆṪẹḢ$+⁸Ḣ

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

Try it online!

How?

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)

Answer 3

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.

Explanation

{                                                 }  # 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)

Answer 4

Jelly, 13 12 bytes

r²ÆṪ=€Ḣ$T+⁸Ḣ

Try it online!

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

Explanation

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)

Answer 5

05AB1E, 11 10 9 7 bytes

L+.Δ‚ÕË

-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.

Explanation:

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.

Answer 6

Gaia, 11 bytes

:sUt¦ṇ=∆:+¿

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

Answer 7

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.

Answer 8

Ruby, 70 68 bytes

->n{(n+1..n*n).find{|m|g=->g{(1..g).sum{|h|1/h.gcd(g)}};g[m]==g[n]}}

Try it online!

Returns nil if not found.

Answer 9

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):
 n=x
 while n<x*x:
  n+=1
  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!

Answer 10

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.

Answer 11

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

Answer 12

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