# Keep/Drop/Increase Sequence

Here is the sequence I'm talking about:

{1, 4, 5, 9, 10, 11, 16, 17, 18, 19, 25, 26, 27...}


Starting from 1, keep 1, drop the next 2, keep the next 2, drop 3, keep 3 and so on. Yes, it's on OEIS (A064801), too!

The Challenge

Given an integer n>0, find the nth term of the above sequence

Test Cases

Input -> Output
1->1
22->49
333->683
4444->8908
12345->24747


This is code golf so the shortest answer in bytes wins! Good luck!

• related – Rod Aug 21 '17 at 15:01
• May we choose between 0 and 1 indexing? – Mr. Xcoder Aug 21 '17 at 15:01
• @Mr.Xcoder I'm afraid not. This is only 1-indexed – user73398 Aug 21 '17 at 15:04
• May we return a list containing all the elements in order? – Sriotchilism O'Zaic Aug 21 '17 at 15:51
• @WheatWizard this is totally unacceptable. sorry – user73398 Aug 21 '17 at 16:06

# Java (OpenJDK 8), 45 44 bytes

n->{int i=0;for(;++i<n;n-=i);return~-n+i*i;}


Try it online!

-1 byte thanks to @Nevay

After staring at this for a while, I noticed a pattern. Every time we drop n numbers, the next number in the sequence is a perfect square. Seeing this, I mentally broke the sequence into convenient chunks: [[1],[4,5],[9,10,11],...] Basically, the ith chunk starts with i*i, and iterates upwards for i elements.

To find the nth number in this sequence, we want to find first which chunk the number is in, and then which position in the chunk it occupies. We subtract our increment number i from n until n is less than i (which gives us our chunk), and then simply add n-1 to i*i to get the correct position in the chunk.

Example:

n = 8
n > 1? Yes, n = n - 1 = 7
n > 2? Yes, n = n - 2 = 5
n > 3? Yes, n = n - 3 = 2
n > 4? No, result is 4 * 4 + 2 - 1 = 17

• You can use return~-n+i*i; to save 1 byte. – Nevay Aug 22 '17 at 11:43

