Konstruierbare n-Gons

10

Ein konstruierbares n-Gon ist ein reguläres Polygon mit n Seiten, das Sie nur mit einem Kompass und einem nicht markierten Lineal konstruieren können.

Wie von Gauß angegeben, ist das einzige n, für das ein n-Gon konstruierbar ist, ein Produkt einer beliebigen Anzahl unterschiedlicher Fermat-Primzahlen und einer Potenz von 2 (dh n = 2^k * p1 * p2 * ...mit keiner ganzen Zahl und jeder pbestimmten Fermat-Primzahl).

Eine Fermat-Primzahl ist eine Primzahl, die als F (n) = 2 ^ (2 ^ n) +1 mit einer positiven ganzen Zahl ausgedrückt werden kann. Die einzigen bekannten Fermat-Primzahlen sind für 0, 1, 2, 3 und 4.

Die Herausforderung

n>2Sagen Sie bei einer gegebenen Ganzzahl , ob das n-Gon konstruierbar ist oder nicht.

Spezifikation

Ihr Programm oder Ihre Funktion sollte eine Ganzzahl oder eine Zeichenfolge verwenden, die diese Ganzzahl darstellt (entweder in unärer, binärer, dezimaler oder einer anderen Basis) und einen wahrheitsgemäßen oder falschen Wert zurückgeben oder drucken.

Dies ist Code-Golf, also gewinnt die kürzeste Antwort, es gelten Standard-Lücken .

Relevante OEIS

Beispiele

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

Antworten:

8

Gelee , 7 5 Bytes

Vielen Dank an Sp3000 für das Speichern von 2 Bytes.

ÆṪBSỊ

Verwendet die folgende Klassifizierung:

Dies sind auch die Zahlen, für die phi (n) eine Potenz von 2 ist.

Wo phi ist Eulersche Phi-Funktion .

ÆṪ        # 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.

Probieren Sie es online aus!

Alternativ (Credits an 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.

Ein direkter Port meiner Mathematica-Antwort ist zwei Bytes länger:

ÆṪ        # Compute φ(n).
  µ       # Start a new monadic chain, to apply to φ(n).
   ÆṪ     # Compute φ(φ(n)).
      H   # Compute φ(n)/2.
     =    # Check for equality.
Martin Ender
quelle
Ich kenne Jelly nicht, aber könnten Sie vielleicht die Potenz von 2 überprüfen, indem Sie berücksichtigen und prüfen, ob das Maximum 2 ist? Sie können auch überprüfen, ob das bitweise UND von ihm und seinem Vorgänger 0 ist.
xnor
@xnor Hm, gute Idee, aber meine Versuche dazu sind gleich lang. Wenn es eine Möglichkeit gibt, zu überprüfen, ob eine Liste in weniger als 3 Bytes die Länge 1 hat, ist sie jedoch kürzer (mithilfe der Faktorisierungsfunktion, die nur eine Liste von Exponenten enthält). Ich kann aber keinen Weg finden, das zu tun.
Martin Ender
Ich sehe, dass es E gibt, um zu überprüfen, ob alle Elemente einer Liste gleich sind. Was ist, wenn Sie die Zahl verdoppeln, faktorisieren und prüfen, ob alle Faktoren gleich sind?
xnor
@xnor Das ist auch eine schöne Idee. :) Das wären dann wahrscheinlich 6 Bytes, aber Sp3000 hat darauf hingewiesen, dass es welche gibt Bund Ịich sie in 5 testen kann.
Martin Ender
Ah schön. Gibt es eine Chance, dass Dekrement, dann Binär, dann Produkt kürzer ist?
xnor
3

Mathematica, 24 Bytes

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

Verwendet die folgende Klassifizierung von OEIS:

Berechenbar als Zahlen, so dass der Totient des Totienten dem Totienten des Totienten entspricht.

Der Totient φ(x) einer Ganzzahl xist die Anzahl der positiven Ganzzahlen darunter x, auf die koprime ist x. Der Cototient ist die Anzahl der positiven ganzen Zahlen, die es nicht sind, dh x-φ(x). Wenn der Totient gleich dem Cototienten ist, bedeutet dies, dass der Totient von φ(x) == x/2.

Die einfachere Klassifizierung

Dies sind auch die Zahlen, für die phi (n) eine Potenz von 2 ist.

endet ein Byte länger:

IntegerQ@Log2@EulerPhi@#&
Martin Ender
quelle
Was sind Cototienten und Totienten? Und sind Cototient-of-Totients- und Totient-of-Totients-Verhältnisse?
Clismique
@ Qwerp-Derp Der Totient von nist die Anzahl der Ganzzahlen darunter n, zu denen nCoprime ist, und der Cototient ist die Anzahl der Ganzzahlen darunter n, die nicht gleich sind. Ich werde in einem Link bearbeiten.
Martin Ender
Mathematicas eingebaute wird nie aufhören, mich zu überraschen
Sefa
@ Qwerp-Derp Was Ihre zweite Frage betrifft, bedeutet dies nur, dass Sie den (Co-) Totienten des Totienten von berechnen n.
Martin Ender
3

Netzhaut, 51 50 Bytes

0+$

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

Die Eingabe erfolgt binär. Die ersten beiden Zeilen teilen sich durch eine Zweierpotenz, die nächsten beiden teilen sich durch alle bekannten Fermat-Primzahlen (wenn die Zahl tatsächlich ein Produkt von Fermat-Primzahlen ist). Bearbeiten: 1 Byte dank @Martin Ender gespeichert ♦.

Neil
quelle
Binäreingabe ist in Ordnung, ebenso wie die Annahme über Fermat-Primzahlen
Sefa
2

JavaScript (ES7), 61 Byte

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

Eigentlich 6 Bytes

Diese Antwort basiert auf dem xnor-Algorithmus in Martin Enders Jelly-Antwort . Golfvorschläge willkommen. Probieren Sie es online aus!

▒D├♂≈π

Wie es funktioniert

         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
quelle
0

Stapel, 97 Bytes

@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)"

Die Eingabe erfolgt stdin in Dezimalzahl. Dies ist tatsächlich 1 Byte kürzer als die iterative Berechnung der Potenzen von 2. Ich habe 1 Byte gespart, indem ich @ xnors 2-Potenz-Check verwendet habe.

Neil
quelle