# A bit of a digital XOR

Here are the first 100 numbers of a sequence:

1,2,33,4,55,66,777,8,99,11,111,12,133,141,1515,1,11,18,191,22,222,222,2232,24,252,266,2772,282,2922,3030,31313,3,33,33,335,36,377,383,3939,44,441,444,4443,444,4455,4464,44747,48,499,505,5151,522,5333,5445,55555,565,5757,5855,59559,6060,61611,62626,636363,6,66,66,676,66,666,770,7717,72,737,744,7557,767,7777,7878,79797,88,888,882,8838,888,8888,8886,88878,888,8898,9900,99119,9929,99399,99494,995959,96,979,988,9999,100


How does this sequence work?

n:            1 2  3  4   5   6   7   8    9    10   11   12   13   14   15   16    17
binary:       1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111 10000 10001
n extended:   1 22 33 444 555 666 777 8888 9999 1010 1111 1212 1313 1414 1515 16161 17171
1-bit digits: 1 2  33 4   5 5 66  777 8    9  9 1 1  1 11 12   13 3 141  1515 1     1   1
result:       1 2  33 4   55  66  777 8    99   11   111  12   133  141  1515 1     11


As you can see, the steps to get the output are as follows:

1. Convert integer $$\n\$$ to a binary-string.
2. Extend integer $$\n\$$ to the same length as this binary-string. (I.e. $$\n=17\$$ is 10001 in binary, which has a length of 5. So we extend the 17 to this same length of 5 by cycling it: 17171.)
3. Only keep the digits in the extended integer $$\n\$$ at the positions of the 1s in the binary-string.
4. Join them together to form an integer.

## Challenge:

One of these options:

1. Given an integer $$\n\$$, output the $$\n^{\text{th}}\$$ number in the sequence.
2. Given an integer $$\n\$$, output the first $$\n\$$ numbers of this sequence.
3. Output the sequence indefinitely without taking an input (or by taking an empty unused input).

## Challenge rules:

• Step 4 isn't mandatory to some extent. You're also allowed to output a list of digits, but you aren't allowed to keep the falsey-delimiter. I.e. $$\n=13\$$ resulting in [1,3,3] or "1,3,3" instead of 133 is fine, but "13 3", [1,3,false,3], [1,3,-1,3], etc. is not allowed.
• Although I don't think it makes much sense, with option 1 you are allowed to take a 0-based index $$\m\$$ as input and output the $$\(m+1)^{\text{th}}\$$ value.
• If you output (a part of) the sequence (options 2 or 3), you can use a list/array/stream; print to STDOUT with any non-digit delimiter (space, comma, newline, etc.); etc. Your call. If you're unsure about a certain output-format, feel free to ask in the comments.
• The input (with options 1 and 2) is guaranteed to be positive.
• You'll have to support at least the first $$\[1, 10000]\$$ numbers. $$\n=\text{...},9998,9999,10000]\$$ result in $$\\text{...},9899989,99999999,10010]\$$ (the largest output in terms of length within this range is $$\n=8191 → 8191819181918\$$).

## General rules:

• This is , so 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.

PS: For the 05AB1E code-golfers among us, 4 bytes is possible.

• I was hoping that the 4-byte 05AB1E answer would look like the word base.
– user92069
Mar 18, 2020 at 12:37
• @a'_' Hehe, unfortunately not. It kinda spells 'pibi' or 'psbi' I guess. ;p Mar 18, 2020 at 12:39
• I don't know 05AB1E, but Jelly has a 4-byte solution as well. No idea if I could make it shorter, though.
– RGS
Mar 18, 2020 at 13:06
• @RGS Yeah, I saw your 4-byter in Jelly. Already +1-ed it. :) The 05AB1E approach I had prepared was different though. Dorian just posted it as an answer. Mar 18, 2020 at 13:09
• The terminology people use is surprising sometimes. I'm used to thinking about integers as already being in binary, and the special thing is working with their decimal digits which goes without any mention here. Unless we're allowed to work in our choice of base, like hex, or perhaps more convenient base256 i.e. chunks of 8 bits = 1 byte or base 2^32? Maybe a challenge where AVX512 machine code's large instructions could actually be non-terrible, using hardware left-packing of 32-bit integers according to a bitmask. Mar 19, 2020 at 23:01

# Wolfram Language (Mathematica), 72 bytes

