| Bytes | Lang | Time | Link |
|---|---|---|---|
| 098 | AWK | 250807T150025Z | xrs |
| 8375 | Vyxal | 231113T142408Z | pacman25 |
| 017 | APL Dyalog Extended | 200323T074155Z | Bubbler |
| 007 | W x | 200321T054842Z | user9206 |
| 057 | bash + GNU utilities | 200320T055804Z | Mitchell |
| 070 | Wolfram Language Mathematica | 200321T003221Z | ZaMoC |
| 369 | Zpr'h | 200321T000116Z | Jonathan |
| 029 | APL Dyalog Classic | 200320T231102Z | AviFS |
| 011 | Jelly | 200319T232630Z | Jonathan |
| 062 | Octave | 200320T174034Z | Luis Men |
| 104 | C gcc | 200320T153919Z | Noodle9 |
| 011 | Japt | 200320T080945Z | Shaggy |
| 013 | Gaia | 200320T181421Z | Giuseppe |
| 080 | Haskell | 200320T143727Z | ovs |
| 128 | Haskell | 200320T023533Z | Jonathan |
| 108 | PHP | 200320T143452Z | Guillerm |
| 026 | K ngn/k | 200320T093733Z | Galen Iv |
| 073 | Perl 5 n | 200320T065741Z | andytech |
| 092 | Factor | 200320T125414Z | Galen Iv |
| 111 | Red | 200320T090818Z | Galen Iv |
| 009 | 05AB1E | 200320T080204Z | Kevin Cr |
| 048 | Ruby | 200320T090904Z | G B |
| 067 | Python | 200319T224711Z | Noodle9 |
| 014 | Jelly | 200319T235415Z | RGS |
| 022 | Charcoal | 200319T234748Z | Neil |
| 015 | MATL | 200319T223441Z | Luis Men |
| 011 | Jelly | 200319T232213Z | Nick Ken |
| 007 | Husk | 200319T230748Z | Leo |
AWK, 98 bytes
{for(;z<$1;y=X){for(x=++i;x;x=int(x/2))y=x%2y
match(s=s y,/1+0+/)&&++z;sub(/1+0+/,X,s)}}$0=RLENGTH
Vyxal, 67 bitsv2, 8.375 bytes
Þ∞bfĠ2ẇvf@
Bitstring:
0010011101110110001111101100111001011111001011101000111011000011110
APL (Dyalog Extended), 17 bytes
{⍵⊃≢¨⊆⍨1+∊⊤¨⍳+⍨⍵}
Gives nth term, 1-indexed.
How it works
{⍵⊃≢¨⊆⍨1+∊⊤¨⍳+⍨⍵}
{ } ⍝ ⍵←n
+⍨⍵ ⍝ Double of n
⍳ ⍝ 1 .. 2n, inclusive
∊⊤¨ ⍝ Convert each to binary and flatten
1+ ⍝ Add 1
⊆⍨ ⍝ Partition self into non-increasing segments
⍝ (Without 1+, zero items are dropped)
≢¨ ⍝ Lengths of each segment
⍵⊃ ⍝ Take nth item
W x, 7 bytes
REALLY slow. The array is 1-indexed and it outputs all upto the input. (Glad that I tie with Husk BTW. Special bonus: it doesn't involve infinite lists!)
♫│x╤►U╟
Uncompressed:
^k2BLHkr
Explanation
^ % 10 ^ input. Make sure that enough items are calculated.
k % Find the length range of that.
2B % Convert every item to binary.
% Since at least 1 item >= the base, this vectorizes.
% Automatic flatten before grouping
LH % Grouping: Is the previous item >= current item?
kr % Reduce by length
Flag:x % Output all items upto the input, including input-indexed item. 1-indexed.
W x, 8 bytes
You can try this without having to wait for a long time.
☺│╪å∟↕c╟
Uncompressed:
3*k2BLHkr
Explanation
3* % Input times 3, idea copied from RGS's answer.
k % Provide a length-range
2B % Convert all to binary
LH % Group by >=
% Automatic flattening before grouping
kr % Reduce by length
Flag:x % Output all less than the input index. INCLUDING the input index item.
```
bash + GNU utilities, 76 58 57 bytes
seq -f 2o%.fn $[2*$1]|dc|sed -E "s/(1*0*){$1}.*/\1Zp/"|dc
Thanks to user41805 for suggestions that ended up shaving 18 bytes off! And for 1 more byte now too.
Takes \$n\$ as an argument, and prints the \$n^\text{th}\$ entry in the sequence (with 1-based indexing).
Wolfram Language (Mathematica), 70 bytes
Tr[1^Join@@Partition[Split[Join@@IntegerDigits[Range[2#],2]],2][[#]]]&
Zpr'(h, 369 bytes
s |> \
(g (foldr (op-> ++) () (map b |N)))
(e ())|>o
(e (S ()))|>z
(e (S (S .n)))|>(e n)
(h ())|>()
(h (S ()))|>()
(h (S (S .n)))|>(S (h n))
(b ())|>()
(b (S .n))|>((b (h (S n))) ++ (' (e n) ()))
(l (' z (' o .r)))|>1
(l (' z (' z .r)))|>(S (l (' z r)))
(l (' o (' o .r)))|>(S (l (' o r)))
(l (' o (' z .r)))|>(S (l (' z r)))
(g .a)|>(' (l a) (g (drop (l a) a)))
<|prelude.zpr
main |> (take 8 s)
Execution
Zpr-h-master/stdlib$ ../Zprh --de-peano above.zpr
(' 3 (' 5 (' 2 (' 4 (' 7 (' 3 (' 3 (' 2 0))))))))
Explanation
; build the sequence by splitting the bits of all natural numbers |N
sequence |> (generate (foldr (op-> ++) () (map bits |N)))
; compute if a natural number is even (parity shifted by one)
(even ()) |> one
(even (S ())) |> zero
(even (S (S .n))) |> (even n)
; halve a natural number, rounding down
(halve ()) |> ()
(halve (S ())) |> ()
(halve (S (S .n))) |> (S (halve n))
; compute a natural number's binary representation
(bits ()) |> ()
(bits (S .n)) |> ((bits (halve (S n))) ++ (' (even n) ()))
; compute the length of the pattern sought after at the bit stream's beginning
(len (' zero (' one .rest))) |> 1
(len (' zero (' zero .rest))) |> (S (len (' zero rest)))
(len (' one (' one .rest))) |> (S (len (' one rest)))
(len (' one (' zero .rest))) |> (S (len (' zero rest)))
(generate .all-bits) |> (' (len all-bits) \
(generate (drop (len all-bits) all-bits)))
; include from the standard library
<| prelude.zpr
; output the first eight sequence members
main |> (take 8 sequence)
Jelly, 11 bytes
ḤB€FŒgẈ+2/ḣ
A monadic Link accepting an integer, n, which yields a list of the first n values.
How?
ḤB€FŒgẈ+2/ḣ - Link: integer, n
Ḥ - double (n)
€ - for each v in (implicit range = [1..2n]):
B - (v) to binary
F - flatten
Œg - group runs
Ẉ - get lengths
2/ - 2-wise reduce by:
+ - addition
ḣ - head to index (n)
Octave, 62 bytes
@(n)diff(regexp([arrayfun(@dec2bin,1:4*n,'un',0){:}],'1+'))(n)
Explanation
@(n) % function with input n
1:4*n % range [1, 2, ... 4*n]
arrayfun(@dec2bin, ,'un',0) % convert each to binary string
[ {:}] % concat into one string
regexp( ,'1+') % starting indices of runs of 1's
diff( ) % consecutive differences
(n) % take n-th entry
C (gcc), 124 \$\cdots\$ 109 104 bytes
Saved 2 3 4 8 9 14 bytes thanks to Arnauld!!!
c;t;b;i;f(n){for(i=c=0,t=1;++i;){for(b=0;i>>++b;);for(;b--;++c)if(t^i>>b&1&&(t^=1)?c*=!--n:0)return c;}}
Goes through positive integers \$i\$ catching transitions from \$0\$ to \$1\$ as it rolls through the non-leading-zero bits of the \$i\$'s.
Returns the \$n^\text{th}\$ term, 1-indexed.
Japt, 11 bytes
Outputs the nth 1-indexed term.
g°U²ô¤¬ò<)l
g°U²ô¤¬ò<)l :Implicit input of integer U
g :Index into
°U : Increment U
² : Square it
ô : Range [0,result]
¤ : To binary strings
¬ : Join
ò< : Partition after characters that are less than the next
) :End indexing
l :Length
Haskell, 80 bytes
([1..]>>=f)#0
f 0=[]
f x=f(div x 2)++[mod x 2]
(0:1:x)#l=l+1:x#1
(a:x)#l=x#(l+1)
Inspired by Leo's Husk answer, calculates an infinite list.
Haskell, 135 128 bytes
- Saved seven bytes thanks to ovs.
g$b=<<[1..]
b 0=[];b n=b(div n 2)++[mod n 2]
l(1:r)1=1+l r 1;l(0:r)0=1+l r 0;l(0:r)1=1+l r 0;l(1:r)0=0
g a=l a 1:g(drop(l a 1)a)
PHP, 108 bytes
for($a=[$p=$i=1];;$p=$c,$o++){if(!$a)$a=str_split(decbin(++$i));if($p<$c=array_shift($a)){echo$o,',';$o=0;}}
Will print the sequence indefinitely.
K (ngn/k), 26 bytes
{x##'(&0>':t)_t:,/2\'!2*x}
Returns the first n items.
J, 35 bytes
{[:((1,2</\])#;.1])@;[:#:&.>[:i.3&*
Returns the nth item
Perl 5 -n, 73 bytes
$_=join'',map{sprintf"%b",$_}1..($n=$_)*2;say y///c for(/1+0+/g)[0..$n-1]
Takes input n via stdin, prints the first n numbers in the sequence.
Factor, 92 bytes
: f ( n -- n ) dup 3 * [0,b] [ >bin ] map concat "01" " " replace " " split nth length 2 + ;
Red, 122 111 bytes
func[n][b: copy""repeat i 2 * n[append b find enbase/base
to#{}i 2"1"]parse b[n copy i[any"1"any"0"]]length? i]
05AB1E, 9 bytes
∞bSγ2ôεSg
Untested, since TIO isn't working.. >.> But it should work (unless one of those builtins used isn't lazy).
I'll try to finally install 05AB1E locally later today to verify if it indeed works.
EDIT: Installed 05AB1E locally, and apparently it didn't work due to the Join on the infinite list. So here an alternative 9-byter that does actually work.
Outputs the infinite sequence.
Explanation:
∞ # Push an infinite list of positive integers: [1,2,3,4,5,6,...]
b # Convert each to a binary string
# → ["1","10","11","100","101","110",...]
S # Convert it to a flattened list of digits
# → [1,1,0,1,1,1,0,0,1,0,1,1,1,0,...]
γ # Split them into parts of consecutive equal digits
# → [[1,1],[0],[1,1,1],[0,0],[1],[0],[1,1,1],[0],...]
2ô # Split all that into parts of size 2
# → [[[1,1],[0]],[[1,1,1],[0,0]],[[1],[0]],[[1,1,1],[0]],...]
ε # Map over each pair
S # Convert it to a flattened list of digits again
# → [[1,1,0],[1,1,1,0,0],[1,0],[1,1,1,0],...]
g # Pop and push its length
# → [3,5,2,4,...]
# (after which the mapped infinite list is output implicitly as result)
Python, 77 67 bytes
lambda n:len(''.join(f'{i:b}'for i in range(9*n)).split('01')[n])+2
Returns the \$n^\text{th}\$ term, 1-indexed.
Jelly, 15 14 bytes
×3ŻBFœṣØ.ḊẈ+2ḣ
Try it online! Thanks to @JonathanAllan and @NickKennedy for helping me out, in chat, to finish this solution. I came up with ×3RBFœṣØ.Ẉ+2ḣ but that fails for n = 1!
How it works:
×3ŻBFœṣØ.ḊẈ+2ḣ Monadic link: takes `n` as input and returns the first `n` terms
×3 Multiply input by three and
Ż create the list [0, 1, ..., 3n].
B Get the binary representation of each number and
F flatten to get [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, ...]
Now we find the /1+0+/ patterns by looking at occurrences of [0, 1],
i.e. when one pattern ends and the next begins:
œṣ Split the [0, 1, 1, 0, 1, 1, 1, 0 ...] list at occurrences of
Ø. [0, 1], so [0, 1, 1, 0, 1, 1, 1, 0 ...] -> [[], [1], [1, 1, ...], ...]
Ḋ and drop the first element of the resulting list (the empty one).
Ẉ Finally we get the length of each sublist,
+2 add 2 (to compensate for the lost 1 and 0),
ḣ and take the first `n` elements of that.
Charcoal, 34 22 bytes
≔…⌕A⭆⊗⊕θ⍘ι²01⊕θηI⁻⊟η⊟η
Try it online! Link is to verbose version of code. Based on @LuisMendo's observation that the numbers up to 2n provide sufficient digits, although I search for 01 so I actually need 0 through 2n+1. Explanation:
⭆⊗⊕θ⍘ι²
Convert all the numbers from 0 to 2n+1 to base 2 and concatenate them.
≔…⌕A...01⊕θη
Find the positions of the substrings 01 but truncated after the nth entry.
I⁻⊟η⊟η
Output the difference between the last two positions.
MATL, 15 bytes
E:"@B]v&Y'2esG)
This takes n as input and outputs the n-th term, 1-indexed.
Explanation
A binary pattern of the specified form ends at least as often as every even number. So for input n, considering the numbers 1, 2, ..., 2*n guarantees that at least n patterns are obtained.
E % Implicit input: n. Push 2*n
:" % For each k in [| 2 ... 2*n]
@ % Push k
B % Binary expansion. Gives a row vector containing 1's and 0's
] % End
v % Concatenate everything into a column vector
&Y' % Lengths of run-length encoding. Runs contain 1's and 0's alternately
2e % Reshape as a two-column matrix, in column-major order
s % Sum of each column. This gives the lenghts of the desired patterns
G) % Take the n-th entry. Implicit display
Jelly, 12 11 bytes
ḤB€FI»0kƲẈḣ
A monadic link taking an integer \$n\$ and returning the first \$n\$ terms of the series.
Change from ×9 to Ḥ inspired by @JonathanAllan’s answer. Thanks!
Husk, 7 bytes
mLġ≤ṁḋN
Takes no input and prints ALL the numbers!
Explanation
mLġ≤ṁḋN
N The list of all positive integers [1,2,3...]
ṁḋ Convert each to binary and concatenate the resulting digits
ġ≤ Split them in groups where each digit is less than or equal to the previous one (basically cuts wherever there is a 0 followed by a 1)
mL Compute the length of each group