Reachable numbers

Question

Definitions

• Euler Phi Function (AKA totient function): a function which takes in a positive number and returns the number of positive numbers less than the given number which are co-prime with given number. It is denoted as φ(n).

• Reachable number: if there exists a positive integer x such that φ(x) == n, then n is reachable.

Task

Write a function/program to determine if a given positive integer is reachable.

Input

A positive number, in any reasonable format. One can assume that the number is within the capability of the language. Unary input is accepted.

Output

Two consistent values, one for reachable numbers, and the other for unreachable numbers. The two values can be anything, as long as they are consistent.

Testcases

The reachable numbers bellow 100 are:

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46, 48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96

(A002202 on OEIS)

Rules

Standard loopholes apply.

Winning criterion

This is code-golf. Submission with lowest byte-count wins.

References

• Euler Phi Function
• OEIS A002202

Answer 1

Jelly, 7 6 bytes

²RÆṪe@

Not exactly fast. Returns 1 or 0.

Try it online!

How it works

²RÆṪe@  Main link. Argument: n

²       Square; yield n².
 R      Range; yield [1, ..., n²].
  ÆṪ    Compute the totient of each integer in the range.
    e@  Exists swap; test if n occurs in the generated array.

Answer 2

Mathematica, 28 bytes

EulerPhi@Range[#^2]~FreeQ~#&

Like Dennis's Jelly answer, we compute the φ-values of all the numbers up to the square of the input and see if the input appears therein. Returns False if the input is reachable and True if it's not. Yep, that's confusing. But FreeQ is a byte shorter than MatchQ, and hey, the spec said any two consistent values >:)

Answer 3

JavaScript (ES6), 90 82 bytes

Returns 0 or true.

f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0

This is based on the assumption that if x exists then x ≤ 2n. If proven false, this should be updated to use x=n*n instead of x=n*2 (same size, much slower).

An edge case is n = 128 which requires to compute ϕ(255).

Demo

f=(n,x=n*2)=>x?(p=i=>(c=(a,b)=>a?c(b%a,a):b<2)(i,x)+(i&&p(--i)))(x)==n||f(n,x-1):0

for(n = 1; n <= 50; n++) {
  console.log(n, f(n));
}

Answer 4

Axiom, 56 bytes

f(x:PI):Boolean==member?(x,[eulerPhi(i)for i in 1..2*x])

i don't know if it is right...test code and results

(35) -> [i  for i in 1..100|f(i)]
   (35)
   [1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 22, 24, 28, 30, 32, 36, 40, 42, 44, 46,
    48, 52, 54, 56, 58, 60, 64, 66, 70, 72, 78, 80, 82, 84, 88, 92, 96, 100]

The range 1..(2*x) would be ok until input x=500...

Answer 5

05AB1E, 5 bytes

nLÕså

Explanation:

n       Square [implicit] input
 L      Range [1 .. a]
  Õ     Euler totient
   s    Put first input at the top of the stack
    å   Is it in the list?

Try it online!

Answer 6

Pari/GP, 34 bytes

x->![n|n<-[1..x^2],eulerphi(n)==x]

Returns 0 if reachable, 1 if not.

Try it online!

Answer 7

05AB1E, 13 12 bytes

EDIT: Saved a byte because input is reused if the stack doesn't have enough elements.

Outputs 1 if reachable, 0 if not.

Relies on assumption that x ≤ 2n if it exists.

xGNÕQi1,q}}0

Try it online!

How it works

              # implicit input    
x            # push input, 2 * input
 G           # for N in 1..2*input
             # implicit push input
  N          # push N
   Õ         # push totient of N
    Q        # check if both are equal
     i.      # if equal
      1,     # print 1
        q    # quit program
         }   # end if
          }  # end for
           0 # push 0 if condition never reached
             # implicit print

Answer 8

C, 123 bytes

g(a,b){return!a?b:g(b%a,a);}
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

Try Online

#include <stdio.h>

// gcd function
g(a,b){return!a?b:g(b%a,a);}

// Euler phi(x) function
i;r;f(n){for(i=2,r=1;i<n;i++)r+=(g(i,n)==1);}

// check if m is reachable, phi(x) for x in (m , m^2]
t;k;s(m){for(k=m,t=0;!t&(k<m*m);)f(++k),t=(r==m);}

main()
{
    // print all reachable number below 50
    for(int x=1; x<50; x++)
    {
        s(x);

        if(t)
        {
            printf(" %d ~ phi(%d) \n", x, k);
        }
    }
}