Pick[Flatten[(i=IntegerDigits)/@Table[#,s=Length[p=#~i~2]]][[;;s]],p,1]&


Here is the plot of the first 30.000 such numbers

And here is the Logarithmic plot # Jelly, 4 bytes

BTịD


Try it online, code that computes the $$\n\$$th term of the sequence, or check the first 100 terms!

How it works:

B     convert number to binary, i.e. 5 -> [1, 0, 1]
T    keep the indices of the Truthy elements, i.e. [1, 0, 1] -> [1, 3]
ị   and then index safely into...
D  the decimal digits of the input number


By "index safely" I mean that indices out of range are automatically converted into the correct range!

• I might start considering porting this answer. Good job!
– user92069
Mar 18, 2020 at 11:57
• Byte for byte what I tested with when assessing the sandboxed post :) Mar 18, 2020 at 21:22
• @JonathanAllan I hope that means I found the optimal solution and not that you think I copied your answer or something like that D:
– RGS
Mar 18, 2020 at 23:00
• These golfing languages never cease to amaze me Mar 18, 2020 at 23:31
• I think you did find the optimal solution. I didn't post it so copying it would have been impressive! Mar 19, 2020 at 0:12

# Python 3, 80 $$\\cdots\$$ 52 53 bytes

Saved a 2 bytes thanks to Jitse!!!
Saved 7 6 bytes thanks to Surculose Sputum!!!
Added a byte to fix bugs kindly point out by Jitse and Surculose Sputum.

lambda n:[c for c,d in zip(str(n)*n,f'{n:b}')if'0'<d]


Try it online!

Returns the $$\n^{\text{th}}\$$ number in the sequence as a list of digits.

• @Arnauld Should be correct now. Mar 18, 2020 at 11:32
• 59 bytes Mar 18, 2020 at 11:47
• @Jitse Very sweet - thanks! :-) Mar 18, 2020 at 11:49
• You can return a list of digits instead, which saves the cost of joining. Mar 18, 2020 at 12:01
• @SurculoseSputum Thanks, wasn't sure about that. Great minds think alike, yeah! :D Mar 18, 2020 at 12:07

# J, 13 10 bytes

#:##@#:$":  Try it online! # 05AB1E, 4 bytes ×IbÏ  Try it online! Yeah, I found the mysterious 4-byte 05AB1E answer :D × expand the input digits (input 123 -> 123123123123123... ) Ib get the binary value of input (123 -> 1111011) Ï keep only the digits where the corresponding binary digit is 1  • Ah nice. I actually had Þ instead of ×, with a list of digits as output. But I actually like your approach more, since the output is a single joined string. :) Mar 18, 2020 at 13:08 • Actually, I tried to find the Þ function, but I didn't know what to search in the info.txt :D Mar 18, 2020 at 13:11 # APL (dzaima/APL), 7 bytes ⊤⌿≢∘⊤⍴⍕  Try it online! ### How it works ⊤⌿≢∘⊤⍴⍕ ⍝ Input: n ≢∘⊤ ⍝ Length of base-2 digits ⍴⍕ ⍝ Repeat the digits of n (as a string) to the length of above ⊤⌿ ⍝ Take the digits where the corresponding base-2 digit is 1  # APL (Dyalog Unicode), 16 bytes ⍕(∊⊢⊆⍴⍨∘≢)2∘⊥⍣¯1  Try it online! ### How it works ⍕(∊⊢⊆⍴⍨∘≢)2∘⊥⍣¯1 ⍝ Input: n 2∘⊥⍣¯1 ⍝ Binary digits of n ⍕ ⍝ Stringify n ( ) ⍝ Inner function with the two args above ∘≢ ⍝ Length of binary digits ⍴⍨ ⍝ Cycle the string digits to the length ∊⊢⊆ ⍝ Filter the digits by the binary digits  • Incredibly done! Beats my Dyalog answer by eons, and I really spent a lot time on it. Also, I must admit I didn’t realize dzaima’s dialect could make it so much shorter! Which properties/operators in particular allowed you to take such a different (and superior) approach in dzaima’s APL extension? Mar 19, 2020 at 1:31 • @AviF.S. Actually it is the same approach. It's just that monadic ⊤ in the extension means exactly 2∘⊥⍣¯1, and ⌿ is a pure function "replicate" rather than a mixed function/operator. ⊤ is shared between various extensions, but pure function ⌿ is unique to dzaima's (which is usually the sole reason to choose the particular extension). Mar 19, 2020 at 1:37 • @AviF.S. See the discussion here. – Adám Mar 19, 2020 at 7:01 # JavaScript (ES6), 55 bytes n=>n.toString(2).replace(/./g,(d,i)=>+d?(n+=[n])[i]:'')  Try it online! ### Commented n => // n = input n.toString(2) // convert n to a binary string .replace( // replace: /./g, // for each (d, i) => // digit d at position i: +d ? // if d is '1': (n += [n]) // coerce n to a string (if not already done) // and double its size to make sure we have enough digits [i] // extract the i-th digit : // else: '' // discard this entry ) // end of replace()  # Python 2, 52 bytes lambda n:[c for c,i in zip(n*n,bin(n)[2:])if'0'<i]  Try it online! Input: An integer $$\n\$$ Output: The $$\n^{th}\$$ numbers in the sequence, in the form of a list of digits. How: • bin(n) is the binary string of n, e.g bin(2) is "0b10". Thus bin(n)[2:] is the binary string of n without the 0b. • n*n creates the n-extended string by repreating the decimal string of n n times. This is longer than needed, but that's ok because extra characters will be truncated later. • c,i in zip(n*n,bin(n)[2:]) takes each pair of corresponding characters c,i from the binary string and the n-extended string. • if'0'<i checks if i is the character "1", if so the corresponding character c is kept in the result list. # C (gcc), 101 $$\\cdots\$$ 96 91 bytes Save a 6 bytes thanks to ceilingcat!!! b;i;f(n){char s[n];for(b=1;i=n/b;b*=2);for(;b/=2;++i)b&n&&putchar(s[i%sprintf(s,"%d",n)]);}  Try it online! Outputs the $$\n^{\text{th}}\$$ number in the sequence. # APL (Dyalog Unicode), 25 24 bytes ## Code {b←2∘⊥⍣¯1⋄(b⍵)/(⍴b⍵)⍴⍕⍵} ### Explanation { ⍝ Start function definition b ← 2∘⊥⍣¯1 ⍝ Let b ← binary conversion function ⋄ ⍝ Start new clause (b⍵) ⍝ Binary representation of ⍵ (input) / ⍝ Mask boolean list over following string (⍴b⍵) ⍝ Length of boolean representation of ⍵ ⍴ ⍝ Reshape ⍕⍵ ⍝ Stringify ⍵ } ⍝ End function definition  ### Binary Conversion This is all much longer than one would expect from APL and is due to the lack of a concise binary conversion function. Unfortunately, the above is the best we can do. Below is the breakdown: • 'Power' (⍣) does an operation n times. So f⍣¯1 calculates the inverse of f, if it can. • 'Decode' (⊥) converts from an arbitrary base back to decimal; 2 ⊥ 1 1 0 1 returns 13. • 'Jot' (∘) can compose two functions as in (f∘g) 3 or curry as in(1∘+) 3. Together, 2∘⊥⍣¯1 denotes the inverse of the function that converts from binary to decimal. (Two left-curried with the encoding function, 2∘⊥, converts binary to decimal.) • Welcome to PPCG and nice first answer! You can try converting the function into a train to save some bytes Mar 18, 2020 at 14:07 • Hi, welcome to CGCC! Nice first answer. I don't know APL, but why is the entire code in the input-section instead of code section? Usually we'd have a full program or function, and the input is than taken through STDIN, System-arguments, or function arguments/parameters. Mar 18, 2020 at 14:49 • @user41805 The / function is often problematic in trains. – Adám Mar 18, 2020 at 14:55 • @Adám It can be circumvented with (/⍨⍨) Mar 18, 2020 at 15:06 • @user41805 Thanks! I know it looks likes it's begging to be trainified but I was unable to make it any shorter. If you can golf it further, please do comment; I'll keep looking as well as I'm not completely happy with it. Mar 18, 2020 at 15:47 # Ruby, 68 bytes ->n{n.to_s(2).gsub(/./).with_index{|b,i|b>?0?(n.to_s*n)[i]:""}.to_i}  Try it online! Returns the nth number in the sequence. I'm no expert golfer, so it's undoubtedly possible there's a better Ruby solution, but I'm (not altogether unpleasantly) surprised to see a challenge where Python and JavaScript both outperform Ruby. I guess python's list comprehensions are a perfect fit for this challenge, and JavaScript passing the index as a parameter to the replace method is very convenient. # APL+WIN, 25 bytes Prompts for integer n and outputs nth term ((b⍴2)⊤n)/(b←1+⌊2⍟n)⍴⍕n←⎕  Try it online! Coutesy of Dyalog Classic # Red, 131 bytes func[n][i: 0 remove-each _ t: take/part append/dup t: to""n n |: length? s: find to""enbase/base to#{}n 2"1"|[s/(i: i + 1) =#"0"]t]  Try it online! # PHP, 758681 73 bytes for(;$i<strlen($d=decbin($a=$argn));$i++)if($d[$i])echo$a[$i%strlen($a)];  Try it online! Gives the nth number. Original version didn't handle 0's in input correctly. # 05AB1E, 4 bytes ∍IbÏ  Try it online! ### How? ∍IbÏ - Full program expecting a single input e.g. 13 stack: ∍ - extend a to length b (stack empty so a=b=input)  I - push the input [1313131313131, 13] b - convert to binary [1313131313131, 1101] Ï - a where b is 1  - implicit output 133  • I'm not used to you posting 05AB1E answers. :) Btw, not sure if you had noticed it, but it's rather similar as this existing 05AB1E answer. Of course it's fine since you came up with it independently, but figured I'd let you know in case you missed it. Mar 18, 2020 at 21:30 • Yeah, I saw not long after I posted (I originally had s rather than I too, but realised I was more natural) I didn't notice x when making it either. (I found this during sandboxing BTW) Mar 18, 2020 at 21:50 • Well, your ∍ is probably slightly better for memory usage than x anyway, since 100 100x would be 10,000 characters long, whereas 100 100∍ would be 100 characters long. :) Mar 18, 2020 at 21:54 • Ah, reading "expand" and "123123..." I assumed it was a lazy infinite generator :) Mar 18, 2020 at 22:03 • That would be Þ ;) Although it implicitly converts it to a list of characters/digits. My prepared 4-byter was actually ÞIbÏ, but I like the approach with x or ∍ actually more, since the output is than a single string/number instead of a list of characters/digits. Mar 18, 2020 at 22:10 # Perl 5 -n, 75 bytes map{$i=0;@b=split//,sprintf"%b",$_;say@s=grep{$b[$i++]}split//,$_ x@b}1..$_  Try it online! Prints the first n numbers in the sequence # Perl 5 -nl, 60 bytes @b=split//,sprintf"%b",$_;say@s=grep{$b[$i++]}split//,$_ x@b  Try it online! Shorter version that just prints the nth number • You can cut the latter entry down to 55 bytes Oct 19, 2020 at 18:13 # Rust, 131 129 bytes |n|format!("{:b}",n).chars().zip(format!("{}",n).chars().cycle()).flat_map(|(b,c)|if'0'<b{Some(c)}else{None}).collect::<String>()  Works according to option 1 and returns the $$\n^{\text{th}}\$$ number of the sequence as a string. -2 thanks to Kevin Cruijssen! ## Explanation |n| // Closure taking a parameter n format!("{:b}",n) // Binary string of n .chars() // Iterate over the chars .zip( // Zip iterator with format!("{}",n) // Decimal string of n .chars().cycle() // Cycle over the chars ) .flat_map( // Map with the following iterator-returning // function and flatten the result |(b,c)| // Closure taking the char pairs (b,c) if'0'<b{Some(c) // If '1' then return an iterator yielding c else{None} // Else return an empty iterator ) .collect::<String>() // Evaluate into a string  • Nice answer! The if b=='1' can apparently be if'0'<b for -2 bytes. :) Nov 6, 2021 at 12:07 • @KevinCruijssen thanks for the tip! Nov 6, 2021 at 16:37 # C (gcc), 79 bytes V;M;r(n){M<=V?r(n/10?:(M*=2,V)),M/=2,M&V&&putchar(n%10+48):0;}f(n){M=1;r(V=n);}  Try it online! Generates the nth number # Ruby, 58 bytes ->n{a=n.digits 2;([n]*n*m='').chars{|x|m<<x*(a.pop||0)};m}  Try it online! # Bash + GNU utilities, 87 bytes x=$1$1$1$1 for((b=dc<<<2o$1p;b;)){ [ $[b] =$b ]&&printf ${x:0:1};x=${x:1};b=${b:1};}  Try the test suite online! Input $$\n\$$ is passed as an argument, and the $$\n^\text{th}\$$ number in the sequence is output on stdout. How it works: x is set to 4 copies of the input in a row, which is more than enough digits to match the binary equivalent of the input. (A number in base 2 can never be longer than 4 times its representation in base 10, since $$\\log_2(10)<4.\$$) b is initialized to the binary representation of the input. The for loop repeats the following as long as b still has at least one 1 in it: • If b doesn't start with a 0, then the first character in x is printed. • The first character is chopped off of x and b. The golfiest trick is probably the way I check to see if b starts with a 1: the expression $[b] means: b evaluated as an arithmetic expression. This will omit any initial 0s (except that it will keep a final 0 if all the characters in b are 0). So [ $[b] = b ] is true iff b either starts with a 1 or is equal to "0". But b can't equal "0" since the loop termination condition would have been true in that case, and the loop would have ended already. # Java (JDK), 108 bytes n->{var s=""+n;for(int b=n.highestOneBit(n),i=0;b>0;b/=2,i++)if((b&n)>0)System.out.print((s+=s).charAt(i));}  Try it online! ## Credits • -7 bytes thanks to Kevin Cruijssen • @KevinCruijssen Nice idea to repeat that way! Mar 19, 2020 at 13:46 • I agree. Not my idea btw, but Arnauld's. When he posted his answer I had to verify whether there was some integer with a binary pattern 10...0...01 for which this might fail, but apparently not. 9 results in exactly enough digits with -> 99 -> 9999, and all integer above that concatenated four times are larger (in terms of length) than their binary-string. Mar 19, 2020 at 13:49 # Husk, 5 bytes fḋ¹¢s  Try it online! This function works according to option 1, outputting the term as a string. ### Explanation fḋ¹¢s (Let X denote the argument.) f Select the elements of s the string representing X, ¢ cycled infinitely, corresponding to truthy values of ḋ¹ the binary digits of X.  # Japt, 8 bytes Came up with a few approaches but couldn't do better than 8 bytes. With output as a digit array: ¤¬ðÍ£sgX  Try it With output as a string: ¤ËÍçEgUs  Try it ¤¬ðÍ£sgX :Implicit input of integer U ¤ :To binary string ¬ :Split ð :Truthy indices when Í : Converted to integer £ :Map each X s : Convert U to string gX : Get digit at index X  ¤ËÍçEgUì :Implicit input of integer U ¤ :To binary string Ë :Map each D at index E Í : Convert D to integer ç : That many times repeat Eg : Index E into Uì : Digit array of U  # Vyxals, 17 bytes ₌SbL:‟*Ẏf?bZ't;vh  Try it Online! A mess. # AWK, 89 bytes {for(f=b=1;$1>=b;e=e$1)c[d++]=and($1,b)/(b*=2);for(;d--;f++)c[d]?g=g substr(e,f,1):0}$0=g  Try it online! Not that short, but AWK doesn't have a print format to generate binary strings from integers, so it has to iterate to get that info... At a high level, one loop uses bitwise and operations with a single bit moved one position to the left each time to built an array of "binary" settings. It also builds up a string composed of multiple copies of the N number while it's looping. AWK doesn't have a nice string*number operator either. Then the second loop works backwards through that array and for each entry which is 1, it appends the appropriate character to a "results" accumulator. The final step just prints the accumulated string. # Loop 1, build the "binary" array and string of duplicated "N" characters for(f=b=1;$1>=b;e=e$1)c[d++]=and($1,b)/(b*=2);
(f=b=1;                                     # Loop init, "f" is used in loop #2
$1>=b; # Exit test, goes until bit check > N e=e$1)                         # End of loop, build "N dup string
c[d++]=and($1,b)/(b*=2); # Body, does a couple of things... # d++ : increment bit position # and($1,b) : extract bit
# /(b*=2) : normalize, then shift bit
# c[d++]= : add to "binary" array

# Loop 2, accumulate chars associated with set bits
for(;d--;f++)c[d]?g=g substr(e,f,1):0
d--;                             # Exit test, when all bits checked stop
f++)                         # End of loop, increment char pos in "N" dup str
c[d]?                 :  # Ternary, code runs if bit is set
g=g substr(e,f,1)   # Append current char to accumulator
0 # No-op "else" from ternary

# Print the result
$0=g # Typical AWK golf trick, assign "$0" to what you want to print w/o code block


# Charcoal, 11 bytes

⭆↨Ｉθ²⎇ι§θκω


Try it online! Link is to verbose version of code. Explanation:

   θ        Input as a string
Ｉ         Cast to integer
↨  ²       Convert to base 2
⭆           Map over digits
ι     Current digit
⎇      If non-zero
θ   Input as a string
§    Cyclically indexed by
κ  Current index
ω Else empty string


# 05AB1E, 6 bytes

The Ï< ruins the consecutive word bāsè... (If you don't get it, the hex code 05AB1E converted to base64 would result in base.)

bāsÏ<è


Try it online!

# Explanation

b      To base 2
ā     Length-range to 1
s    Prepend
Ï   Keep all that's truthy
<  -1 due to 0-based indexing ... that's terrible!
è Modular Indexing

• Great, +1 in that case (and I like how it -almosts- spells 'base'). PS: As mentioned at the bottom of my question, 4 bytes is possible in 05AB1E. ;) Mar 18, 2020 at 12:26