Définitions

• Fonction Euler Phi ( fonction AKA totient ): une fonction qui prend un nombre positif et renvoie le nombre de nombres positifs inférieur au nombre donné qui sont co-premiers avec un nombre donné. Il est désigné par φ(n).

• Numéro accessible : s'il existe un entier positif xtel que φ(x) == n, alors il nest accessible .

Tâche

Écrivez une fonction / un programme pour déterminer si un entier positif donné est accessible.

Contribution

Un nombre positif, dans n'importe quel format raisonnable. On peut supposer que le nombre est à la portée de la langue. Une entrée unaire est acceptée.

Production

Deux valeurs cohérentes, l'une pour les numéros accessibles et l'autre pour les numéros inaccessibles. Les deux valeurs peuvent être n'importe quoi, tant qu'elles sont cohérentes.

Cas de test

Les numéros accessibles ci 100- dessous sont:

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

Règles

Des échappatoires standard s'appliquent.

Critère gagnant

C'est du code-golf . Soumission avec le plus petit nombre de victoires d'octets.

Les références

• Fonction Euler Phi
• OEIS A002202

Gelée , 7 6 octets

²RÆṪe@

Pas vraiment rapide. Renvoie 1 ou 0 .

Essayez-le en ligne!

Comment ça fonctionne

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

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

Comme la réponse Jelly de Dennis, nous calculons les valeurs φ de tous les nombres jusqu'au carré de l'entrée et voyons si l'entrée y apparaît. Renvoie Falsesi l'entrée est accessible et Truesi ce n'est pas le cas. Oui, c'est déroutant. Mais FreeQest un octet plus court que MatchQ, et bon, la spécification dit deux valeurs cohérentes> :)

JavaScript (ES6), 90 82 octets

Renvoie 0ou 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

Ceci est basé sur l'hypothèse que si x existe alors x ≤ 2n . S'il s'avère faux, cela devrait être mis à jour pour utiliser à la x=n*nplace de x=n*2(même taille, beaucoup plus lent).

Un cas de bord est n = 128 qui nécessite de calculer ϕ (255) .

Démo

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

Axiome, 56 octets

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

je ne sais pas si c'est bien ... code de test et résultats

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

La plage 1 .. (2 * x) serait correcte jusqu'à ce que l'entrée x = 500 ...

Pari / GP , 34 octets

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

Retour 0 si accessible, 1sinon.

Essayez-le en ligne!

05AB1E , 5 octets

nLÕså

Explication:

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?

Essayez-le en ligne!

05AB1E , 13 12 octets

ÉDITER : enregistré un octet car l'entrée est réutilisée si la pile n'a pas assez d'éléments.

Sorties 1 si joignable, 0 sinon.

Repose sur l'hypothèse que x ≤ 2n s'il existe.

xGNÕQi1,q}}0

Essayez-le en ligne!

Comment ça fonctionne

              # 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 octets

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

Essayez en ligne

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