15
\$\begingroup\$

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 , so the shortest code in bytes wins.

\$\endgroup\$
  • 12
    \$\begingroup\$ 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. \$\endgroup\$ – Sriotchilism O'Zaic Dec 22 '16 at 23:13
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Pavel Dec 22 '16 at 23:35
  • \$\begingroup\$ 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? \$\endgroup\$ – smls Dec 22 '16 at 23:49
  • 4
    \$\begingroup\$ I think this might have allowed more interesting answers if you just had to return the n'th value. \$\endgroup\$ – xnor Dec 23 '16 at 3:27
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – mbomb007 Dec 23 '16 at 18:11
3
\$\begingroup\$

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.

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

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.

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

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.

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

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

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

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.

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

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

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.

\$\endgroup\$
0
\$\begingroup\$

Jelly, 15 bytes

2*ḍ+
ḶçЀḶUḄ+Ḷ’

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

Try it online!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\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.