19
\$\begingroup\$

In this challenge you will compute numbers from a curious sequence.

Your input is a single decimal nonnegative integer. Reverse the bits in this integer and then square the number to get the required output.

When reversing the bits you must not use any leading zeroes in the input. For example:

26 (base 10) = 11010 (base 2) -> 01011 (base 2) = 11 -> 11*11 = 121

The first 25 inputs/outputs of this sequence:

0: 0
1: 1
2: 1
3: 9
4: 1
5: 25
6: 9
7: 49
8: 1
9: 81
10: 25
11: 169
12: 9
13: 121
14: 49
15: 225
16: 1
17: 289
18: 81
19: 625
20: 25
21: 441
22: 169
23: 841
24: 9

Your solution should work for arbitrarily sized integers. If your language does not have a convenient built-in method of using those, implement your answer as if it does. You are then excused if your answer breaks for large numbers. However, do not use tricks/bounds that only work for a limited domain (such as a lookup table).


Your score is the number of bytes of source code.

-50% bonus if you never convert the number to/from binary. This is not limited to builtins, if you loop over the number bit by bit (either by shifting or masking or any other method), it will also count as conversion. I don't know whether this is actually possible, but it gives an incentive to spot a pattern in the sequence.

Smallest score wins.

\$\endgroup\$
  • 6
    \$\begingroup\$ So close \$\endgroup\$ – Conor O'Brien Nov 29 '15 at 18:54
  • 1
    \$\begingroup\$ If the code calls a method that results in a character string that represents the bits, is that eligible for the bonus? \$\endgroup\$ – Brad Gilbert b2gills Nov 29 '15 at 19:35
  • 2
    \$\begingroup\$ @BradGilbertb2gills No. \$\endgroup\$ – orlp Nov 29 '15 at 19:39
  • \$\begingroup\$ I presume that using math to extract the bits also counts as binary conversion? \$\endgroup\$ – lirtosiast Nov 29 '15 at 20:23
  • 2
    \$\begingroup\$ Relevant and relevant \$\endgroup\$ – Mego Nov 29 '15 at 23:47

19 Answers 19

5
\$\begingroup\$

Par, 5 bytes

✶Σ⌐Σ²

That's read-binary-reverse-binary-square.

\$\endgroup\$
  • \$\begingroup\$ I count 12 \$\endgroup\$ – Conor O'Brien Dec 4 '15 at 3:52
  • \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ That byte counter assumes UTF-8. I believe Mauris is using some encoding that is not UTF-8 to count his bytes, but he did not specify this encoding. \$\endgroup\$ – orlp Dec 4 '15 at 9:16
  • \$\begingroup\$ Par uses its own weird encoding. Its canonical representation is a certain subset of <256 Unicode characters. I'm not sure if it has a name; I should wait for @Ypnypn to chime in. \$\endgroup\$ – Lynn Dec 4 '15 at 9:51
  • \$\begingroup\$ Oh, I see. @orlp \$\endgroup\$ – Conor O'Brien Dec 4 '15 at 12:10
  • \$\begingroup\$ Possibly it has its own SBCS? \$\endgroup\$ – HyperNeutrino Apr 1 '17 at 21:38
19
\$\begingroup\$

Mathematica, 42 21 bytes

Thanks to alephalpha for halving the score.

#~IntegerReverse~2^2&

The actual reason I did this in Mathematica was because I wanted to look at a plot... it sure looks funny:

enter image description here

\$\endgroup\$
  • 11
    \$\begingroup\$ But I like the score! XD \$\endgroup\$ – Conor O'Brien Nov 29 '15 at 18:57
  • 1
    \$\begingroup\$ why does this answer have more votes than the answer with the least bytes? o_O \$\endgroup\$ – Seadrus Nov 29 '15 at 19:56
  • 27
    \$\begingroup\$ @Seadrus You know what they say. A picture is worth 7 bytes. \$\endgroup\$ – Martin Ender Nov 29 '15 at 20:03
  • 5
    \$\begingroup\$ so your score is 42 + 7 = 49 bytes :P \$\endgroup\$ – Seadrus Nov 29 '15 at 23:20
  • 3
    \$\begingroup\$ Sorry, @CᴏɴᴏʀO'Bʀɪᴇɴ. \$\endgroup\$ – Martin Ender Nov 30 '15 at 10:09
