Diagonal Binary Sequence

Question

Challenge:

Given a positive number \$n\$, convert it to binary, and output a sequence where all 1s form a top-left to bottom-right diagonal line, including a leading column of 1s. To give two examples:

\$n=1\$ will result in [1,3,5,9,17,33,65,129,...], with binary values:

1
11
101
1001
10001
100001
1000001
10000001
↓       ↘

\$n=89\$ will result in [89,153,281,537,1049,2073,4121,8217,...], with binary values:

1011001
10011001
100011001
1000011001
10000011001
100000011001
1000000011001
10000000011001
↓         ↘↘  ↘

In general, the binary sequences are formed by replacing the leading 1 with 10 in every iteration, with the exception of \$n=1\$.

Challenge rules:

• The input \$n\$ is guaranteed to be positive.
• Default sequence rules apply, so you're allowed to:
  • Take an additional input \$k\$ and output the \$k^{th}\$ value of the sequence, either 0-index or 1-index.
  • Take an additional input \$k\$ and output the first \$k\$ values of the sequence.
  • Output the values of the sequence indefintely.
• Of course, any reasonable output format can be used. Could be as strings/integers/decimals/etc.; could be as an (infinite) list/array/stream/generator/etc.; could be output with space/comma/newline/other delimiter to STDOUT; etc. etc.
  • I/O as binary isn't allowed for this challenge, since it's already easy enough as is.

Please state what I/O and sequence output-option you're using in your answer!

General Rules:

• This is code-golf, so the shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (e.g. TIO or ATO).
• Also, adding an explanation for your answer is highly recommended.

Test Cases:

n     First 10 values of the output sequence

1     [1,3,5,9,17,33,65,129,257,513,...]
2     [2,4,8,16,32,64,128,256,512,1024,...]
3     [3,5,9,17,33,65,129,257,513,1025,...]
6     [6,10,18,34,66,130,258,514,1026,2050,...]
7     [7,11,19,35,67,131,259,515,1027,2051,...]
12    [12,20,36,68,132,260,516,1028,2052,4100,...]
31    [31,47,79,143,271,527,1039,2063,4111,8207,...]
89    [89,153,281,537,1049,2073,4121,8217,16409,32793,...]
111   [111,175,303,559,1071,2095,4143,8239,16431,32815,...]
1000  [1000,1512,2536,4584,8680,16872,33256,66024,131560,262632,...]

Answer 1

Python, 39 bytes

lambda n,k:n^-2&(1^1<<k)<<len(bin(n))-3

Attempt This Online!

Explanation

lambda n,k:n^-2&(1^1<<k)<<len(bin(n))-3
           n^                             # change bits
             -2&                          # keep lowest bit
                (1^1<<k)                  # 1 0000 1  (k-1 zeros)
                        <<len(bin(n))-3   # shifted to highest bit

---

Python, 49 bytes

simple string based solution, the n&1 is needed to satisfy the test-case for input 1

lambda n,k:n&1|int((s:=bin(n))[:3]+k*"0"+s[3:],2)

Attempt This Online!

Answer 2

JavaScript (V8), 41 bytes

Prints the sequence 'indefinitely' (in practice, until the call stack overflows).

f=(n,k=2)=>k*2>n?print(n)|f(n+k):f(n,k*2)

Try it online!

Commented

f = (         // f is a recursive function taking:
  n,          //   n = input
  k = 2       //   k = power of 2 to be added to n
              //       the minimum is 2, because of
              //       the edge case n = 1
) =>          //
k * 2 > n ?   // if k * 2 is greater than n:
  print(n)    //   print n
  | f(n + k)  //   and do a recursive call with n + k
:             // else:
  f(n, k * 2) //   do a recursive call with k doubled

Answer 3

Husk, 8 bytes

