20
\$\begingroup\$

Challenge:

Given a positive number \$n\$, convert it to binary, and output a 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 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 , 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,...]
\$\endgroup\$
9
  • 4
    \$\begingroup\$ I wonder how your prepared answer deals with the edge case of 1... \$\endgroup\$
    – Neil
    Oct 9, 2023 at 7:33
  • 3
    \$\begingroup\$ Test cases n=1 and n=3 seem to be missing a 257, unless I'm misunderstanding the problem. \$\endgroup\$ Oct 9, 2023 at 7:39
  • 2
    \$\begingroup\$ @Neil I realize I made a mistake in my own challenge.. The leading 1 of \$n=89\$ (or any \$n\$ including \$1\$) should have been a diagonal line as well.. -_-' Ah well, too late to change it now since there are already a bunch of answers. \$\endgroup\$ Oct 9, 2023 at 8:24
  • 1
    \$\begingroup\$ Usually I find the edge-cases (like 1 here) to be an annoyance, but in this case somehow it seems to be one of the main aspects of the challenge... \$\endgroup\$ Oct 9, 2023 at 12:35
  • 1
    \$\begingroup\$ @PeterCordes If they're under the hood binary it's completely fine. I indeed meant to disallow base-2 strings and lists as I/O. \$\endgroup\$ Oct 12, 2023 at 6:41

23 Answers 23

12
\$\begingroup\$

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!

\$\endgroup\$
9
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ Prints the sequence ... until FP rounding error makes it start printing something else, long before callstack overflow. e.g. f(odd) should always be odd since we keep the low bit, but after 51 numbers, the output for f(7) includes 9007199254740996 and soon after the numbers all end with multiple trailing zeros. I presume answers aren't required to use BigInt in langs without easy access to it (like C before C23 _BitInt, or older JavaScript), but it's worth noting en.wikipedia.org/wiki/… (52-bit mantissa) \$\endgroup\$ Oct 12, 2023 at 0:36
7
\$\begingroup\$

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.

\$\endgroup\$
6
\$\begingroup\$

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!

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

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))))
\$\endgroup\$
2
  • \$\begingroup\$ Why did you use bg< as an obfuscated floor(log2(...)) when the actual .²ï is the same length? And nice solution, +1 from me. I had λb¦TìC₁Θ+ myself. :) \$\endgroup\$ Oct 9, 2023 at 8:59
  • 2
    \$\begingroup\$ @KevinCruijssen bg< doesn't rely on floating-point arithmetic so IMHO it's actually better. \$\endgroup\$
    – Neil
    Oct 9, 2023 at 11:14
5
\$\begingroup\$

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.

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

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Just like my prepared unposted solution, I'm afraid this fails for edge case \$n=1\$. \$\endgroup\$ Oct 9, 2023 at 8:21
  • 2
    \$\begingroup\$ @KevinCruijssen Ah, good spot, thanks. Corrected at the annoying cost of 12 bytes. \$\endgroup\$ Oct 9, 2023 at 9:12
5
\$\begingroup\$

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

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

R, 40 bytes

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

Attempt This Online!

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

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.
\$\endgroup\$
1
  • \$\begingroup\$ For readers not familiar with the 386 bit-manipulation instructions, bsr is Bit Scan Reverse (like count leading zeros but gives the bit-index, so like ilog2). BTR is Bit Test and Reset (clear the bit and set CF = old value at that position.) BTS is Bit Test and Set (felixcloutier.com/x86/bts), like dst |= 1<< src, also setting CF = old value. A uint64_t version of this would need REX prefixes (1 byte each) on BSR, BTR, and BTS, so 3 more bytes. (jrcxz is still 2 bytes, and add is working with small numbers, just the index) \$\endgroup\$ Oct 12, 2023 at 0:57
4
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ Note that you could drop the and simply use the "output the first 𝑘 values of the sequence" option to save 1 byte... \$\endgroup\$ Oct 11, 2023 at 15:46
  • \$\begingroup\$ @DominicvanEssen But then I would need a pop because the stack is output at the end of the program. Consider this output. \$\endgroup\$
    – chunes
    Oct 11, 2023 at 16:07
  • \$\begingroup\$ Ah. I hadn't thought that the stack was output (I thought that the online window displayed it for convenience, separately from STDOUT). So if the stack is output, you can drop both and &p. and use the "output the 𝑘𝑡ℎ value of the sequence, ... 0-index ..." option to save 4 bytes, like this... \$\endgroup\$ Oct 12, 2023 at 7:48
  • \$\begingroup\$ @DominicvanEssen Thanks! \$\endgroup\$
    – chunes
    Oct 12, 2023 at 15:35
4
\$\begingroup\$

K (ngn/k), 25 21 bytes

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

Try it online!

-4 bytes - thanks to @coltim

\$\endgroup\$
3
  • \$\begingroup\$ Port of @Leo’s Husk solution is shorter: f:(3|2/2\_2/0.5,2\)\ \$\endgroup\$
    – doug
    Oct 10, 2023 at 4:34
  • \$\begingroup\$ The 2/2\ can be dropped from that too, leaving (3|_2/0.5,2\)\ (for 14 bytes). Another 14 byter: {3|x+2/&\2\x}\ . (trailing spaces because I can't figure out the markdown...) \$\endgroup\$
    – coltim
    Oct 20, 2023 at 16:13
  • 2
    \$\begingroup\$ It's also possible to shave some bytes from your original answer: {2/?[2\x;!2;1,x=1]}\ \$\endgroup\$
    – coltim
    Oct 20, 2023 at 21:12
4
\$\begingroup\$

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

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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
.
.
\$\endgroup\$
2
  • \$\begingroup\$ I'm curious whether you actually need the final digit of 1.4427...? Obviously this answer is only accurate within reasonable bounds (presumably exceeding the numeric limit of Perl), as it would theoretically lose precision at values > exp(10000). But is there any value within Perl's numeric limit for which 1.443 wouldn't suffice? Can Perl handle values as large as exp(1000) == 10^434? \$\endgroup\$ Oct 11, 2023 at 9:26
  • \$\begingroup\$ @DominicvanEssen I thought about that but didn't get around to check it. Maybe more digits are needed also, not less. As "Try it online" shows, scrolling down, Perl builtin numbers overflows after a few steps, and when I tried use bigint then somehow I couldn't get << to work (maybe << isnt overloaded). An alternative to 3<<log2(n) could be 3*2**int(log2(n)), maybe that works with bigint, but then more bytes are needed. \$\endgroup\$
    – Kjetil S
    Oct 11, 2023 at 19:58
2
\$\begingroup\$

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.

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

Charcoal, 20 19 bytes

NθI⁺θ×X²L⍘÷貦²⊖X²N

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.

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

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

NθI|θX²⁺⊖L↨θ²N

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:

Nθ              Input `n` as a number
      ²         Literal integer `2`
     X          Raised to power
           θ    Input `n`
          ↨     Converted to base
            ²   Literal integer `2`
         L      Take the length
        ⊖       Decremented
       ⁺        Plus
             N  Input `k`
   |            Bitwise Or
    θ           Input `n`
  I             Cast to string
                Implicitly print
\$\endgroup\$
2
\$\begingroup\$

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

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

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

Ruby, 39 bytes

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

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.