8
\$\begingroup\$

Minkolang 0.14, 43 bytes

Thanks to Mego for inspiring this.

n1{d1`,2$3*&$z2zd2%-2l$Md1%-;z2%*z2:{+}2;N.

Test the code here and check all test cases here.

Explanation

This uses this recurrence relation:

a(0) = 0
a(1) = 1
a(2n) = a(n)
a(2n+1) = a(n) + 2^(floor(log_2(n))+1)

If n is the input, then a(n) is the resulting number after its binary sequence has been flipped. 0 and 1 are obvious. For a(2n) = a(n), consider that x0 (where x is any sequence of binary digits) flipped is 0x, which is the same as x. For a(2n+1), the reasoning is a bit more complicated. x1 flipped is 1x, which is equal to x + 2^k for some k. This k is one more than the number of digits in x, which is floor(log_2(n))+1. The full formula follows, except that it's modified a bit. This is what I actually code:

a(0) = 0
a(1) = 1
a(n) = a(n//2) + (n%2) * 2^(floor(log_2(n - n%2)))

As Mego and I worked out in chat, floor(n/2) = (n - n%2)/2. Thus, log_2(floor(n/2))+1 = log_2(n - n%2). Furthermore, multiplying by (n%2) collapses both the odd and even parts into one expression.

Finally, without any further ado, here's the code, explained.

n                                              Take number from input
 1{                                            Start recursion that takes only one element
   d1`,                                        1 if top of stack 0 or 1, 0 otherwise
       2$3*                                    26
           &                                   Jump if top of stack is not zero
            $z                                 Store top of stack in register (z)

               zd2%-                           n - n%2
                    2l$M                       log_2(n - n%2)
                        d1%-                   floor(log_2(n - n%2))
              2             ;                  2^floor(log_2(n - n%2))
                             z2%               n%2
                                *              Multiply
                                 z2:           n//2
                                    {          Recurse
                                     +         Add
                                      }        Return
                                       2;N.    Square it, output as number, and stop.
\$\endgroup\$
  • 1
    \$\begingroup\$ I think the recurrence is just a reformulation of iterating over the individual bits. \$\endgroup\$ – Martin Ender Nov 30 '15 at 10:11
  • 3
    \$\begingroup\$ I'm afraid this doesn't count. Whenever you see 2n and 2n+1 in a recurrence relation you should immediately think of it as looping over bits. \$\endgroup\$ – orlp Nov 30 '15 at 10:58
  • 1
    \$\begingroup\$ @orlp: Well, that's a bummer. I'm kinda convinced now that your bonus is impossible. \$\endgroup\$ – El'endia Starman Nov 30 '15 at 20:18
  • \$\begingroup\$ @El'endiaStarman I've almost got it, I think. \$\endgroup\$ – Conor O'Brien Dec 3 '15 at 18:41
8
\$\begingroup\$

Japt, 29 28 11 7 bytes

(You can save the program as a 7-byte IEC_8859-1-encoded file, then upload it to the interpreter.)

Japt is shortened JavaScript made by ETHproductions.

¢w n2 ²

Try it online!

Explanation:

  1. ¢ is shortcut to Us2, which compiles to U.s(2). U is input (implicit), .s(2) called by a number, invokes .toString(2) (converts to binary, parses as string).

  2. w compiles to .w(), which reverses the string (.split('').reverse().join('')).

  3. n2 works as parseInt(<number>,2), i.e. converts binary to decimal.

  4. ² invokes Math.pow(<number>,2), i.e. squares the number.

\$\endgroup\$
  • 1
    \$\begingroup\$ There's a string function toNumber on n, so you could do Us2 a w a n2 p2. Good job though! \$\endgroup\$ – ETHproductions Nov 29 '15 at 20:40
  • 1
    \$\begingroup\$ Also, w works the same on strings as it does on arrays, so you don't need the two as :) \$\endgroup\$ – ETHproductions Nov 29 '15 at 20:41
  • 1
    \$\begingroup\$ One last thing: Us2  = ¢, and p2 = ², bringing it down to 7 bytes: ¢w n2 ² \$\endgroup\$ – ETHproductions Nov 29 '15 at 20:44
  • 3
    \$\begingroup\$ The online interpreter now accepts IEC_8859-1 encoded files. (Although I'm not sure how to do UTF-8 and UTF-16 as well...) \$\endgroup\$ – ETHproductions Dec 1 '15 at 4:17
  • 2
    \$\begingroup\$ @ETHproductions - now I can +1 this :) \$\endgroup\$ – Digital Trauma Dec 2 '15 at 23:11
5
\$\begingroup\$

Python, 32 bytes

lambda x:int(bin(x)[:1:-1],2)**2

Try it online.

The code is pretty straightforward: bin(6), for example, gives 0b110, the binary representation of 6. [:1:-1] reverses the string and removes 0b. int converts the string to an integer from binary, and **2 squares it.

\$\endgroup\$
5
\$\begingroup\$

Jolf, 7 bytes

Just run it. The input on the page doesn't work.

^C_Bj22

Explanation

^C_Bj22
    j   numeric input
   B    convert to binary (str)
  _     reverse
 C   2  parse as binary integer to base 10
^     2 square
        implicit output

I added the Q command, which makes this 6 bytes: QC_Bj2

\$\endgroup\$
  • 4
    \$\begingroup\$ Crossed out 7 still looks like a 7. \$\endgroup\$ – a spaghetto Nov 29 '15 at 21:40
  • 2
    \$\begingroup\$ @quartata Not as bad as a crossed out 4. \$\endgroup\$ – orlp Nov 29 '15 at 21:51
4
\$\begingroup\$

TeaScript, 9 bytes 11

TeaScript is Javascript for golfing

®x÷v¤)**2