¡(Y3ḋ:.ḋ

Try it online!

When your language does not have logarithms you need to get creative with base conversion. Here's some fun with half bits!

Takes a positive integer as input and outputs an infinite list of the sequence starting from that number.

Explanation

¡(Y3ḋ:.ḋ
¡(        Infinitely repeat the following commands and collect outputs in a list:
       ḋ    Convert to base 2
     :.     Prepend 0.5 as an extra initial digit
    ḋ       Convert back from base 2
  Y3        Take the maximum between the obtained value and 3

As the challenge states, this sequence can be generated by replacing the leading 1 in the binary representation of each value with 10. If we allow our "binary" number to have digits higher than 1, we could simply add 1 to the first digit (e.g. \$5_{10} = 101_2 \rightarrow 201_{"2"} = 1001_{2} = 9_{10}\$). Even better, adding 1 to a digit in base 2 is equivalent to adding 0.5 to the digit preceding it! (\$201_{"2"} = [0.5][1][0][1]_{2.0} = 1001_2\$; I think I'm starting to get too creative with notation here).

Taking the maximum between the resulting number and 3 was the shortest way I could find to fix the edge case for 1.

Answer 4

Python 2, 41 bytes

A function that takes \$ n \$ as input, and outputs the sequence indefinitely.

def f(n):print n;f(n^3<<len(bin(n))-3&-2)

Try it online!

Answer 5

05AB1E, 9 bytes

λbg<1Mo₁+

Try it online! or try all testcases.

Explanation

λ         # recursively start with f(0) = n
 bg<       # push floor(log2(f(i-1)))
 1M        # max(1, floor(log2(f(i-1))))
 o         # 2**max(1, floor(log2(f(i-1))))
 ₁+        # f(i) = f(i-1) + 2**max(1, floor(log2(f(i-1))))

Answer 6

Haskell, 35 bytes

(%2)
n%k|k*2>n=n:(n+k)%k|l<-k*2=n%l

Attempt This Online!

Port of Arnauld's JavaScript answer.

Answer 7

Excel, 41 53 bytes

=DECIMAL(10^B1&TEXTAFTER(BASE(A1,2),1),2)+IF(B1,A1=1)

Inputs n and k in cells A1 and B1 respectively, where k represents the kth 0-indexed value of the sequence.

Answer 8

K (ngn/k), 13 bytes

(3|2/2,1_2\)\

Try it online!

A base conversion trick that works somewhat like Husk or Nekomata answers, but keeps things in integers. This works by replacing the leading 1 with a 2 in the binary representation.

(3|2/2,1_2\)\
(          )\    collect first k iterations:
         2\      convert to base 2
     2,1_        remove the leading 1 and attach a 2
   2/            convert from "base 2" to integer
 3|              max with 3 to handle 1

Answer 9

Nibbles, 8.5 7.5 bytes (15 nibbles)

`.$+^2,:>2``@

Attempt This Online!

`.$+^2,:>2``@    # full program
`.$+^2,:>2``@$$$ # with implicit arguments shown;
`.               # iterate while unique (in this case, for ever),
  $              # starting with the input:
   +             #   add
               $ #   the previous result to
    ^2           #   2 to the power of
      ,          #     the length of 
          ``@$   #     the binary digits of the previous result
        >2       #     without the first two digits
       :      $  #     and appending the result so far

Answer 10

R, 40 bytes

f=\(n){m=log2(print(n))%/%1;f(n+2^m+!m)}

Attempt This Online!

Answer 11

x86 32-bit machine code, 14 bytes

0F BD C8 E3 03 0F B3 C8 01 D1 0F AB C8 C3

Try it online!

Following the regparm(2) calling convention, this takes n in EAX and a 0-index in EDX, and returns a number in EAX.

In assembly:

f:  bsr ecx, eax    # Set ECX to the highest position of a 1 bit in EAX.
    jecxz s         # Jump if ECX is 0.
    btr eax, ecx    # (Otherwise) Remove that highest 1 bit.
s:  add ecx, edx    # Add the index (in EDX) to ECX.
    bts eax, ecx    # Reinsert a 1 bit into EAX at position ECX.
    ret             # Return.

Answer 12

Uiua, 18 14 bytes

⍥(+ⁿ∶2↥1-1⧻⋯.)

Try it!

Returns the nth member of the sequence.

-4 thanks to Dominic van Essen

⍥(+ⁿ∶2↥1-1⧻⋯.)
⍥(           )  # repeat
            .   # duplicate
           ⋯    # convert to bits
          ⧻     # length
        -1      # subtract 1
      ↥1        # max between this and 1 (need this for input of 1)
   ⁿ∶2          # 2 raised to the result
  +             # add

Answer 13

K (ngn/k), ²⁵ 21 bytes

{2/?[;!2;1,x=1]@2\x}\

Try it online!

-4 bytes - thanks to @coltim

Answer 14

Rust, 49 bytes

Input is an integer n as a start value and an integer k for the sequence index. I tried experimenting with next_power_of_two, but the name turned out to be way too long.

|n:u64,k:u32|1<<n.ilog2()+k|n&!(1<<n.ilog2())|n&1

Attempt This Online!

Explanation and prettier code:

// A captureless closure with two integer arguments
// n is the seed number, k is the sequence index
|n: u64, k: u32|
// The following numbers get bit-or'ed together:
       // A one followed by zeroes whose length is the length of the original number plus the parameter k.
       // ilog2 calculates the floored base-2 logarithm.
       // This means 1 shifted by it is equivalent to setting all digits but the most significant one to zero. 
       // Adding k means shifting the most significant one, which is the only thing k is used for in this sequence. 
       1 << n.ilog2() + k
       // The number n, with its most significant one bit set to zero (the replacement part). 
   |   n & !(1 << n.ilog2())
       // A one if the original number's least significant digit contains a one. Only relevant for n=1.
   |   n & 1

Answer 15

Retina 0.8.2, 84 bytes

^.+
$*
+`^(1+)\1
$+0
01
1
^(.)(.+)?¶(.+)
$1$3$*0$2$#2$*##
0##
0
1|0#
01
+`10
011
%`1

Try it online! Takes n and k as input and outputs the kth (0-indexed) term of the sequence but link is to test suite for multiple values of n that sets k=0..4 (because larger values would be too slow).

91 bytes to output the first k terms:

^.+
$*
+`^(1+)\1
$+0
01
1
^(.)(.*)¶(.+)
$1$3$*_$2
_
$'¶1
O`
1A`
_\b
1
_
0
1
01
+`10
011
%`1

Try it online! Takes n and k as input and outputs the first k terms of the sequence but link is to test suite for multiple values of n that sets k=5 (because larger values would be too slow). Explanation:

^.+
$*

Convert n to unary.

+`^(1+)\1
$+0
01
1

Convert n to binary.

^(.)(.*)¶(.+)
$1$3$*_$2

Convert k to unary as _s and insert it after the first digit of n.

_
$'¶1
O`
1A`

Generate all of the first k terms.

_\b
1

Fix the n=1 error.

_
0

Change the remaining _s to 0s.

1
01
+`10
011

Convert to unary.

%`1

Convert to decimal.

54 bytes with the original intent that the leading 1 participates in the diagonal:

.+¶
$*_
\d+
$*
+`(1+)\1
$+0
01
1
^.|1
01
+`1[0_]
011
1

Try it online! Takes k and n as input and outputs the kth (0-indexed) term of the sequence but link is to test suite for multiple values of n that sets k=0..4 (because larger values would be even slower).

70 bytes to output the first k terms:

.+¶
$*_
\d+
$*
+`(1+)\1
$+0
01
1
M!&`_.+
O`
%`^_.|1
01
+`1[0_]
011
%`1

Try it online! Takes k and n as input and outputs the first k terms of the sequence but link is to test suite for multiple values of n that sets k=5 (because larger values would be even slower). Explanation:

.+¶
$*_

Convert k to unary as _s.

\d+
$*

Convert n to unary.

+`(1+)\1
$+0
01
1

Convert n to binary.

M!&`_.+
O`

Generate the first k terms.

%`^_.|1
01
+`1[0_]
011

Convert to unary, but the leading _ makes the next digit 1 while any remaining _s are interpreted as 0s.

%`1

Convert to decimal.

Answer 16

Fortran (GFortran), 73 bytes body, 13 bytes header and footer

program x

read*,n;i=2**(31-leadz(n));n=n-i;do;print*,i+n;if(i<2)n=n+1;i=i*2;end do

end

Try it online: n=1, n=89

Reads n from standard input and outputs the corresponding sequence.

Uses leadz() to count the leading zeros. Puts the highest 1 into i and removes it from n. The loop shifts the highest 1 further to the left in each iteration and outputs the sum of i and n in each cycle. Special handling for n==1.

Answer 17

Perl 5.10 -n, 35 bytes

$_^=$_-1?3<<(1.4427*log):2while say

Try it online!

Finds the next elem by xor'ing the current n with 3 << log₂(n) where << is the left shift operator that only cares about the integer part of log₂. Here n=1 is handled as a special case where 1 is xor'ed by 2 to get 3.

 89 xor (3 << log2(89)  ) =  89 xor (3<<6) = 153
153 xor (3 << log2(153) ) = 153 xor (3<<7) = 281
281 xor (3 << log2(281) ) = 281 xor (3<<8) = 537
.
.

Answer 18

TI-Basic, 20 bytes

While 1
Disp Ans
max(3,Ans+2^int(log(Ans,2
End

Takes input in Ans. Outputs infinitely with each number on its own line. If not using OS 2.53 MP or higher, replace log(Ans,2 with log(Ans)/log(2 for +2 bytes.

Answer 19

Charcoal, 20 19 bytes

ＮθＩ⁺θ×Ｘ²Ｌ⍘÷貦²⊖Ｘ²Ｎ

Try it online! Takes n and k as input and outputs the 0-indexed kth element but link is to version that outputs the first k elements at a cost of 1 byte. Explanation: Port of @Arnauld's JavaScript answer with some inspiration from @DominicvanEssen's Nibbles answer.

Ｎθ                  Input `n` as a number
       ²            Literal integer `2`
      Ｘ             Raised to power
           θ        Input `n`
          ÷         Integer divided by
            ²       Literal integer `2`
         ⍘          Converted to base
              ²     Literal integer `2`
        Ｌ           Take the length
     ×              Multiplied by
                 ²  Literal integer `2`
                Ｘ   Raised to power
                  Ｎ Input `k` as a number
               ⊖    Decremented
   ⁺                Plus
    θ               Input `n`
  Ｉ                 Cast to string
                    Implicitly print

14 bytes with the original intent that the leading 1 participates in the diagonal:

ＮθＩ｜θＸ²⁺⊖Ｌ↨θ²Ｎ

Try it online! Takes n and k as input and outputs the 0-indexed kth element but link is to version that outputs the first k elements at a cost of 1 byte. Explanation:

Ｎθ              Input `n` as a number
      ²         Literal integer `2`
     Ｘ          Raised to power
           θ    Input `n`
          ↨     Converted to base
            ²   Literal integer `2`
         Ｌ      Take the length
        ⊖       Decremented
       ⁺        Plus
             Ｎ  Input `k`
   ｜            Bitwise Or
    θ           Input `n`
  Ｉ             Cast to string
                Implicitly print

Answer 20

Nekomata, 9 bytes

ᶦ{Ƃ2ŗɔƃ3M

Attempt This Online!

A port of @Leo's Husk answer.

ᶦ{Ƃ2ŗɔƃ3M
ᶦ{          Infinite loop and print the result of each iteration:
  Ƃ             Convert to base 2
   2ŗɔ          Prepend 1/2
      ƃ         Convert back from base 2
       3M       Take the maximum of the result and 3

Answer 21

05AB1E, 8 bytes

λb¦TìC3M

Now that it's been a short while, I'm gonna post my own solution.

Outputs the infinite sequence.

Try it online or verify the first ten terms of all test cases.

Explanation:

λ         # Create a recursive environment,
          # to generate the infinite sequence
          # (which will be lazily output implicitly at the end)
          # Starting with a(0) = (implicit) input
          # And where every following a(n) is calculated as:
          #  Implicitly push the previous term a(n-1)
 b        #  Convert a(n-1) to a binary string
  ¦       #  Remove its leading "1"
   Tì     #  Prepend "10" instead
     C    #  Convert it back from binary to a (base-10) integer
      3M  #  Manually fix a(1) for input=1:
      3   #   Push 3
       M  #   Push a copy of the maximum of the stack

Answer 22

Uiua, 12 bytes

⍥(↥3+⍜'ₙ2⌊.)
⍥(+ⁿ↥1⌊ₙ2,2)

Try it online!

⍥(↥3+⍜'ₙ2⌊.)    input: repetition, initial number
⍥(         )    repeat the successor operation the given number of times:
      ⍜'ₙ2⌊      power of two <= current number
   ↥3+     .     add to the current number, and maximum with 3 to handle 1

⍥(+ⁿ↥1⌊ₙ2,2)
       ⌊ₙ2,       floor(log2(current number))
     ↥1          max with 1 to handle 1
    ⁿ     2      2 raised to the power of that
   +             add to the current number

Could be 10 bytes if there weren't a bug in ⍜ₙ:

⍥(+⊃⍜ₙ⌊↥2)
    ⊃    2    call two functions on 2 and the current number:
      ⍜ₙ⌊      power of two <= current number,
         ↥     max
   +           add the two

Answer 23

Ruby, 39 bytes

->n,k{r=1;r*=2until n<r*2;n-r/2*2|r<<k}

Try it online!