10
\$\begingroup\$

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
\$\endgroup\$
8
\$\begingroup\$

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

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

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

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

JavaScript (ES7), 61 bytes

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

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.
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.