Count forth and back then double up

Question

Let's count...

Count up to 2 and back to 1
Count up to 4 and back to 1
Count up to 6 and back to 1
... ok you got it...

put all these together and you'll get the following sequence

 {1,2,1,2,3,4,3,2,1,2,3,4,5,6,5,4,3,2,1,2,3,4,5,6,7,8,7,6,5,4,3,2,1,2,3...}

Challenge
Given an integer n>0for 1-indexed (or n>=0 for 0-indexed), output the nth term of this sequence

Test cases

Input->Output  

1->1  
68->6  
668->20  
6667->63  
10000->84

Rules

your program must be able to compute solutions up to n=10000 in under a minute

This is code-golf, so the shortest code in bytes wins!

Answer 1

JavaScript (ES7),  59 ... 44  43 bytes

Saved 1 byte thanks to Titus

Expected input: 1-indexed.

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

Initially inspired by a formula for A004738, which is a similar sequence. But I ended up rewriting it entirely.

Test cases

let f=

n=>(n-=(r=(~-n/2)**.5|0)*r*2)<++r*2?n:r*4-n

console.log(f(1))     // -> 1
console.log(f(68))    // -> 6
console.log(f(668))   // -> 20
console.log(f(6667))  // -> 63
console.log(f(10000)) // -> 84

How?

The sequence can be arranged as a triangle, with the left part in ascending order and the right part in descending order.

Below are the first 4 rows, containing the first 32 terms:

            1 | 2
        1 2 3 | 4 3 2
    1 2 3 4 5 | 6 5 4 3 2
1 2 3 4 5 6 7 | 8 7 6 5 4 3 2

Now, let's introduce some variables:

 row  | range   | ascending part              | descending part
 r    | x to y  | 1, 2, ..., i                | 4(r+1)-(i+1), 4(r+1)-(i+2), ...
------+---------+-----------------------------+-----------------------------------------
  0   |  1 -  2 |                           1 | 4-2
  1   |  3 -  8 |                   1   2   3 | 8-4  8-5  8-6
  2   |  9 - 18 |           1   2   3   4   5 | 12-6 12-7 12-8  12-9  12-10
  3   | 19 - 32 |   1   2   3   4   5   6   7 | 16-8 16-9 16-10 16-11 16-12 16-13 16-14

We start with 2 elements at the top and add 4 elements on each new row. Therefore, the number of elements on the 0-indexed row r can be expressed as:

a(r) = 4r + 2

The 1-indexed starting position x of the row r is given by the sum of all preceding terms in this arithmetic series plus one, which leads to:

x(r) = r * (2 + a(r - 1)) / 2 + 1
     = r * (2 + 4(r - 1) + 2) / 2 + 1
     = 2r² + 1

Reciprocally, given a 1-indexed position n in the sequence, the corresponding row can be found with:

r(n) = floor(sqrt((n - 1) / 2))

or as JS code:

r = (~-n / 2) ** 0.5 | 0

Once we know r(n), we subtract the starting position x(r) minus one from n:

n -= r * r * 2

We compare n with a(r) / 2 + 1 = 2r + 2 to figure out whether we are in the ascending part or in the descending part:

n < ++r * 2 ?

If this expression is true, we return n. Otherwise, we return 4(r + 1) - n. But since r was already incremented in the last statement, this is simplified as:

n : r * 4 - n

Answer 2

Haskell, 37 bytes

(!!)$do k<-[1,3..];[1..k]++[k+1,k..2]

Try it online!

Zero-indexed. Generates the list and indexes into it. Thanks to Ørjan Johansen for saving 2 bytes!

---

Haskell, 38 bytes

(!!)[min(k-r)r|k<-[0,4..],r<-[1..k-2]]

Try it online!

Zero-indexed. Generates the list and indexes into it.

---

Haskell, 39 bytes

n%k|n<k=1+min(k-n)n|j<-k+4=(n-k)%j
(%2)

Try it online!

Zero-indexed. A recursive method.

Answer 3

Python, 46 bytes

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

Try it online!

Zero indexed.

Answer 4

Husk, 8 bytes

!…ṁoe1DN

1-indexed. Try it online!

Explanation

