Constructible n-gon jest regularny wielobok o n bokach, które można budować tylko z kompasem i nieoznakowanym linijki.

Jak stwierdził Gauss, jedynym n, dla którego można zbudować n-gon, jest iloczyn dowolnej liczby odrębnych liczb pierwszych Fermata i potęgi 2 (tj. n = 2^k * p1 * p2 * ...Z kbyciem liczbą całkowitą i każdą pinną wyraźną liczbą pierwszą Fermata).

Liczba pierwsza Fermata jest liczbą pierwszą, którą można wyrazić jako F (n) = 2 ^ (2 ^ n) +1 z liczbą całkowitą dodatnią. Jedyne znane liczby pierwsze Fermata to 0, 1, 2, 3 i 4.

Wyzwanie

Biorąc pod uwagę liczbę całkowitą n>2, powiedz, czy n-gon jest możliwy do zbudowania, czy nie.

Specyfikacja

Twój program lub funkcja powinna przyjąć liczbę całkowitą lub ciąg znaków reprezentujący tę liczbę całkowitą (w postaci jednoargumentowej, binarnej, dziesiętnej lub dowolnej innej podstawie) i zwrócić lub wydrukować wartość prawdy lub fałszu.

To jest golf golfowy, więc wygrywa najkrótsza odpowiedź, obowiązują standardowe luki .

Odpowiedni OEIS

Przykłady

3 -> True
9 -> False
17 -> True
1024 -> True
65537 -> True
67109888 -> True
67109889 -> False

Galaretka , 7 5 bajtów

Dzięki Sp3000 za oszczędność 2 bajtów.

ÆṪBSỊ

Wykorzystuje następującą klasyfikację:

Są to również liczby, dla których phi (n) jest potęgą 2.

Gdzie phi jest funkcją totalną Eulera .

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

Wypróbuj online!

Alternatywnie (kredyty dla 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.

Bezpośredni port mojej odpowiedzi Mathematica jest o dwa bajty dłuższy:

ÆṪ        # Compute φ(n).
  µ       # Start a new monadic chain, to apply to φ(n).
   ÆṪ     # Compute φ(φ(n)).
      H   # Compute φ(n)/2.
     =    # Check for equality.

Mathematica, 24 bajty

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

Wykorzystuje następującą klasyfikację z OEIS:

Obliczalne jako liczby takie, że cototient-of-totient równa się totient-of-totient.

Totient φ(x) liczby całkowitej xjest liczba dodatnich liczb całkowitych poniżej x, które są względnie pierwsze do x. Cototient to liczba dodatnich liczb całkowitych, które nie są, tj x-φ(x). Jeśli suma jest równa kototenowi, oznacza to, że suma z φ(x) == x/2.

Prostsza klasyfikacja

Są to również liczby, dla których phi (n) jest potęgą 2.

kończy się bajtem dłużej:

IntegerQ@Log2@EulerPhi@#&

Siatkówka, 51 50 bajtów

0+$

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

Dane wejściowe są binarne. Pierwsze dwie linie dzielą się przez potęgę dwóch, następne dwie dzielą przez wszystkie znane liczby pierwsze Fermata (jeśli w rzeczywistości liczba jest iloczynem liczb pierwszych Fermata). Edycja: Zapisano 1 bajt dzięki @Martin Ender ♦.

JavaScript (ES7), 61 bajtów

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

Właściwie 6 bajtów

Ta odpowiedź jest oparta na algorytmie xnora w odpowiedzi Jelly Martina Endera . Sugestie dotyczące gry w golfa mile widziane. Wypróbuj online!

▒D├♂≈π

Jak to działa

         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.

Partia, 97 bajtów

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

Wejście jest ustawione na standardowe w systemie dziesiętnym. Jest to w rzeczywistości 1 bajt krótszy niż iteracyjne obliczanie mocy potęg 2. Zapisałem 1 bajt, używając @ xnor potęgi 2 czeków.