Конструктивен п-угольник является правильным многоугольником с п сторон , которые можно построить только с компасом и без опознавательных знаков линейки.

Как заявлено Гаусс, единственный п , для которых п-угольник построимо является продуктом любого числа различных простых чисел Ферма и мощностью 2 (то есть. n = 2^k * p1 * p2 * ...С kпредставляет собой целое число и каждый pнекоторое отличие Ферма Prime).

Простое число Ферма - это простое число, которое может быть выражено как F (n) = 2 ^ (2 ^ n) +1 с положительным целым числом. Единственное известное простое число Ферма для 0, 1, 2, 3 и 4.

Соревнование

Учитывая целое число n>2, скажите, если n-гон конструктивен или нет.

Спецификация

Ваша программа или функция должны взять целое число или строку, представляющую указанное целое число (в унарной, двоичной, десятичной или любой другой базе), и вернуть или вывести истинное или ложное значение.

Это код-гольф, поэтому самый короткий ответ выигрывает, применяются стандартные лазейки .

Соответствующий OEIS

Примеры

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

Желе , 7 5 байт

Спасибо Sp3000 за сохранение 2 байта.

ÆṪBSỊ

Использует следующую классификацию:

Это также числа, для которых фи (п) является степенью 2.

Где фи - это функция Эйлера .

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

Попробуйте онлайн!

В качестве альтернативы (кредиты для 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.

Прямой порт моего ответа Mathematica на два байта длиннее:

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

Mathematica, 24 байта

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

Использует следующую классификацию от OEIS:

Вычисляется как число, такое, что совокупный коэффициент равен суммарному коэффициенту.

Totient φ(x) целого числа xесть число положительных целых чисел ниже , xкоторые взаимно просто с x. Cototient является числом положительных целых чисел, которые не являются, то есть x-φ(x). Если totient равен cototient, это означает, что totient of φ(x) == x/2.

Более простая классификация

Это также числа, для которых фи (п) является степенью 2.

заканчивает тем, что был байтом длиннее:

IntegerQ@Log2@EulerPhi@#&

Сетчатка, 51 50 байт

0+$

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

Ввод в двоичном виде. Первые две строки делятся на степени двух, следующие две делятся на все известные простые числа Ферма (если на самом деле число является произведением простых чисел Ферма). Редактировать: 1 байт сохранен благодаря @Martin Ender ♦.

JavaScript (ES7), 61 байт

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

На самом деле, 6 байтов

Этот ответ основан на алгоритме xnor в ответе Jelly Мартина Эндера . Предложения по игре в гольф приветствуются. Попробуйте онлайн!

▒D├♂≈π

Как это работает

         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.

Пакет, 97 байт

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

Ввод в стандартном формате в десятичном виде. На самом деле это на 1 байт меньше, чем итеративный расчет степеней степеней 2. Я сохранил 1 байт, используя @ xnor power 2 check.