Count forth and back then double up

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 , so the shortest code in bytes wins!

• Who decides what takes a minute? A time-optimal Turing machine built from lego would take a really long time, while the same Turing machine simulated in, say, C, would presumably take seconds, or minutes, depending on what processor it runs on. Thus, if I submit said Turing machine description, is it valid? Aug 23 '17 at 10:14
• @Arthur I think that you can understand why I made this restriction...I didn't want an algorithm to take "forever" to find n=10000 by producing a huge list.Most of the people here gave brilliant answers that find millions in seconds.
– user73398
Aug 23 '17 at 10:32
• @BillSteihn I think the restriction is unnecessary. Aug 23 '17 at 10:38
• @EriktheOutgolfer gode golf answers can be tricky...without the restriction an answer that produces 10.000 tuples [1,2...2n..2,1] would be valid.The restriction is only for answers like this.I don't see where the problem is.I just want your answer to find all test cases in a reasonable amount of time.
– user73398
Aug 23 '17 at 11:01
• @StraklSeth General consensus here is that it should work in theory, not necessarily in practice. Aug 23 '17 at 11:24

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
• Ok, I think I understood. The length of each up-down part is 2,6,10,14... so the sum grows with the square of the rowcount, hence the sqrt. Very nice! Aug 23 '17 at 8:10

(!!)$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. 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. 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. 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$_

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.

• Could you do 1:n*2 instead of seq(2,n,2)? It'll be bigger than you need but that should be fine! Also I don't think this worked with seq(2,n,2) for n=1 anyway! Sep 26 '17 at 13:24

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.

• I have golfed this part: print 2*n-abs(2*n*n+2*n+1-x)+2 - 2*n*n+2*n can be 2*n*-~n and +2+2*n can be turned into -~n*2, which allows us to move it to the beginning which saves bytes (53 bytes) Aug 23 '17 at 7:11

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
• Doesn't work correctly unless you remove ¦, which also saves a byte ofc :) Aug 23 '17 at 9:34
• €1 is weird... Sep 3 '17 at 21:30

JavaScript, 39 bytes

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

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
#
• Your code is equivalent to Ḥ€ŒḄ€Ṗ€Fị@, so you can use µ€ for -1 (three or more monads with at the start): ḤŒḄṖµ€Fị@ Aug 23 '17 at 10:13
• This should really be ḤŒḄṖ <newline> ½ĊÇ€Fị@ for 12 to comply with the 10,000 requirement (running the 9 byte code locally takes about 2:20 on my i7 and uses 7GB) Aug 24 '17 at 13:15

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
• nice! TIO is slow sometimes...
– user73398
Aug 22 '17 at 23:10
• Well, the main cause of slowness here is the algorithm (which generates much more terms than necessary). Also, the MATL compiler is not particularly fast Aug 22 '17 at 23:35

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
• 8 bytes using Aug 23 '17 at 7:30
• @Zgarb that's a great idea and you should probably post it as your answer :)
– Leo
Aug 23 '17 at 10:43
• Done. Aug 23 '17 at 16:00

Mathematica, 90 bytes

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

Try it online!

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

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!

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.