14
\$\begingroup\$

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 . Submission with lowest byte-count wins.

References

\$\endgroup\$
  • \$\begingroup\$ also relevant: oeis.org/A264739 \$\endgroup\$ – Destructible Lemon Apr 29 '17 at 6:13
  • 1
    \$\begingroup\$ I offer a bounty to a one-line Retina answer, where the one line is a plain regex (no backticks). \$\endgroup\$ – Leaky Nun Apr 29 '17 at 11:45
  • \$\begingroup\$ @LeakyNun I'm little confused, so far I understand that phi(n) = count { m : 1 <= m <= n AND (m,n) are coprime }.. is that true? \$\endgroup\$ – Khaled.K May 22 '17 at 11:59
  • \$\begingroup\$ @Khaled.K yes, that is true. \$\endgroup\$ – Leaky Nun May 22 '17 at 13:04
6
\$\begingroup\$

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.
\$\endgroup\$
  • \$\begingroup\$ How does it work? \$\endgroup\$ – Leaky Nun Apr 29 '17 at 4:59
  • 1
    \$\begingroup\$ Brute force. There's a lower bound for the totient function, so it's enough to take a large enough range, map totient, and check for occurrences of the input. \$\endgroup\$ – Dennis Apr 29 '17 at 5:02
  • \$\begingroup\$ Can you prove that the square root is the minimum? \$\endgroup\$ – Leaky Nun Apr 29 '17 at 5:59
  • \$\begingroup\$ The square root is actually not a lower bound, but the square root divided by sqrt(2) is. I'm positive that doubling is not required, but a proof will have to wait until I've gotten some sleep. Too tired right now. \$\endgroup\$ – Dennis Apr 29 '17 at 6:05
  • 4
    \$\begingroup\$ @LeakyNun Actually, lemma 3 of this paper proves that the square root is a lower bound unless n = 2k with odd k. Since k and 2k have the same totient, doubling is not required. \$\endgroup\$ – Dennis Apr 29 '17 at 6:09
6
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Conveniently the Fermat primes are all consecutive giving rise to consecutive edge cases n=2, n=8, n=128, n=32768 and n=2147483648. \$\endgroup\$ – Neil Apr 29 '17 at 19:31
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

Pari/GP, 34 bytes

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

Returns 0 if reachable, 1 if not.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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

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);
        }
    }
}
\$\endgroup\$

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.