Constructible n-gons

Question

A constructible \$n\$-gon is a regular polygon with n sides that you can construct with only a compass and an unmarked ruler.

As stated by Gauss, the only \$n\$ for which a \$n\$-gon is constructible is a product of any number of distinct Fermat primes and a power of \$2\$ (ie. \$n = 2^k \times p_1 \times p_2 \times ...\$ with \$k\$ being an integer and every \$p_i\$ some distinct Fermat prime).

A Fermat prime is a prime which can be expressed as \$2^{2^n}+1\$ with \$n\$ a positive integer. The only known Fermat primes are for \$n = 0, 1, 2, 3 \text{ and } 4\$

The challenge

Given an integer \$n>2\$, say if the \$n\$-gon is constructible or not.

Specification

Your program or function should take an integer or a string representing said integer (either in unary, binary, decimal or any other base) and return or print a truthy or falsy value.

This is code-golf, so shortest answer wins, standard loopholes apply.

Relevant OEIS

Examples

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

Answer 1

Jelly, 7 5 bytes

Thanks to Sp3000 for saving 2 bytes.

ÆṪBSỊ

Uses the following classification:

These are also the numbers for which phi(n) is a power of 2.

Where phi is Euler's totient function.

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

Try it online!

Alternatively (credits to 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.

A direct port of my Mathematica answer is two bytes longer:

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

Answer 2

Mathematica, 24 bytes

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

Uses the following classification from OEIS:

Computable as numbers such that cototient-of-totient equals the totient-of-totient.

The totient φ(x) of an integer x is the number of positive integers below x that are coprime to x. The cototient is the number of positive integers that aren't, i.e. x-φ(x). If the totient is equal to the cototient, that means that the totient of φ(x) == x/2.

The more straightforward classification

These are also the numbers for which phi(n) is a power of 2.

ends up being a byte longer:

IntegerQ@Log2@EulerPhi@#&

Answer 3

Retina, 51 50 bytes

0+$

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

Input is in binary. The first two lines divide by a power of two, the next two divide by all known Fermat primes (if in fact the number is a product of Fermat primes). Edit: Saved 1 byte thanks to @Martin Ender♦.

Answer 4

JavaScript (ES7), 61 bytes

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

Answer 5

Actually, 6 bytes

This answer is based on xnor's algorithm in Martin Ender's Jelly answer. Golfing suggestions welcome. Try it online!

▒D├♂≈π

How it works

         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.

Answer 6

Batch, 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)"

Input is on stdin in decimal. This is actually 1 byte shorter than calculating the powers of powers of 2 iteratively. I saved 1 byte by using @xnor's power of 2 check.