Constructible n-gons
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.
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@#&
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♦.