Skip to main content
We’ve updated our Terms of Service. A new AI Addendum clarifies how Stack Overflow utilizes AI interactions.
Code Golf

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Required fields*

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 \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*

Draft saved
Draft discarded
Cancel
6
  • \$\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\$ Commented Sep 5, 2016 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\$ Commented Sep 5, 2016 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\$ Commented Sep 5, 2016 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\$ Commented Sep 5, 2016 at 9:00
  • \$\begingroup\$ Ah, nice. Any chance that decrement, then binary, then product is shorter? \$\endgroup\$ Commented Sep 5, 2016 at 9:01

AltStyle によって変換されたページ (->オリジナル) /