# 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 Commented Dec 4, 2019 at 20:27
• M for 8 is 10 - both have phi(x) = 4 Commented Dec 4, 2019 at 20:49
• @NickKennedy thanks, missed that Commented Dec 4, 2019 at 20:53
• Is it permissible to return the input where there is no M? Commented Dec 4, 2019 at 21:13
• This is A066659. Commented Dec 5, 2019 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)
$- 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)  • Thanks guys. @Mr.Xcoder More 12s I got along the way: ²ÆṪ€ẹị@¥>Ƈ⁸Ḣ and ²ÆṪ€=ÆṪT>Ƈ⁸Ḣ Commented Dec 4, 2019 at 22:50 • @Mr.Xcoder Oh, but TIO Commented Dec 4, 2019 at 22:52 • Sighs. Just when I thought I found a 9. 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. ### 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)


# 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 Commented Dec 5, 2019 at 12:14
• @ExpiredData Ah, nice! I had something similar at first, except that I had 1è instead of ¦¬. You can remove the s by using ¬QÏ instead. :) Thanks, this is now the 9-byter: nŸDÕ¬QÏ¦н Commented Dec 5, 2019 at 14:25
• .Δ conveniently defaults to -1 when no result is found, saving one byte: nŸ¦.Δ‚ÕË. Commented Dec 5, 2019 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. Commented Dec 5, 2019 at 15:32
• @Grimmy Oh, very nice! And nicely spotted of the $<2n$ in the Mathematica implementation of the oeis sequence! :) Commented Dec 5, 2019 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!

Returns nil if not found.

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