15
\$\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\$
4
  • \$\begingroup\$ also relevant: oeis.org/A264739 \$\endgroup\$ Apr 29, 2017 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, 2017 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, 2017 at 11:59
  • \$\begingroup\$ @Khaled.K yes, that is true. \$\endgroup\$
    – Leaky Nun
    May 22, 2017 at 13:04

10 Answers 10

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\$
10
  • \$\begingroup\$ How does it work? \$\endgroup\$
    – Leaky Nun
    Apr 29, 2017 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, 2017 at 5:02
  • \$\begingroup\$ Can you prove that the square root is the minimum? \$\endgroup\$
    – Leaky Nun
    Apr 29, 2017 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, 2017 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, 2017 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\$
1
  • \$\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, 2017 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\$
1
0
\$\begingroup\$

Whispers v2, 63 bytes

> Input
>> 1²
>> [2]
>> φ(L)
>> Each 4 3
>> 1∈5
>> Output 6

Try it online!

Works by brute force. We square the input, then generate the range [1, 2, ..., x²]. Next we calculate \$\phi(i)\$ for each \$i\$ in this range. Finally, we check if the original input \$x\$ is in the array of \$\phi(i)\$ values.

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

Stax, 6 bytes

┬$τ▀Ω♀

Run and debug it

I'm not sure why 3 golflangs have an Euler Totient function, but I guess it's convenient for these challenges.

0 for reachable and 1 for non-reachable.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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