N-gons constructibles

10

Un n-gon constructible est un polygone régulier à n côtés que vous pouvez construire avec uniquement une boussole et une règle non marquée.

Comme indiqué par Gauss, le seul pour lequel n a n-gon est constructible est un produit d'un nombre quelconque de nombres premiers de Fermat distincts et une puissance de 2 (ie. n = 2^k * p1 * p2 * ...En kétant un nombre entier et chaque pcertaine perfection de Fermat distincts).

Un nombre premier de Fermat est un nombre premier qui peut être exprimé comme F (n) = 2 ^ (2 ^ n) +1 avec un entier positif. Les seuls nombres premiers de Fermat connus sont pour 0, 1, 2, 3 et 4.

Le défi

Étant donné un entier n>2, dites si le n-gon est constructible ou non.

spécification

Votre programme ou fonction doit prendre un entier ou une chaîne représentant ledit entier (soit en unaire, binaire, décimal ou toute autre base) et retourner ou imprimer une valeur véridique ou fausse.

Il s'agit de code-golf, donc la réponse la plus courte l'emporte, les échappatoires standard s'appliquent.

OEIS pertinent

Exemples

3 -> True
9 -> False
17 -> True
1024 -> True
65537 -> True
67109888 -> True
67109889 -> False
code-golf Sefa
la source

Réponses:

8

Gelée , 7 5 octets

Merci à Sp3000 pour avoir économisé 2 octets.

ÆṪBSỊ

Utilise la classification suivante:

Ce sont aussi les nombres pour lesquels phi (n) est une puissance de 2.

Où phi est la fonction de totient d'Euler .

ÆṪ        # Compute φ(n).
  B       # Convert to binary.
   S      # Sum bits.
    Ị     # Check whether it's less than or equal to 1. This can only be the
          # case if the binary representation was of the form [1 0 0 ... 0], i.e. 
          e# a power of 2.

Essayez-le en ligne!

Alternativement (crédits à xnor):

ÆṪ’BP
ÆṪ        # Compute φ(n).
  ’       # Decrement.
   B      # Convert to binary.
    P     # Product. This is 1 iff all bits in the binary representation are
          # 1, which means that φ(n) is a power of 2.

Un port direct de ma réponse Mathematica est plus long de deux octets:

ÆṪ        # Compute φ(n).
  µ       # Start a new monadic chain, to apply to φ(n).
   ÆṪ     # Compute φ(φ(n)).
      H   # Compute φ(n)/2.
     =    # Check for equality.
Martin Ender
la source
Je ne connais pas Jelly, mais pourriez-vous peut-être vérifier la puissance de 2 en factorisant et en vérifiant si le maximum est 2? Vous pouvez également vérifier si le ET au niveau du bit de celui-ci et de son prédécesseur est 0.
xnor
@xnor Hm, bonne idée mais mes tentatives sont de la même longueur. S'il existe un moyen de vérifier si une liste est de longueur 1 en moins de 3 octets, elle serait cependant plus courte (en utilisant la fonction de factorisation qui donne juste une liste d'exposants). Mais je ne trouve pas de moyen de le faire.
Martin Ender
Je vois qu'il y a E pour vérifier si tous les éléments d'une liste sont égaux. Que faire si vous doublez le nombre, le factorisez et vérifiez si tous les facteurs sont égaux?
xnor
@xnor C'est aussi une bonne idée. :) Ce serait probablement 6 octets alors, mais Sp3000 a souligné qu'il y en avait Bet Ịqui m'a permis de le tester en 5.
Martin Ender
Ah, bien. Toute chance que décrémenter, puis binaire, puis le produit est plus court?
xnor
3

Mathematica, 24 octets

e=EulerPhi
e@e@#==e@#/2&

Utilise la classification suivante d'OEIS:

Calculable sous forme de nombres tels que cototient-de-totient est égal au totient-de-totient.

Le total φ(x) d'un entier xest le nombre d'entiers positifs en dessous xqui sont coprimes x. Le cototient est le nombre d'entiers positifs qui ne le sont pas, c'est-à-dire x-φ(x). Si le totient est égal au cototient, cela signifie que le totient de φ(x) == x/2.

La classification la plus simple

Ce sont aussi les nombres pour lesquels phi (n) est une puissance de 2.

finit par être un octet de plus:

IntegerQ@Log2@EulerPhi@#&
Martin Ender
la source
Que sont les cototients et les totients? Et les rapports cototient-de-totients et totient-de-totients?
clismique
@ Qwerp-Derp Le total de nest le nombre d'entiers ci n- dessous qui sont coprime to n, et le cototient est le nombre d'entiers ci n- dessous qui ne le sont pas. Je vais éditer dans un lien.
Martin Ender
L'intégration de Mathematica ne cessera jamais de m'étonner
Sefa
@ Qwerp-Derp Quant à votre deuxième question, cela signifie simplement que vous calculez le (co) totient du totient de n.
Martin Ender
3

Rétine, 51 50 octets

0+$

+`^(.*)(?=(.{16}|.{8}|....|..?)$)0*\1$
$1
^1$

L'entrée est en binaire. Les deux premières lignes se divisent par une puissance de deux, les deux suivantes se divisent par tous les nombres premiers de Fermat connus (si en fait le nombre est un produit des nombres premiers de Fermat). Edit: 1 octet enregistré grâce à @Martin Ender ♦.

Neil
la source
l'entrée binaire est très bien, ainsi que l'hypothèse sur les nombres premiers de Fermat
Sefa
2

JavaScript (ES7), 61 octets

n=>[...Array(5)].map((_,i)=>n%(i=2**2**i+1)?0:n/=i)&&!(n&n-1)
Neil
la source
1

En fait, 6 octets

Cette réponse est basée sur l'algorithme de xnor dans la réponse Jelly de Martin Ender . Suggestions de golf bienvenues. Essayez-le en ligne!

▒D├♂≈π

Comment ça fonctionne

         Implicit input n.
▒        totient(n)
 D       Decrement.
  ├      Convert to binary (as string).
   ♂≈    Convert each char into an int.
     π   Take the product of those binary digits.
         If the result is 1,
           then bin(totient(n) - 1) is a string of 1s, and totient(n) is power of two.
Sherlock9
la source
0

Lot, 97 octets

@set/pn=
@for /l %%a in (4,-1,0)do @set/a"p=1<<(1<<%%a),n/=p*!(n%%-~p)+1"
@cmd/cset/a"!(n-1&n)"

L'entrée est sur stdin en décimal. Ceci est en fait 1 octet plus court que le calcul itératif des puissances des puissances de 2. J'ai économisé 1 octet en utilisant la puissance de @ xnor de 2 chèques.

Neil
la source