25
\$\begingroup\$

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

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

12 Answers 12

10
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
8
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks guys. @Mr.Xcoder More 12s I got along the way: ²ÆṪ€ẹị@¥>Ƈ⁸Ḣ and ²ÆṪ€=ÆṪT>Ƈ⁸Ḣ \$\endgroup\$ – Jonathan Allan Dec 4 '19 at 22:50
  • \$\begingroup\$ @Mr.Xcoder Oh, but TIO \$\endgroup\$ – Jonathan Allan Dec 4 '19 at 22:52
  • \$\begingroup\$ Sighs. Just when I thought I found a 9. \$\endgroup\$ – Mr. Xcoder Dec 4 '19 at 22:54
7
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
5
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • 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\$ – Expired Data Dec 5 '19 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\$ – Kevin Cruijssen Dec 5 '19 at 14:25
  • 1
    \$\begingroup\$ conveniently defaults to -1 when no result is found, saving one byte: nŸ¦.Δ‚ÕË. \$\endgroup\$ – Grimmy Dec 5 '19 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 Dec 5 '19 at 15:32
  • \$\begingroup\$ @Grimmy Oh, very nice! And nicely spotted of the \$<2n\$ in the Mathematica implementation of the oeis sequence! :) \$\endgroup\$ – Kevin Cruijssen Dec 5 '19 at 19:47
4
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Downvoted because... ? \$\endgroup\$ – G B Dec 6 '19 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 Feb 12 at 16:39
  • \$\begingroup\$ @JPeroutek done \$\endgroup\$ – G B Feb 20 at 15:10
  • \$\begingroup\$ @G B fixed! sorry about that! \$\endgroup\$ – JPeroutek Feb 20 at 15:42
1
\$\begingroup\$

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!

| improve this answer | |
\$\endgroup\$
1
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 19 bytes \$\endgroup\$ – Shaggy Dec 9 '19 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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