Keep/Drop/Increase Sequence

Question

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!

\$\begingroup\$ related \$\endgroup\$
– Rod
Aug 21, 2017 at 15:01 — Rod, Aug 21, 2017 at 15:01
\$\begingroup\$ May we choose between 0 and 1 indexing? \$\endgroup\$
– Mr. Xcoder
Aug 21, 2017 at 15:01 — Mr. Xcoder, Aug 21, 2017 at 15:01
\$\begingroup\$ @Mr.Xcoder I'm afraid not. This is only 1-indexed \$\endgroup\$
– user73398
Aug 21, 2017 at 15:04 — user73398, Aug 21, 2017 at 15:04
\$\begingroup\$ May we return a list containing all the elements in order? \$\endgroup\$
– Wheat Wizard ♦
Aug 21, 2017 at 15:51 — Wheat Wizard, Aug 21, 2017 at 15:51
\$\begingroup\$ @WheatWizard this is totally unacceptable. sorry \$\endgroup\$
– user73398
Aug 21, 2017 at 16:06 — user73398, Aug 21, 2017 at 16:06

Xanderhall · Accepted Answer · 2017-08-22 12:28:45Z

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

\$\begingroup\$ You can use return~-n+i*i; to save 1 byte. \$\endgroup\$
– Nevay
Aug 22, 2017 at 11:43 — Nevay, Aug 22, 2017 at 11:43

Leaky Nun · Accepted Answer · 2017-08-21 15:16:59Z

8

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

edited Aug 21, 2017 at 15:16

answered Aug 21, 2017 at 15:14

Leaky Nun

49.6k6 gold badges107 silver badges281 bronze badges

\$\begingroup\$ 46 bytes: def f(n):a=round((2*n)**.5);return~-n+a*-~a//2. Not sure though... Clever approach! \$\endgroup\$
– Mr. Xcoder
Aug 21, 2017 at 15:15
\$\begingroup\$ Aw, double lambdas is one extra byte, I was hoping that would save a byte... \$\endgroup\$
– Stephen
Aug 21, 2017 at 15:21
\$\begingroup\$ Why did one downvote this? Is there any problem with the approach that we didn't notice? \$\endgroup\$
– Mr. Xcoder
Aug 21, 2017 at 15:24
\$\begingroup\$ @Mr.Xcoder maybe because of the corky remark. \$\endgroup\$
– Leaky Nun
Aug 21, 2017 at 15:28
\$\begingroup\$ 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. \$\endgroup\$
– Titus
Aug 22, 2017 at 13:42

| Show 1 more comment

nimi · Accepted Answer · 2017-08-21 16:14:47Z

Haskell, 48 43 41 bytes

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#1             -- start with n=1 and l=0 and
 0:             -- prepend a dummy value to shift from 0 to 1-based index
    !!          -- pick the i-th element from the list

Ørjan Johansen · Accepted Answer · 2017-08-22 05:46:36Z

Haskell, 33 bytes

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.

Erik the Outgolfer · Accepted Answer · 2017-08-21 15:16:32Z

3

Jelly, 8 bytes

Ḷ+²µ€Ẏ⁸ị

Try it online!

answered Aug 21, 2017 at 15:16

Erik the Outgolfer

40.5k5 gold badges41 silver badges121 bronze badges

Add a comment |

Mr. Xcoder · Accepted Answer · 2017-08-21 15:32:24Z

3

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!

answered Aug 21, 2017 at 15:32

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

\$\begingroup\$ Same algorithm... \$\endgroup\$
– Leaky Nun
Aug 21, 2017 at 15:45

Add a comment |

Leaky Nun · Accepted Answer · 2017-08-21 20:55:24Z

TeX, 166 bytes

\newcommand{\f}[1]{\count0=0\count1=0\loop\advance\count0 by\the\count1\advance\count1 by1\ifnum\count0<#1\repeat\advance\count0 by#1\advance\count0 by-1
\the\count0}

Usage

\documentclass[12pt,a4paper]{article}
\begin{document}
\newcommand{\f}[1]{\count0=0\count1=0\loop\advance\count0 by\the\count1\advance\count1 by1\ifnum\count0<#1\repeat\advance\count0 by#1\advance\count0 by-1
\the\count0}

\f{1}

\f{22}

\f{333}

\f{4444}

\f{12345}
\end{document}

Erik the Outgolfer · Accepted Answer · 2017-08-21 15:27:39Z

2

05AB1E, 12 bytes

LεÝÁćn+}˜¹<è

Try it online!

answered Aug 21, 2017 at 15:27

Erik the Outgolfer

40.5k5 gold badges41 silver badges121 bronze badges

\$\begingroup\$ Very cool approach! \$\endgroup\$
– Emigna
Aug 21, 2017 at 20:55
\$\begingroup\$ @Emigna Well, I'm just doing [0..a-1] + a**2, the cool thing here imo is just the ÝÁćn+ instead of D<Ýsn+. \$\endgroup\$
– Erik the Outgolfer
Aug 22, 2017 at 7:47
\$\begingroup\$ εÝÁćn+} can be DL<sn+ for -1 \$\endgroup\$
– Kevin Cruijssen
Nov 23, 2022 at 8:51