!…ṁoe1DN  Implicit input (an integer).
       N  Positive integers: [1,2,3,4,...
  ṁo      Map and concatenate
      D   double: [2,4,6,8,...
    e1    then pair with 1: [1,2,1,4,1,6,1,8,...
 …        Fill gaps with ranges: [1,2,1,2,3,4,3,2,1,2,3,4,5,6,...
!         Index with input.

Answer 5

Perl 6, 29 bytes

{({|(1...$+=2...2)}...*)[$_]}

Try it online

0-based

Expanded:

{  # bare block lambda with implicit parameter ｢$_｣

  (
    # generate an outer sequence

    {           # bare block lambda

      |(        # flatten into outer sequence

        # generate an inner sequence

        1       # start at 1

        ...     # go (upward) towards:

        $       # an anonymous state variable (new one for each outer sequence)
          += 2  # increment by 2

        ...     # go (downward) towards:

        2       # stop at 2 (1 will come from the next inner sequence)

      )
    }

    ...         # keep generating the outer sequence until:
    *           # never stop

  )[ $_ ]       # index into outer sequence
}

The inner sequence 1...$+=2...2 produces

(1, 2).Seq
(1, 2, 3, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 7, 6, 5, 4, 3, 2).Seq
(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2).Seq
...

To get it to be 1-based, add 0, before the second {, or add -1 after $_

Answer 6

R, 64 bytes

function(n)unlist(sapply(seq(2,n,2),function(x)c(2:x-1,x:2)))[n]

Function that takes an argument n. It creates a vector 2:n with increments of 2. For each of these, the vector 1:(x-1) and x:2 is created. This in total will be longer than n. We unlist it, to get a vector and take the n-th entry.

Answer 7

Jelly, 10, 9 bytes

ḤŒḄṖµ€Fị@

Try it online!

Also 1 indexed, and finishes pretty fast.

One byte saved thanks to @ErikTheOutgolfer!

Explanation:

Hypothetically, let's say the input (a) is 3.

    µ€      # (Implicit) On each number in range(a):
            #
Ḥ           # Double
            #   [2, 4, 6]
            #
 ŒḄ         # Convert to a range, and Bounce
            #   [[1, 2, 1], [1, 2, 3, 4, 3, 2, 1], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1]]
            #
   Ṗ        # Pop
            #   [[1, 2], [1, 2, 3, 4, 3, 2], [1, 2, 3, 4, 5, 6, 5, 4, 3, 2]]
            #
     F      # Flatten
            #   [1, 2, 1, 2, 3, 4, 3, 2, 1, 2, 3, 4, 5, 6, 5, 4, 3, 2]
            #
      ị@    # Grab the item[a]
            #   1
            #

Answer 8

Python 2, 56 bytes

def f(x):n=int((x/2)**.5);print 2*n-abs(2*n*n+2*n+1-x)+2

Try it online!

This is 0-indexed.

-1 byte thanks to @JustinMariner

How this Works

We note that the 1-indexed n-th group (1, 2, ... 2n ..., 2, 1) occurs from elements numbered 0-indexed 2(n-1)^2 to 2n^2.

To find the element at index x, we can find the group number n that x is in. From that, we calculate the distance from the center of the group that x is. (This distance is abs(2*n**2+2*n+2-x)).

However, since the elements decrease further away from the center of a group, we subtract the distance from the maximum value of the group.

Answer 9

05AB1E, 8 bytes

Code:

ÅÈ€1Ÿ¦¹è

Uses the 05AB1E encoding. Try it online!

Explanation:

ÅÈ           # Get all even numbers until input (0, 2, ..., input)
  €1         # Insert 1 after each element
    Ÿ        # Inclusive range (e.g. [1, 4, 1] -> [1, 2, 3, 4, 3, 2, 1])
     ¦       # Remove the first element
      ¹è     # Retrieve the element at the input index

Answer 10

JavaScript, 39 bytes

f=(n,t=2)=>n>t?f(n-t,t+4):n>t/2?t-n+2:n

Answer 11

MATL, 15 bytes

li:"@EZv4L)]vG)

1-based.

Try it online!

This times out for the largest test cases in TIO, but finishes in time on my desktop computer (compiler running on MATLAB R2017a). To display elapsed time, add Z` at the end of the code.

>> matl 'li:"@EZv4L)]vG)Z`'
> 10000
84
15.8235379852476

Explanation

The code generates many more terms than necessary. Specifically, it computes n "pieces" of the sequence, where each piece is a count up and back to 1.

l       % Push 1
i       % Push input, n
:       % Range [1 2 ...n]
"       % For each k in that range
  @E    %   Push 2*k
  Zv    %   Symmetric range: [1 2 ... 2*k-1 2*k 2*k-1 ... 2 1]
  4L)   %   Remove last entry: [1 2 ... 2*k-1 2*k 2*k-1 ... 2]
]       % End
v       % Concatenate all stack contents into a column vector
G)      % Get n-th entry. Implicitly display

Answer 12

Husk, 12 10 bytes

!ṁ§¤+hḣṫİ0

Try it online!

1-indexed, works quite fast

Explanation

!ṁ§¤+hḣṫİ0
 ṁ      İ0    Map the following function over the even numbers and concatenate the results together
  §   ḣṫ      Get the ranges 1-n and n-1, then... 
   ¤+h         remove the last element from both of them and concatenate them together
!             Return the element of the resulting list at the given index

Answer 13

Mathematica, 90 bytes

Flatten[{1}~Join~Table[Join[Rest[p=Range@i],Reverse@Most@p],{i,2,Round[2Sqrt@#],2}]][[#]]&

Try it online!

Answer 14

Ruby, 78 75 bytes

Saved 1 byte thanks to Step Hen

Saved 1 byte thanks to Mr. Xcoder

->n{a=0;b=2;c=1;n.times{if a==b then c=0;b+=2;end;c=1if a<2;a+=c<1?-1:1};a}

Try it online!

Hopefully I can get some tips for pulling the bytecount down more. I tried to take a simple approach.

Answer 15

Retina, 62 bytes

.+
$*
^((^.|\2..)*)\1.
6$*1$2$2;1
(?=.+;(.+))\1(.+).*;\2.*
$.2

Try it online! Link includes test cases. Input is 1-indexed. The first stage is just decimal to unary conversion. The second stage finds the highest square number s strictly less than half of n; $1 is s², while $2 is 2s-1. It calculates two values, first the number of numbers in the current up/down run, which is 4(s+1) = 4s+4 = 2$2+6, and secondly the position within that run, which is n-2s² = n-(2$1+1)+1 = n-$&+1, which just requires a 1 to make up for the 1 used to enforce the strict inequality. The final stage then counts from that position to both the start and end of the run and takes the lower result and converts it to decimal.

Answer 16

Mathematica, 67 bytes

(t=z=1;While[(x=3-4t+2t^2)<#,t++;z=x];If[#-z>2t-2,4t-5+z-#,#-z+1])&

Try it online!

Answer 17

Perl 5, 43 + 1 (-p) = 44 bytes

$_=($n=2*int sqrt$_/2)+2-abs$n/2*$n+$n+1-$_

Try it online!

I was working on a formula to calculate the n-th element directly. Then I saw that @fireflame241 had done that work, and I golfed it into Perl.

# Perl 5, 50 + 1 (-n) = 51 bytes

push@r,1..++$",reverse 2..++$"while@r<$_;say$r[$_]

Try it online!

Results are 0 indexed.

Answer 18

Haskell, 115 81 bytes

y%x=snd(span(<x)$scanl(+)y[y+1,y+3..])!!0
g 1=1
g x|1%x>2%x=1+g(x-1)|1>0=g(x-1)-1

Try it online!

There is some magic going on here. Could probably be shorter if I used a normal approach though.

Explanation

First we define %. % is a function that takes two variables x, and y. It constructs a list scanl(+)y[y+1,y+3..] and finds the first element of that list greater than x. scanl(+) just performs iterative sums, to get the triangular numbers we would do scanl(+)0[1..], to get the square numbers we would do scanl(+)0[1,3..]. The two lists in particular we will be constructing are scanl(+)2[3,5..] and scanl(+)1[2,4..] these are the inflection points of the pattern.

Now we define the main function g which takes an x. If x is one we return 1 because that's the first value. Otherwise we check the next two inflection points, if the down inflection is larger 1%x>2x we return the successor of g$x-1 otherwise we return the predecessor of g$x-1.

Ok but why does that work?

First of all "Whats with the way we find vertices?". Its important to note the distance between consecutive vertices of the same type. You will notice that the differences are growing by 2 each time. This makes sense because the triangles bases become wider by 2 each time. We can make a list constant difference using a list literal like so [2,4..] and we use scanl(+) to to turn these lists into our vertex lists, based on the location of the first vertex and the first difference.

So now that we have a way of finding upward and downward vertices we can use that information to get the values. We say that the first value is 1 otherwise we have to take either the successor or the predecessor. If the next vertex is a upward one we want to take the predecessor, otherwise we take the successor.

Haskell, 56 51 46 bytes

Here's my better solution with less math and fewer bytes.

d x|e<-[1..x-1]=e++map(x+1-)e
(([1..]>>=d)!!0)

Try it online!

Answer 19

Pyke, 14 bytes

SF}SDtO_+)sQt@

Try it here!

S              -    range(1, input)
 F}SDtO_+)     -   for i in ^:
  }            -      ^ * 2
   S           -     range(1, ^)
        +      -    ^ + v
     tO_       -     ^[1:-1:-1]
          s    -  sum(^)
           Qt@ - ^[input-1]

Answer 20

C# (.NET Core), 120 bytes

Explanation: pretty simple, the first nested loop climbs up to our max, the second climbs back down to 2. The repeat for each multiple of 2.

x=>{var a=0;for(int i=2,j=0;j<x;i+=2){for(var b=1;b<=i&j<x;b++,j++){a=b;}for(var c=i-1;c>1&j<x;c--,j++){a=c;}}return a;}

Try it online!

Answer 21

Java (OpenJDK 8), 53 bytes

n->{int i=2;for(;n>i;i+=4)n-=i;return n>i/2?i-n+2:n;}

Try it online!

-2 bytes thanks to Nevay.

1-indexed.

TL;DR We split the sequence into convenient chunks, find the chunk n is in, then find the nth position in the chunk.

Here, we can split the sequence like [[1,2],[1,2,3,4,3,2],[1,2,3,4,5,6,5,4,3,2],...], which gives us chunk sizes of 4i-2. Starting with i=2, we subtract i from n, essentially moving upwards a chunk at a time. Once we satisfy n<=i, we know n is now the position of the correct value in the current chunk.

We then get the value by comparing n to i, the size of the chunk. The midpoint of each chunk is equal to i/2+1; if n is less than this, we simply return n. If n is greater, we return i-n+2.

Example

n = 16, i = 2

Is n > i? Yes, n = n - 2 = 14, i = i + 4 = 6
Is n > i? Yes, n = n - 6 = 8, i = i + 4 = 10
Is n > i? No, stop looping.
10 / 2 + 1 = 6
Is n > 6? Yes, return i - n + 2 = 8 - 6 + 2 = 4

Answer 22

Python 2, 5! bytes (120 bytes :P)

r=range
a=[]
for i in r(2,998,2): 
	for j in r(1,i+1): a.append(j)
	for j in r(i-1,1,-1): a.append(j)
print a[input()-1]

Try it online!

Straightforward, makes the list and then takes input'th element

Answer 23

Python 3, 184 156 bytes

l,n,r=list,next,range
h=lambda x:l(r(1,x))+l(r(x-2,1,-1))
def g():
	x=3
	while True:yield from h(x);x+=2
def f(i):
	x=g()
	for _ in r(i-1):n(x)
	return n(x)

Try it online!

golfed with Python generator for "lazy" evaluation

Answer 24

QBIC, 47 bytes

g=q{p=p+1~p=:|_Xg\g=g+q~g=1or g>=r|r=r+1┘q=q*-1

Explanation

g=q         var g is the current value of the sequence; set to 1 at the start
{           DO infinitely
p=p+1       raise the step counter (var p)
~p=:|_Xg    IF p equals the input term a (read from cmd line) THEN QUIT, printing g
\           ELSE
g=g+q       raise (or decrement) g by q (q is 1 at the start of QBIC)
~g=1        IF g is at the lower bound of a subsequence
    or g>=r OR g is at the upper bound (r start as 2 in QBIC)
|r=r+1      THEN increment r (this happens once on lower bound, and once on upper, 
            total of 2 raise per subsequence)
┘q=q*-1     and switch q from 1 to -1

Answer 25

Pyth,  19  18 bytes

-yhKs@/Q2 2a*yKhKt

Try it here!

Answer 26

Röda, 54 bytes

f n{seq 1,n|{|i|seq 1,2*i;seq 2*i-1,2}_|head n+2|tail}

Try it online!

Call with: try f(n)

This function returns quickly the answer, but after that does some unnecessary calculations and eventually runs out of memory.

As the function does return the actual answer shortly after it is called (clearly under a minute), I think this answer is valid.

(In Röda functions can return values before they exit due to parallelism.)

Answer 27

C# (.NET Core),99 95 86 bytes

n=>{int i=1,t=2,d=0;for(;n>1;){i+=1-2*d;if(i==t){d++;t+=2;}if(i==1)d--;n--;}return i;}

Try it online!

Lambda function that takes and returns an integer. Single loop that handles counting up and down.

Answer 28

PHP, 65+1 bytes

for($x=$d=$z=1;--$argn;)$d=($x+=$d)>1?$x>$z?-1:$d:!!$z+=2;echo$x;

Run as pipe with -R or try it online (or uncomment one of the other versions).

A port of tsh´s recursive JavaScript takes 66 bytes:

function f($n,$t=2){return$t<2*$n?$t<$n?f($n-$t,$t+4):$t-$n+2:$n;}

A port of Arnauld´s solution takes 62+1:

$n=$argn;echo($n-=($r=(~-$n/2)**.5|0)*$r*2)<++$r*2?$n:$r*4-$n;

A golfed port of Xanderhall´s Java has the shortest code so far (55+1 bytes):

for($n=$argn;$n+2>$i+=4;)$n-=$i-2;echo$n*2>$i?$i-$n:$n;