Next Shared Totient

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

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

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

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

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

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)

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)

05AB1E, 11109 7 bytes

L+.Δ‚ÕË

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

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

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.

• Maybe this 10 bytes is easier to work with? It feels like I'm missing an obvious way to remove a byte – Expired Data Dec 5 '19 at 12:14
• @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Ï¦н – Kevin Cruijssen Dec 5 '19 at 14:25
• conveniently defaults to -1 when no result is found, saving one byte: nŸ¦.Δ‚ÕË. – Grimmy Dec 5 '19 at 15:28
• 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. – Grimmy Dec 5 '19 at 15:32
• @Grimmy Oh, very nice! And nicely spotted of the $<2n$ in the Mathematica implementation of the oeis sequence! :) – Kevin Cruijssen Dec 5 '19 at 19:47

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

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

Try it online!

• Downvoted because... ? – G B Dec 6 '19 at 6:49
• 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! – JPeroutek Feb 12 '20 at 16:39
• @JPeroutek done – G B Feb 20 '20 at 15:10
• @G B fixed! sorry about that! – JPeroutek Feb 20 '20 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):
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!

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

• 19 bytes – Shaggy Dec 9 '19 at 9:12