Sloping Binary Numbers

Question

Given an integer n, output the first n sloping binary numbers, either 0- or 1-indexed. They are called this because of how they are generated:

Write numbers in binary under each other (right-justified):

........0
........1
.......10
.......11
......100
......101
......110
......111
.....1000
.........

Then, you need to take each diagonal from bottom-left to top-right, such that each final digit is the final digit of a diagonal. Here's the fourth diagonal (zero-indexed) marked with x's, which is 100:

........0
........1
.......10
.......11
......10x
......1x1
......x10
......111
.....1000
.........

The upward-sloping diagonals in order are:

0
11
110
101
100
1111
1010
.......

Then, convert to decimal, giving 0, 3, 6, 5, 4, 15, 10, ...

OEIS A102370

This is code-golf, so the shortest code in bytes wins.

I don't think this specification is very clear. I had to do a good deal of external reading before I could understand what was being asked here. — Sriotchilism O'Zaic, Dec 22 '16 at 23:13
Here's a visualization, if it helps. Read the "ovals" top to bottom, and within the oval from bottom left to top right. Those give you the binary numbers you need to convert to decimal. — Pavel, Dec 22 '16 at 23:35
What do you mean, "either 0- or 1-indexed"? Do you mean that one may output either the first n or the first n+1 numbers? — smls, Dec 22 '16 at 23:49
I think this might have allowed more interesting answers if you just had to return the n'th value. — xnor, Dec 23 '16 at 3:27
@PatrickRoberts I never put a limit on how many to generate. I simply said "write numbers in binary...". You generate as many as you need to. — mbomb007, Dec 23 '16 at 18:11

PurkkaKoodari · Accepted Answer · 2016-12-23 01:00:31Z

3

Jelly, 11 bytes

ḤḶBUz0ŒDUḄḣ

Try it online!

Explanation

ḤḶBUz0ŒDUḄḣ    Main link. Argument: n
Ḥ              Double the argument. This ensures there are enough
               rows, since n + log2(n) <= 2n.
 Ḷ             Get range [0 .. 2n-1].
  B            Convert each number to binary.
   U           Reverse each list of digits. 
    z0         Transpose, padding with zeroes to a rectangle.
      ŒD       Get the diagonals of the rectangle, starting from the
               main diagonal. This gets the desired numbers, reversed,
               in binary, with some extras that'll get dropped.
        U      Reverse each diagonal.
         Ḅ     Convert each diagonal from binary to a number.
          ḣ    Take the first n numbers.

The transpose is the simplest way to pad the array for the diagonals builtin to work. Then the reverses are added to get everything in the correct order.

edited Dec 23 '16 at 1:00

answered Dec 22 '16 at 23:56

PurkkaKoodari

15.7k2 gold badges28 silver badges81 bronze badges

\$\begingroup\$ The implementation of the OEIS formula might also be really short in Jelly. \$\endgroup\$ – Yytsi Dec 23 '16 at 0:04
\$\begingroup\$ @TuukkaX Might be. I'm tired enough to find picking an upper limit for the sum hard. \$\endgroup\$ – PurkkaKoodari Dec 23 '16 at 0:19
\$\begingroup\$ @TuukkaX I tried it, but I don't see it happening. I'm sure Dennis & co will implement it in 5 bytes or so. \$\endgroup\$ – PurkkaKoodari Dec 23 '16 at 0:52
\$\begingroup\$ Currently you are lucky ;) \$\endgroup\$ – geisterfurz007 Dec 23 '16 at 6:16

add a comment |

Neil · Accepted Answer · 2016-12-23 00:46:43Z

7

JavaScript (ES6), 53 bytes

n=>[...Array(n)].map(g=(j=1,i)=>j>i?0:j&i|g(j+j,i+1))

0-indexed. It's not often I get to use a recursive function as a parameter to map.

answered Dec 23 '16 at 0:46

Neil

90.2k8 gold badges46 silver badges190 bronze badges

add a comment |

Greg Martin · Accepted Answer · 2016-12-22 23:39:46Z

Mathematica, 46 bytes

