37
\$\begingroup\$

(Challenge taken from a multiplayer game (clash of code) at codingame.com)

The challenge

Find the n-th term of the following sequence: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4... or, to make it more obvious, {1}, {1,2}, {1,2,3}, {1,2,3,4}...

The sequence is made up from concatenated ranges from 1 to x, starting from 1, all the way up to infinity.

Rules / IO

Input and output can be in any format, as long as it's distinguishable. Input can be taken from any appropriate source: STDIN, file, etc...

The input can be 0- or 1-indexed, and the selected indexing must be mentioned in the post.

You will have to handle at least up to a result of 255 inclusive (meaning the 0-indexed maximum input is 32640). Anything over that has to be handled, if your language supports it.

This is code-golf so the shortest byte count wins!

Test cases (0-based indexing)

0 -> 1
1 -> 1
5 -> 3
10 -> 1
59 -> 5
100 -> 10
1001 -> 12
\$\endgroup\$
  • 11
    \$\begingroup\$ OEIS \$\endgroup\$ – Gurupad Mamadapur Jan 22 '17 at 14:44
  • 4
    \$\begingroup\$ You should probably add a few more larger test cases (59, 100, etc) \$\endgroup\$ – FlipTack Jan 22 '17 at 16:07
  • \$\begingroup\$ Related: codegolf.stackexchange.com/questions/103670/… \$\endgroup\$ – JAD Jan 23 '17 at 9:27
  • \$\begingroup\$ It's the challenge in reverse. The best answers from that challenge work in a way that couldn't be reversed. @JarkoDubbeldam \$\endgroup\$ – devRicher Jan 23 '17 at 12:45
  • \$\begingroup\$ @devRicher I know, just putting it out there and it wasn't meant negatively. My own answer there actually was reversable. Related != duplicate. \$\endgroup\$ – JAD Jan 23 '17 at 14:27

41 Answers 41

1
\$\begingroup\$

Pushy, 11 bytes

1-indexed implementation.

