# Constructible n-gons

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 * p1 * p2 * ... with k being an integer and every p some distinct Fermat prime).

A Fermat prime is a prime which can be expressed as F(n)=2^(2^n)+1 whith n a positive integer. The only known Fermat prime are for 0, 1, 2, 3 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


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

• 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. – xnor Sep 5 '16 at 8:41
• @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. – Martin Ender Sep 5 '16 at 8:51
• 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? – xnor Sep 5 '16 at 8:55
• @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. – Martin Ender Sep 5 '16 at 9:00
• Ah, nice. Any chance that decrement, then binary, then product is shorter? – xnor Sep 5 '16 at 9:01

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

• What are cototients and totients? And are cototient-of-totients and totient-of-totients ratios? – clismique Sep 5 '16 at 8:14
• @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. – Martin Ender Sep 5 '16 at 8:15
• Mathematica's built-in will never stop to amaze me – Sefa Sep 5 '16 at 8:21
• @Qwerp-Derp As for your second question it just means that you compute the (co)totient of the totient of n. – Martin Ender Sep 5 '16 at 8:31

## Retina, 51 50 bytes

0+$+^(.*)(?=(.{16}|.{8}|....|..?)$)0*\11
^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♦.

• binary input is fine, as well as the assumption about Fermat primes – Sefa Sep 5 '16 at 9:17

## JavaScript (ES7), 61 bytes

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


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


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