Definiciones

• Función Euler Phi (AKA totient function ): una función que toma un número positivo y devuelve el número de números positivos menores que el número dado que son primos con el número dado. Se denota como φ(n).

• Número accesible : si existe un número entero positivo xtal que φ(x) == n, entonces nes accesible .

Tarea

Escriba una función / programa para determinar si se puede alcanzar un entero positivo dado.

Entrada

Un número positivo, en cualquier formato razonable. Se puede suponer que el número está dentro de la capacidad del idioma. Se acepta la entrada unaria.

Salida

Dos valores consistentes, uno para números alcanzables y el otro para números inalcanzables. Los dos valores pueden ser cualquier cosa, siempre que sean consistentes.

Casos de prueba

Los números alcanzables a continuación 100son:

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 en OEIS)

Reglas

Se aplican lagunas estándar .

Criterio ganador

Este es el código de golf . Presentación con el menor recuento de bytes gana.

Referencias

• Función Euler Phi
• OEIS A002202

Gelatina , 7 6 bytes

²RÆṪe@

No exactamente rápido. Devuelve 1 o 0 .

Pruébalo en línea!

Cómo funciona

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

Mathematica, 28 bytes

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

Al igual que la respuesta Jelly de Dennis, calculamos los valores φ de todos los números hasta el cuadrado de la entrada y vemos si la entrada aparece allí. Devuelve Falsesi la entrada es accesible y Truesi no lo es. Sí, eso es confuso. Pero FreeQes un byte más corto que MatchQ, y oye, la especificación dice dos valores consistentes> :)

JavaScript (ES6), 90 82 bytes

Devoluciones 0o 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

Esto se basa en el supuesto de que si x existe, entonces x ≤ 2n . Si se demuestra que es falso, se debe actualizar para usar en x=n*nlugar de x=n*2(mismo tamaño, mucho más lento).

Un caso de borde es n = 128 que requiere calcular ϕ (255) .

Manifestación

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

Axioma, 56 bytes

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

no sé si es correcto ... código de prueba y resultados

(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]

El rango 1 .. (2 * x) estaría bien hasta que la entrada x = 500 ...

Pari / GP , 34 bytes

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

Devuelve 0si es accesible, 1si no.

Pruébalo en línea!

05AB1E , 5 bytes

nLÕså

Explicación:

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?

Pruébalo en línea!

05AB1E , 13 12 bytes

EDITAR : se guardó un byte porque la entrada se reutiliza si la pila no tiene suficientes elementos.

Salidas 1 si se puede alcanzar, 0 si no.

Se basa en la suposición de que x ≤ 2n si existe.

xGNÕQi1,q}}0

Pruébalo en línea!

Cómo funciona

              # 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

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

Probar en línea

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