One challenge on code golf is to find the shortest possible code to identify whether or not an integer belongs to the binary cyclops numbers which binary expansion is 0, 101, 11011, 1110111, 111101111, &tc. The n-th such number being

a(n) = 2^{2n + 1} - 2^n - 1 = 2\,4^n - 2^n - 1 = (2^n - 1)(2\,2^n + 1)

this leads to the above solution in R (26 bits). The same length as the C solution [which I do not get]


And with shorter versions in many esoteric languages I had never heard of, like the 8 bits Brachylog code


or the 7 bits Jelly


As a side remark, since this was not the purpose of the game, the R code is most inefficient in creating a set of size (x+1), with most terms being Inf.

6 Responses to “(x=scan())%in%(2*4^(n=0:x)-2^n-1)”

  1. […] discovered codegolf on Stack Exchange a few weeks ago, I spotted a few interesting puzzles since then but only got the […]

  2. This is the closest I can get to the logic of the C solution in R. Hoping this survives the forum software:

    cyclops = function(n) {m=bitwXor(n,n+1);n==(m+2)*floor(m/2)}

    If n=(2^k-1)*(2^(k+1)+1), then using the binary representation of integers, a bitwise exclusive OR comparison between n and n+1 gives us m=2^(k+1)-1. So m+2 gives the larger factor and floor(m/2) the smaller one. If we can reconstruct n from its factors then it is a cyclops number.

    You can shave off a few characters, avoiding brackets and the floor function with:

    cyclops = function(n) {m=bitwXor(n,n+1);2*n+2==m*m+m}

    The C code is extremely compact because bit-wise operators are built in (we need the bitwXor function), you can rely on integer arithmetic (R coerces to double), and you can overwrite the input in the middle of an expression (you can’t do this in a functional language).

  3. […] leave a comment for the author, please follow the link and comment on their blog: R – Xi'an's Og. R-bloggers.com offers daily e-mail updates about R news and tutorials on topics such as: Data […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.