R&:{R;&:{;#

Try it online!

\$\endgroup\$
0
\$\begingroup\$

APL, 9 bytes

{⍵⊃∊⍳¨⍳⍵}

Explanation:

⍵⊃           ⍝ ⍵'th element of
  ∊          ⍝ concatenated elements of
   ⍳         ⍝ each list from 1 to N 
    ¨        ⍝ for each N in 
     ⍳⍵      ⍝ list from 1 to ⍵
\$\endgroup\$
0
\$\begingroup\$

Batch, 55 bytes

@set/am=%2+1,n=%1-m
@if %n% gtr 0 %0 %n% %m%
@echo %1

1-indexed. Like some of the other recursive answers, this keeps track of which range it's in using a second argument that defaults to the empty string. This means that m equals 1 on the first pass. The loop ends when n falls below 1 in which case the previous value of n is the answer.

\$\endgroup\$
0
\$\begingroup\$

Scala, 45 bytes

(n:Int)=>Stream.from(1)flatMap(1 to _)apply n

0-indexed.

\$\endgroup\$
0
\$\begingroup\$

dc, 47 bytes, 0 indexed

?0sb1se[0sble1+se]sf[lb1+dsble=f1-d0!>c]dscxlbp

Try It Online!

Explanation

This explanation assumes that the input is 100.

?                                               # Ask for inout and store it on top of the main stack. 
                                                # Main = [100].
 0sb1se                                         # Store 0 on top of register "b" and 1 on top of register "e" to be referenced later. 
                                                # b = [0], e = [1], Main = [100].
       [0sble1+se]sf                            # Store the macro "0sble1+se" on top of register "f". 
                                                # f = [0sble1+se], b = [0], e = [1], Main = [100].
                    [lb1+dsble=f1-d0!>c]dscx    # Store the macro "lb1+dsble=f1-d0!>c" on top of Main stack, duplicate it, and then store one copy on top of register "c" and then immediately executing the other copy as a dc program. 
                                                # c = [lb1+dsble=f1-d0!>c], f = [0sble1+se], b = [0], e = [1], Main = [100]

================================================================================================================================================================================================================================================

Upon invocation of the macro `lb1+dsble=f1-d0!>c`:

    lb1+dsble            # Load (not pop) the value off of the top of register "b" on top of the main stack, add 1 to it, duplicate the sum, and then push one copy to the top of register "b". 
                         # Then, load the value off of the top of "e" onto the main stack.
                         # b = [0,1], e = [1], Main = [100,1,1].
             le=f        # Now, pop the top 2 values (1 and 1), compare them, and invoke the macro on top of register "f" if both are equal. In this case, it is invoked, since 1==1.
                         # b = [0,1], e = [1], Main = [100].

    ======================================================================================================================================================================================

     If the macro on top of "f" (`0sble1+se`) is invoked:

         0sble1+se # Push 0 to the top of the Main stack. Then, push it to the top of register "b", resetting the sequence, after which the value on top of "e" is loaded onto the main stack.
                   # Then, this value is incremented by 1. This new value os finally pushed to the top of register "e".
                   # b = [0,1,0], e = [1, 2], Main = [100]

    ======================================================================================================================================================================================

                 1-d0!>c # Finally, decrement the value on top of the Main stack (the input) by 1, duplicate this, pop and compare this value with 0, and as long as the `input-1`>=0, keep on executing this macro.
                         # b = [0,1,0], e = [1, 2], Main = [100,99]

================================================================================================================================================================================================================================================

                                            lbp # Finally, once all the iterations of the macros have taken place, load the n'th value of the sequence off of the top of register "b", and then output it.
                                                # At the end, b = [0,1,0,1,2,0,1,2,3,0,1,2,3,4,...] and Main=[100,99,...,0,-1].             
\$\endgroup\$
0
\$\begingroup\$

PHP, 41 bytes

seems like there´s nothing shorter in PHP. Damn the dollars.

for($s=$argv[1];$s>0;$s-=++$i);echo$i+$s;

1-indexed. Run with -r or Try it Online.

\$\endgroup\$
  • \$\begingroup\$ Try It Online! In Bash, as it was more convenient and I could not figure out how to use flags on the actual PHP page, but at least it proves that the code works. :) \$\endgroup\$ – R. Kap Jan 23 '17 at 0:51
  • \$\begingroup\$ @R.Kap The actual PHP page needs no flags. -r tells PHP to run code from the command line instead of from a file. But thanks for the TiO. \$\endgroup\$ – Titus Jan 23 '17 at 9:03
0
\$\begingroup\$

Bash + BSD utilities (MacOS X, etc.), 28 bytes, 1-based indexing

jot -wjot\ %d $1|sh|sed $1!d

Bash + standard utilities (GNU or BSD), 29 bytes, 1-based indexing

seq $1|xargs -n1 seq|sed $1!d

Try the GNU version online!

BSD's jot is a little golfier than the GNU seq utility, since jot lets you use the %d printing code, whereas seq requires %.f (which is one byte longer) to get a similar effect.

\$\endgroup\$
0
\$\begingroup\$

QBasic, 43 bytes

INPUT a
i=1
WHILE a-i>0
a=a-i:i=i+1
WEND
?a

1-based. Try it online!

\$\endgroup\$
0
\$\begingroup\$

Pyt, 16 bytes

←Đř△⇹Đ↔Đ04Ș<*↑+-

Solution is 1-indexed

Explanation:

Code Explanation (with stack in parentheses) (sample input of 5)

←                              Get input (5)
 Đ                             Duplicate input (5,5)
  ř                            Push [1,2,...,top of stack] (5,[1,2,3,4,5])
   △                           Triangle numbers (5,[1,3,6,10,15])
    ⇹                          Swap top two elements ([1,3,6,10,15],5)
     Đ                         Duplicate top ([1,3,6,10,15],5,5)
      ↔                        Flip stack (5,5,[1,3,6,10,15])
       Đ                       Duplicate top (5,5,[1,3,6,10,15],[1,3,6,10,15])
        0                      Push 0 [this is to allow the next step] (5,5,[1,3,6,10,15],[1,3,6,10,15],0)
         4Ș                    Flip top four elements (5,0,[1,3,6,10,15],[1,3,6,10,15],5)
           <                   Less than (5,0,[1,3,6,10,15],[True,True,False,False,False])
            *                  Multiply (5,0,[1,3,0,0,0])
             ↑                 Get maximum (5,0,3)
              +                Add [this is to get rid of the 0 inserted earlier] (5,3)
               -               Subtract (2)
\$\endgroup\$
0
\$\begingroup\$

Husk, 4 bytes

!ΣḣN

This uses 1-indexing, try it online! (Or try this which uses 0-indexing)

Explanation

!ΣḣN  -- takes an integer N as argument, for example 5
   N  -- natural numbers: [1,2,3,4,…
  ḣ   -- rangify each: [[1],[1,2],[1,2,3],[1,2,3,4],…
 Σ    -- concatenate: [1,1,2,1,2,3,1,2,3,4,…
!     -- index into that list: 2
\$\endgroup\$
0
\$\begingroup\$

Python 2, 50 bytes

Try it online!

c=1
u=0
n=input()
while u<n:u+=c;c+=1
print(n-u+c)

I have a feeling this can be golfed a lot, but this is what I have so far.

\$\endgroup\$

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.