Will golf more once I get back to my computer

Try it online!

Test all

\$\endgroup\$
4
\$\begingroup\$

Seriously, 8 7 bytes

2;,¡R¿ª

Challenges like these are perfect for Seriously :)

Try it online

Explanation:

2;,¡    get a string representing the (decimal) input in binary, with a 2 on the bottom of the stack
R      reverse the string
¿    convert binary string to decimal int (using that extra 2 from earlier)
ª      square it
\$\endgroup\$
  • \$\begingroup\$ Nice job matching Jolf! \$\endgroup\$ – Conor O'Brien Nov 29 '15 at 21:28
  • \$\begingroup\$ +1 for having your interpreter accept CP437 encoding (or at least the hex representation of it) \$\endgroup\$ – Digital Trauma Nov 30 '15 at 20:49
4
\$\begingroup\$

J, 10 9 bytes

2^~|.&.#:

This is a tacit, monadic verb. Try it online!

Thanks to @randomra for golfing off 1 byte!

How it works

2^~|.&.#:  Right argument: y

       #:  Convert y to binary.
   |.      Reverse the digits.
     &.    Dual; apply the inverse of #:, i.e., convert back to integer.
 ^~        Apply power (^) with reversed argument order (~)...
2          to 2 and the previous result.
\$\endgroup\$
  • \$\begingroup\$ Link doesn't work, I get a 404 error on a google page that says "The requested URL /host/0B3cbLoy-_9Dbb0NaSk9MRGE5UEU/index.html was not found on this server. That’s all we know." \$\endgroup\$ – Bijan Apr 1 '17 at 19:38
2
\$\begingroup\$