n#l=[l..l+n]++(n+1)#(l+2*n+3)
((0:0#1)!!)


4 extra bytes for 1-based indexing instead of 0-based. An unnecessary restriction, IMHO.

Try it online!

n#l             -- n is one less than the number of element to keep/drop and
-- l the next number where the keep starts
[l..l+n]     -- keep (n+1) numbers starting at l
++           -- and append a recursive call
(n+1)#       -- where n is incremented by 1 and
(l+2*n+3) -- l skips the elements to keep & drop

0:             -- prepend a dummy value to shift from 0 to 1-based index
!!          -- pick the i-th element from the list


# Python 3, 47 46 bytes

1 byte thanks to Mr. Xcoder.

def f(n):a=round((2*n)**.5);return~-n+a*-~a//2


Try it online!

VERY fast for higher numbers

• 46 bytes: def f(n):a=round((2*n)**.5);return~-n+a*-~a//2. Not sure though... Clever approach! – Mr. Xcoder Aug 21 '17 at 15:15
• Aw, double lambdas is one extra byte, I was hoping that would save a byte... – Stephen Aug 21 '17 at 15:21
• Why did one downvote this? Is there any problem with the approach that we didn't notice? – Mr. Xcoder Aug 21 '17 at 15:24
• @Mr.Xcoder maybe because of the corky remark. – Leaky Nun Aug 21 '17 at 15:28
• a*(a+1) is even for every integer. Does Python complain about float division on integers? Does it complain about bitwise operations on floats? If not: (2*n)**.5+.5|0. – Titus Aug 22 '17 at 13:42

# Jelly, 8 bytes

Ḷ+²µ€Ẏ⁸ị


Try it online!

An anonymous function. Use as ((!!)$0:do n<-[1..];[n^2..n^2+n-1]) 1 (!!)$0:do n<-[1..];[n^2..n^2+n-1]


Try it online!

• Constructs the sequence as an infinite list, then indexes into it with !!. The 0: is a dummy element to adjust from 0- to 1-based indexing.
• The range [n^2..n^2+n-1] constructs a subsequence without gaps, starting with the square of n and containing n numbers.
• The do notation concatenates the constructed ranges for all n>=1.

# Python 3, 46 bytes

f=lambda x,y=0,z=0:y<x and f(x,y+z,z+1)or~-y+x


Try it online!

• Same algorithm... – Leaky Nun Aug 21 '17 at 15:45

# Perl 6, 43 bytes

{(1..*).rotor({++$=>++$+1}...*).flat[$_-1]}  Test it ## Expanded: { # bare block lambda with implicit parameter ｢$_｣

( 1 .. * )                  # range starting from 1

.rotor(                     # break it into chunks

{ ++$=> ++$ + 1} ... * # infinite Seq of increasing pairs
#   1  =>    1 + 1    ==>   1 => 2 ( grab 1 skip 2 )
#   2  =>    2 + 1    ==>   2 => 3
#   3  =>    3 + 1    ==>   3 => 4
# ...  =>  ... + 1

).flat\                     # reduce the sequence of lists to a flat sequence


Try it online!

# Tampio, 310 308 bytes

n:n uni on n unena 1:lle
a unena k:lle on a vuona k:lla vähennettynä a:sta ja k
a vuona nollalla ja k on a
a vuona k:lla vähennettynä nollasta ja k on a
a vuona b:n seuraajalla ja k on yhteenlaskun kutsuttuna k:n kerrottuna 2:lla arvolla ja k:n vähennettynä a:sta arvolla unena k:n seuraajalle seuraaja


Usage: 4:n uni evaluates to 9.

Explanation:

n:n uni on n unena 1:lle
uni(n)  =  n uni 1

a unena k:lle on  a vuona  k:lla vähennettynä a:sta ja k
a uni k     =  (a vuo (k     vähennetty a)    )  k

a vuona nollalla ja k on a
(a vuo 0        )  k =  a

a vuona  k:lla vähennettynä nollasta ja k on a
(a vuo (k     vähennetty 0)       )  k =  a

a vuona  b:n seuraajalla ja k on
(a vuo (b   + 1)        )  k =

yhteenlaskun kutsuttuna k:n kerrottuna 2:lla arvolla

ja k:n vähennettynä a:sta arvolla unena  k:n seuraajalle seuraaja
((  k   vähennetty a     )       uni (k   + 1)   )  ) + 1


From standard library:

a vähennetty b = b - a
yhteenlasku a b  = a + b


# JavaScript (ES6), 33 bytes

Recursive solution inspired by Xanderhall's observations.

f=(n,x=1)=>n<x?n+x*x-1:f(n-x,++x)


## Try it

o.innerText=(
f=(n,x=1)=>n<x?n+x*x-1:f(n-x,++x)
)(i.value=12345);oninput=_=>o.innerText=f(+i.value)
<input id=i type=number><pre id=o>

# Python 3, 50 bytes

def f(n):
a=i=0
while a<n:a+=i;i+=1
return~-a+n


Try it online!

• This would really benefit from a full-program port to Python 2 (46 bytes - would tie the recursive approach) – Mr. Xcoder Aug 21 '17 at 15:37

# Mathematica, 82 bytes

Complement[Range[3#],Array[#+⌊((r=Sqrt[1+8#])-1)/2⌋⌊(r+1)/2⌋/2&,3#]][[#]]&


# Python, 40 bytes

lambda n:(round((2*n)**.5)+.5)**2//2+n-1


Try it online!

Optimizing Leaky Nun's expression.

# Python, 41 bytes

f=lambda n,k=1:n*(n<=k)or-~f(n-k,k+1)+2*k


Try it online!

Recursive expression.

# Javascript (ES6) 100 98 Bytes

var k=n=>{var s=[],i=1,c=1,j;while(s.length<n){for(j=i;j<i+c;j++){s.push(j)}i+=c*2+1;c++}return s}


Kind of did this one fast, so I bet there is a lot of room for improvement, just basic loops and counters.

# Retina, 27 bytes

.+
$* ((^1|1\2)+)1$1$2$&
1


Try it online! Port of @LeakyNun's Python answer. The first and last stages are just boring decimal ⇔ unary conversion. The second stage works like this: ((^1|1\2)+) is a triangular number matcher; $1 is the matched triangular number while $2 is its index. The trailing 1 means it matches the largest triangular number strictly less than the input, thus resulting in exactly one fewer iteration than the Python loop, meaning that $1 is equivalent to a-i and $2 to i-1 and their sum is a-1 or ~-a as required. ($& just prevents the match from being deleted from the result.) Note that for an input of 1 no matching happens and the output is simply the same as the input. If you were perverse you could use ^((^1|1\2)*)1 to match in that case too. # MATL, 12 bytes :"@U@:q+]vG)  Try it online! ### Explanation : % Push range [1 2 ... n], where n is implicit input " % For each k in that range @U % Push k^2 @: % Push range [1 2 ... k] q % Subtract 1: gives [0 1 ... k-1] + % Add: gives [k^2 k^2+1 ... k^2+k-1] ] % End v % Concatenate all numbers into a column vector G) % Get n-th entry. Implicitly display  # C (gcc), 38 bytes Using @Xanderhall's algorithm here i;f(n){for(i=0;++i<n;n-=i);n=n-1+i*i;}  Try it online! # PHP, 48 42 37+1 bytes ported from Leaky Nun´s answer while($argn>$a+=$i++);echo$a+~-$argn;


Run as pipe with -F or try it online.

direct approach, 42+1 bytes (ported from Leaky Nun´s other answer)

<?=($a=(2*$argn)**.5+.5|0)*-~$a/2+~-$argn;


Run as pipe with -nR or uncomment in above TiO.

older iterative solution, 48+1 bytes

for(;$argn--;$n++)$c++>$z&&$n+=++$z+$c=1;echo$n;