18
\$\begingroup\$

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.
  • Please state which of the three options you've used in your answer.
  • 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.
  • If possible, please add a link with a test for your code (i.e. TIO).
  • Also, adding an explanation for your answer is highly recommended.

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

\$\endgroup\$
  • \$\begingroup\$ I was hoping that the 4-byte 05AB1E answer would look like the word base. \$\endgroup\$ – petStorm Mar 18 at 12:37
  • \$\begingroup\$ @a'_' Hehe, unfortunately not. It kinda spells 'pibi' or 'psbi' I guess. ;p \$\endgroup\$ – Kevin Cruijssen Mar 18 at 12:39
  • \$\begingroup\$ I don't know 05AB1E, but Jelly has a 4-byte solution as well. No idea if I could make it shorter, though. \$\endgroup\$ – RGS Mar 18 at 13:06
  • \$\begingroup\$ @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. \$\endgroup\$ – Kevin Cruijssen Mar 18 at 13:09
  • \$\begingroup\$ 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. \$\endgroup\$ – Peter Cordes Mar 19 at 23:01

22 Answers 22

9
\$\begingroup\$

Wolfram Language (Mathematica), 72 bytes

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

Try it online!

Here is the plot of the first 30.000 such numbers

enter image description here

And here is the Logarithmic plot

enter image description here

|improve this answer|||||
\$\endgroup\$
5
\$\begingroup\$

J, 13 10 bytes

#:##@#:$":

Try it online!

|improve this answer|||||
\$\endgroup\$
5
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ @Arnauld Should be correct now. \$\endgroup\$ – Noodle9 Mar 18 at 11:32
  • \$\begingroup\$ @Jitse Nice one - thanks :-) \$\endgroup\$ – Noodle9 Mar 18 at 11:38
  • \$\begingroup\$ 59 bytes \$\endgroup\$ – Jitse Mar 18 at 11:47
  • \$\begingroup\$ @Jitse Very sweet - thanks! :-) \$\endgroup\$ – Noodle9 Mar 18 at 11:49
  • \$\begingroup\$ You can return a list of digits instead, which saves the cost of joining. \$\endgroup\$ – Surculose Sputum Mar 18 at 12:01
4
\$\begingroup\$

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()
|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

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!

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

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.
|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. :) \$\endgroup\$ – Kevin Cruijssen Mar 18 at 13:08
  • 3
    \$\begingroup\$ Actually, I tried to find the Þ function, but I didn't know what to search in the info.txt :D \$\endgroup\$ – Dorian Mar 18 at 13:11
4
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
4
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – Avi F. S. Mar 19 at 1:31
  • \$\begingroup\$ @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). \$\endgroup\$ – Bubbler Mar 19 at 1:37
  • \$\begingroup\$ @AviF.S. See the discussion here. \$\endgroup\$ – Adám Mar 19 at 7:01
3
\$\begingroup\$

APL (Dyalog Unicode), 25 24 bytes

Code

{b←2∘⊥⍣¯1⋄(b⍵)/(⍴b⍵)⍴⍕⍵}

Try it online!

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.)

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG and nice first answer! You can try converting the function into a train to save some bytes \$\endgroup\$ – user41805 Mar 18 at 14:07
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Mar 18 at 14:49
  • \$\begingroup\$ @user41805 The / function is often problematic in trains. \$\endgroup\$ – Adám Mar 18 at 14:55
  • \$\begingroup\$ @Adám It can be circumvented with (/⍨⍨) \$\endgroup\$ – user41805 Mar 18 at 15:06
  • \$\begingroup\$ @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. \$\endgroup\$ – Avi F. S. Mar 18 at 15:47
3
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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!

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

PHP, 75 86 81 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.

|improve this answer|||||
\$\endgroup\$
2
\$\begingroup\$

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)       [1313131313131]
 I   - push the input                                        [1313131313131, 13]
  b  - convert to binary                                     [1313131313131, 1101]
   Ï - a where b is 1                                        [133]
     - implicit output                                       133
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Mar 18 at 21:30
  • \$\begingroup\$ 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) \$\endgroup\$ – Jonathan Allan Mar 18 at 21:50
  • \$\begingroup\$ 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. :) \$\endgroup\$ – Kevin Cruijssen Mar 18 at 21:54
  • \$\begingroup\$ Ah, reading "expand" and "123123..." I assumed it was a lazy infinite generator :) \$\endgroup\$ – Jonathan Allan Mar 18 at 22:03
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Mar 18 at 22:10
1
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

Ruby, 58 bytes

->n{a=n.digits 2;([n]*n*m='').chars{|x|m<<x*(a.pop||0)};m}

Try it online!

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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.

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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

|improve this answer|||||
\$\endgroup\$
1
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ @KevinCruijssen Nice idea to repeat that way! \$\endgroup\$ – Olivier Grégoire Mar 19 at 13:46
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen Mar 19 at 13:49
0
\$\begingroup\$

Charcoal, 11 bytes

⭆↨Iθ²⎇ι§θκω

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

   θ        Input as a string
  I         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
|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

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
|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ 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. ;) \$\endgroup\$ – Kevin Cruijssen Mar 18 at 12:26

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.