CJam, 10 bytes

ri2bW%2b_*

Try it online

\$\endgroup\$
2
\$\begingroup\$

JavaScript, 64 63 56 53 bytes

n=>parseInt([...n.toString(2)].reverse().join``,2)**2

I realize I'm extra long, but hey, I can do it :P

Demo

\$\endgroup\$
  • \$\begingroup\$ instead of parseInt( you can do +("0b"+ \$\endgroup\$ – Downgoat Nov 29 '15 at 18:45
  • \$\begingroup\$ @Downgoat hm, it doesn't appear to give correct results. \$\endgroup\$ – nicael Nov 29 '15 at 18:48
  • \$\begingroup\$ [...n.toString(2)] and .join`` \$\endgroup\$ – Conor O'Brien Nov 29 '15 at 18:48
  • 1
    \$\begingroup\$ Even shorter w/ ES7 (49 bytes): n=>+("0b"+[...n.toString(2)].reverse().join``)**2. Doesn't work in any browsers yet \$\endgroup\$ – Downgoat Nov 29 '15 at 19:08
  • 1
    \$\begingroup\$ @CᴏɴᴏʀO'Bʀɪᴇɴ Thanks, this saves some bytes. \$\endgroup\$ – nicael Nov 29 '15 at 19:45
2
\$\begingroup\$

Perl 6, 21 bytes

{:2(.base(2).flip)²}

Example usage:

say {:2(.base(2).flip)²}(26); # 121

say (0..24).map: {:2(.base(2).flip)²};
# (0 1 1 9 1 25 9 49 1 81 25 169 9 121 49 225 1 289 81 625 25 441 169 841 9)

my &code = {:2(.base(2).flip)²};
say code 3; # 9

say chars code 10¹⁰⁰; # 140
\$\endgroup\$
2
\$\begingroup\$

PHP, 45 bytes

echo pow(bindec(strrev(decbin($argv[1]))),2);
\$\endgroup\$
2
\$\begingroup\$

Shell, 25

dc -e2o?p|rev|dc -e2i?d*p

Input/output via STDIN/STDOUT:

$ echo 26|dc -e2o?p|rev|dc -e2i?d*p
121
$ 
\$\endgroup\$
1
\$\begingroup\$

Pyth - 9 bytes

Straightforward conversions. I actually assigned 2 to a var which is pretty weird.

^i_jQK2KK

Test Suite.

\$\endgroup\$
1
\$\begingroup\$

Pyth, 9 bytes

^i_.BQ2 2

This is a very simple pyth based answer similar to the Python one

\$\endgroup\$
1
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 12 chars / 21 bytes

⦅`ᶀ`+ᴙ(ïß2)²

Try it here (Firefox only).

Noncompetitive answer, 9 chars / 18 bytes

⦅Յ+ᴙ(ïⓑ)²

Try it here (Firefox only).

\$\endgroup\$
  • 1
    \$\begingroup\$ Via this byte counter, gives 15 bytes (uses another encoding). \$\endgroup\$ – nicael Nov 29 '15 at 23:07
  • \$\begingroup\$ I grade using UTF-8 (until I can get Mines encoding to work). \$\endgroup\$ – Mama Fun Roll Nov 29 '15 at 23:12
  • \$\begingroup\$ The... name of the language... is boxes? \$\endgroup\$ – corsiKa Nov 30 '15 at 21:45
  • \$\begingroup\$ It's ESMin in doublestruck. The Unicode chars aren't fully supported. \$\endgroup\$ – Mama Fun Roll Nov 30 '15 at 23:41
1
\$\begingroup\$

Ruby, 35 bytes

->(x){x.to_s(2).reverse.to_i(2)**2}
\$\endgroup\$
1
\$\begingroup\$

TI-Basic (TI-84 Plus CE), 42 bytes

Prompt X
0→S
While X
2S→S
If X/2≠int(X/2
S+1→S
End
S2
\$\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.