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.

• xnor: I don't know Jelly, but could you perhaps check power of 2 by factoring and checking if the maximum is 2? You can also check if the bitwise AND of it and its predecessor is 0.
• Martin Ender: @xnor Hm, good idea but my attempts at that are the same length. If there's a way to check if a list is of length 1 in less than 3 bytes, it would be shorter though (by using the factorisation function that just gives a list of exponents). I can't find a way to do that though.
• xnor: I see there's E to check if all element of a list are equal. What if you double the number, factor it, and check if all factors are equal?
• Martin Ender: @xnor That's also a nice idea. :) That would probably be 6 bytes then, but Sp3000 pointed out that there's B and Ị which let me test it in 5.
• xnor: Ah, nice. Any chance that decrement, then binary, then product is shorter?

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@#&

• clismique: What are cototients and totients? And are cototient-of-totients and totient-of-totients ratios?
• Martin Ender: @Qwerp-Derp The totient of n is the number of integers below n that are coprime to n, and the cototient is the number of integers below n that aren't. I'll edit in a link.
• Sefa: Mathematica's built-in will never stop to amaze me
• Martin Ender: @Qwerp-Derp As for your second question it just means that you compute the (co)totient of the totient of n.

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♦.

• Sefa: binary input is fine, as well as the assumption about Fermat primes

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.