Add a comment |

Brad Gilbert b2gills · Accepted Answer · 2017-08-21 16:36:56Z

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
  [ $_ - 1 ]                  # index into the sequence
                              # (adjusting to 0-based index)
}

(1..*).rotor({++$=>++$+1}...*) produces:

(
 (1,),
 (4, 5),
 (9, 10, 11),
 (16, 17, 18, 19),
 (25, 26, 27, 28, 29),
 ...
).Seq

user61980user61980 · Accepted Answer · 2017-08-21 21:17:17Z

2

Mathematica, 37 bytes

Flatten[Range@#+#^2-1&~Array~#][[#]]&

Explanation

Range@#+#^2-1&

Function which takes a positive integer # and returns the run of # consecutive numbers in the sequence.

...~Array~#

Produces the list of all such runs up to the input #

Flatten[...][[#]]

Flattens the resulting list and returns the #th element.

answered Aug 21, 2017 at 21:17

user61980

Add a comment |

mackoo13 · Accepted Answer · 2017-08-22 15:08:06Z

Javascript, 43 38 bytes

n=>eval("for(r=1;n>r;)n-=r++;r*r+n-1")

Try it online!

I use the fact, that for each triangular number plus one, the result is a square number.

As an example: triangular numbers are 0, 1, 3, 6, 10... so for 1, 2, 4, 7, 11... we observe 1, 4, 9, 16, 25... in our sequence.

If the index is somewhere between these known numbers, the elements of our sequence only advance by one. For instance, to calculate the result for 10, we take 7 (as a triangular number plus one), take the result (16) and add 10-7=3. Thus, 16+3=19.

naffetS · Accepted Answer · 2022-11-17 19:07:39Z

Vyxal, 8 bytes

v₍ʁ²ṠfJi

Try it Online!

Would beat Jelly if zero-indexing were allowed (remove J).

v₍ʁ²ṠfJi
v        # For each in a range [1, n]:
 ₍       #  Apply both of the next two elements and wrap in a list:
  ʁ      #   Range [0, n), and:
   ²     #   Square n
    Ṡ    # Sum each (vectorizing)
         # For an input of 4, this will give [[1], [4, 5], [9, 10, 11], [16, 17, 18, 19]]
         # Basically, for each x in [1, n], add x^2 to each in [0, x)
     f   # Flatten
      J  # Prepend the input to the beginning (doesn't matter what we prepend)
       i # Index the input into this

Stephen · Accepted Answer · 2017-08-21 15:30:32Z

1

cQuents, 27 bytes

#R(2B)^.5)|1:b~-B+A*-b~A//2

Try it online!

Currently a port of Leaky's Python answer, I think there's a better way though.

answered Aug 21, 2017 at 15:30

Stephen

13.8k3 gold badges50 silver badges116 bronze badges

\$\begingroup\$ Try my alternative algorithm \$\endgroup\$
– Leaky Nun
Aug 21, 2017 at 15:31

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

Swift 3, 72 bytes

Port of my Python solution.

func f(_ x:Int,_ y:Int=0,_ z:Int=0)->Int{return y<x ?f(x,y+z,z+1):y+x-1}

Test Suite.

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 21, 2017 at 16:00

Mr. Xcoder

42.3k9 gold badges79 silver badges214 bronze badges

Add a comment |

TheLethalCoder · Accepted Answer · 2017-08-21 16:27:21Z

1

C# (Mono), 164 bytes

using System.Linq;n=>{var a=new int[1]{1}.ToList();for(int i=1,m;a.Count<n;a.AddRange(new int[++i*2].Select((_,d)=>m+d+1).Skip(i).Take(i)))m=a.Max();return a[n-1];}

Try it online!

answered Aug 21, 2017 at 16:27

TheLethalCoder

7,14926 silver badges43 bronze badges

Add a comment |

Xcali · Accepted Answer · 2017-08-22 05:04:14Z

1

Perl 5, 33 + 1 (-p) = 34 bytes

$\+=$.--?1:2+($.=++$s)while$_--}{

Try it online!

edited Aug 22, 2017 at 5:04

answered Aug 22, 2017 at 4:35

Xcali

13.4k2 gold badges14 silver badges37 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 22, 2017 at 11:52

Luis Mendo

104k9 gold badges132 silver badges365 bronze badges

Add a comment |

fergusq · Accepted Answer · 2017-08-22 18:48:07Z

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
(yhteenlasku            (k   *          2     )

 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

Community · Accepted Answer · 2020-06-17 09:04:33Z

1

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>

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 22, 2017 at 17:32

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Leaky Nun · Accepted Answer · 2017-08-21 15:30:34Z

0

Python 3, 50 bytes

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

Try it online!

answered Aug 21, 2017 at 15:30

Leaky Nun

49.6k6 gold badges107 silver badges281 bronze badges

\$\begingroup\$ This would really benefit from a full-program port to Python 2 (46 bytes - would tie the recursive approach) \$\endgroup\$
– Mr. Xcoder
Aug 21, 2017 at 15:37

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

Mathematica, 82 bytes

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

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 21, 2017 at 16:24

ZaMoC

24.4k2 gold badges29 silver badges79 bronze badges

Add a comment |

xnor · Accepted Answer · 2017-08-21 20:44:24Z

0

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.

edited Aug 21, 2017 at 20:44

answered Aug 21, 2017 at 20:25

xnor

144k26 gold badges273 silver badges638 bronze badges

Add a comment |

Asleepace · Accepted Answer · 2017-08-22 00:39:24Z

0

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.

edited Aug 22, 2017 at 0:39

answered Aug 22, 2017 at 0:05

Asleepace

6053 silver badges7 bronze badges

Add a comment |

Neil · Accepted Answer · 2017-08-22 09:37:55Z

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.

cleblanc · Accepted Answer · 2017-08-22 13:27:55Z

0

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!

answered Aug 22, 2017 at 13:27

cleblanc

3,4608 silver badges16 bronze badges

Add a comment |

Community · Accepted Answer · 2020-06-17 09:04:33Z

0

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;

edited Jun 17, 2020 at 9:04

CommunityBot

1

answered Aug 22, 2017 at 13:42

Titus

14.6k1 gold badge23 silver badges41 bronze badges

Add a comment |

MarcMush · Accepted Answer · 2022-11-17 19:05:04Z

0

TI-Basic, ⁴¹ 22 bytes

Input N
int(.5+√(2N
N-1+.5Ans(Ans+1

Port of Leaky Nun's Python 3 answer.

I was quite happy with my previous 41-byte solution so here it is:

Input N
For I,1,N
For J,1,I(N>0
DS<(N,0
Ans+1
Ans+1
End
End
Ans-1

Needs a fresh calculator, or at least Ans initialized to 0

edited Nov 17, 2022 at 19:05

answered Nov 17, 2022 at 18:45

MarcMush

6,26511 silver badges16 bronze badges

Add a comment |

Jordan · Accepted Answer · 2022-11-17 19:50:49Z

0

Ruby, 37 36 bytes

-1 byte thanks to Steffan

Port of Leaky Nun's Python 3 answer.

->n{~-n-(a=((2*n)**0.5).round)*~a/2}

Attempt This Online!

edited Nov 17, 2022 at 19:50

answered Nov 17, 2022 at 16:48

Jordan

9,7261 gold badge30 silver badges47 bronze badges

\$\begingroup\$ you can save a byte replacing +-~a/2 with -~a/2: ->n{~-n-(a=((2*n)**0.5).round)*~a/2} \$\endgroup\$
– naffetS
Nov 17, 2022 at 18:54
\$\begingroup\$ @Steffan Nice, thanks. \$\endgroup\$
– Jordan
Nov 17, 2022 at 19:50

Add a comment |

Shaggy · Accepted Answer · 2022-11-21 10:44:17Z

0

Japt, 9 bytes

0-indexed

g°Uô²cÈóY

Try it

g°Uô²cÈóY     :Implicit input of integer U
g             :Index into
 °U           :  Prefix increment U
   ô          :  Range [0,U]
    ²         :  Square each
     cÈ       :  Flat map each X at 0-based index Y
       óY     :    Range [X,X+Y)

edited Nov 21, 2022 at 10:44

answered Nov 17, 2022 at 20:06

Shaggy

41.6k4 gold badges34 silver badges92 bronze badges

Add a comment |

Keep/Drop/Increase Sequence

29 Answers 29

Java (OpenJDK 8), 45 44 bytes

Python 3, 47 46 bytes

Haskell, 48 43 41 bytes

Haskell, 33 bytes

Jelly, 8 bytes

Python 3, 46 bytes

TeX, 166 bytes

Usage

05AB1E, 12 bytes

Perl 6, 43 bytes

Expanded:

Mathematica, 37 bytes

Explanation

Javascript, 43 38 bytes

Vyxal, 8 bytes

cQuents, 27 bytes

Swift 3, 72 bytes

C# (Mono), 164 bytes

Perl 5, 33 + 1 (-p) = 34 bytes

MATL, 12 bytes

Explanation

Tampio, 310 308 bytes

JavaScript (ES6), 33 bytes

Try it

Python 3, 50 bytes

Mathematica, 82 bytes

Python, 40 bytes

Python, 41 bytes

Javascript (ES6) 100 98 Bytes

Retina, 27 bytes

C (gcc), 38 bytes

PHP, 48 42 37+1 bytes

TI-Basic, 41 22 bytes

Ruby, 37 36 bytes

Japt, 9 bytes

Your Answer

Sign up or log in

Post as a guest

Linked

Related

Hot Network Questions

TI-Basic, ⁴¹ 22 bytes