Plus@@@Table[BitAnd[n+k,2^k],{n,0,#},{k,0,n}]&

Unnamed function taking a nonnegative integer # as input and returning the 0-index sequence up to the #th term. Constructs the sloping binary numbers using BitAnd (bitwise "and") with appropriate powers of 2.

Community · Accepted Answer · 2017-04-13 12:39:04Z

2

Python3, 63 61 bytes

lambda i:[sum(n+k&2**k for k in range(n+1))for n in range(i)]

Uses the formula from OEIS.

-2 bytes thanks to Luis Mendo! i+1 --> i

edited Apr 13 '17 at 12:39

Community♦

1

answered Dec 23 '16 at 0:01

Yytsi

3,0771 gold badge12 silver badges32 bronze badges

\$\begingroup\$ Can you explain how you went from Sum_{ k >= 1 such that n + k == 0 mod 2^k } 2^k to that simpler bitwise formula? \$\endgroup\$ – smls Dec 23 '16 at 0:36
\$\begingroup\$ @smls It just calculates the upward diagonals directly. I actually thought it was more obvious than the other form. \$\endgroup\$ – Neil Dec 23 '16 at 0:41

add a comment |

Titus · Accepted Answer · 2016-12-22 23:52:13Z

1

PHP, 68 bytes

for(;$n++<$argv[1];print$s._)for($s=$i=0;$i<$n;)$s|=$n+$i-1&1<<$i++;

takes input from command line argument, prints numbers separated by underscores. Run with -r.

answered Dec 22 '16 at 23:52

Titus

13.6k1 gold badge14 silver badges41 bronze badges

add a comment |

Luis Mendo · Accepted Answer · 2016-12-23 09:51:16Z

MATL, 18 17 bytes

:q"@tt:+5MW\~fWs+

Try it online!

This uses the formula from OEIS:

a(n) = n + Sum_{ k in [1 2... n] such that n + k == 0 mod 2^k } 2^k

Code:

:q"     % For k in [0 1 2 ...n-1], where n is implicit input
  @     %   Push k
  tt    %   Push two copies
  :     %   Range [1 2 ... k]
  +     %   Add. Gives [n+1 n+2 ... n+k]
  5M    %   Push [1 2... k] again
  W     %   2 raised to that
  \     %   Modulo
  ~f    %   Indices of zero entries
  W     %   2 raised to that
  s     %   Sum of array
  +     %   Add
        % End implicitly. Display implicitly

Community · Accepted Answer · 2017-04-13 12:39:13Z

Perl 6, 59 43 bytes

~~{map ->\n{n+sum map {2**$_ if 0==(n+$_)%(2**$_)},1..n},^$_}~~

{map {sum map {($_+$^k)+&2**$k},0..$_},^$_}

Uses the formula from the OESIS page.
Update: Switched to the bitwise-and based formula from TuukkaX's Python answer.

Perl 6, 67 bytes

{map {:2(flip [~] map {.base(2).flip.comb[$++]//""},$_..2*$_)},^$_}

Naive solution.
Converts the numbers that are part of the diagonal to base 2, takes the correct digit of each, and converts the result back to base 10.

Dennis · Accepted Answer · 2016-12-23 03:44:43Z

0

Jelly, 15 bytes

2*ḍ+
ḶçÐ€ḶUḄ+Ḷ’

This would be shorter than the other Jelly answer if we had to print only the n^th term.

Try it online!

answered Dec 23 '16 at 3:44

Dennis

193k36 gold badges324 silver badges765 bronze badges

add a comment |

Billywob · Accepted Answer · 2016-12-23 15:58:40Z

0

R, 66 bytes

function(n,k=0:length(miscFuncs::bin(n-1)))sum(bitwAnd(k+n-1,2^k))

Unnamed function which uses the bin function from the miscFuncs package to calculate the length of n represented in binary and then using one of the OEIS formulas.

answered Dec 23 '16 at 15:58

Billywob

3,3436 silver badges16 bronze badges

add a comment |

Stack Exchange Network

current community

your communities

more stack exchange communities

Sloping Binary Numbers

9 Answers 9

Jelly, 11 bytes

Explanation

JavaScript (ES6), 53 bytes

Mathematica, 46 bytes

Python3, 63 61 bytes

PHP, 68 bytes

MATL, 18 17 bytes

Perl 6, 59 43 bytes

Perl 6, 67 bytes

Jelly, 15 bytes

R, 66 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged code-golf sequence base-conversion binary or ask your own question.

Hot Network Questions

Sloping Binary Numbers

9 Answers 9

Jelly, 11 bytes

Explanation

JavaScript (ES6), 53 bytes

Mathematica, 46 bytes

Python3, 63 61 bytes

PHP, 68 bytes

MATL, 18 17 bytes

Perl 6, 59 43 bytes

Perl 6, 67 bytes

Jelly, 15 bytes

R, 66 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golf sequence base-conversion binary or ask your own question.

Related

Hot Network Questions