23
\$\begingroup\$

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!

\$\endgroup\$
12
  • 2
    \$\begingroup\$ 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? \$\endgroup\$
    – Arthur
    Aug 23 '17 at 10:14
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – user73398
    Aug 23 '17 at 10:32
  • 4
    \$\begingroup\$ @BillSteihn I think the restriction is unnecessary. \$\endgroup\$ Aug 23 '17 at 10:38
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – user73398
    Aug 23 '17 at 11:01
  • 3
    \$\begingroup\$ @StraklSeth General consensus here is that it should work in theory, not necessarily in practice. \$\endgroup\$ Aug 23 '17 at 11:24

28 Answers 28

16
\$\begingroup\$

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
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – JollyJoker
    Aug 23 '17 at 8:10
7
\$\begingroup\$

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.

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

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.

\$\endgroup\$
5
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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 $_

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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! \$\endgroup\$
    – Giuseppe
    Sep 26 '17 at 13:24
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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) \$\endgroup\$
    – Mr. Xcoder
    Aug 23 '17 at 7:11
2
\$\begingroup\$

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
\$\endgroup\$
2
2
\$\begingroup\$

JavaScript, 39 bytes

f=(n,t=2)=>n>t?f(n-t,t+4):n>t/2?t-n+2:n
\$\endgroup\$
2
\$\begingroup\$

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
            #
\$\endgroup\$
2
  • \$\begingroup\$ Your code is equivalent to Ḥ€ŒḄ€Ṗ€Fị@, so you can use µ€ for -1 (three or more monads with at the start): ḤŒḄṖµ€Fị@ \$\endgroup\$ Aug 23 '17 at 10:13
  • \$\begingroup\$ 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) \$\endgroup\$ Aug 24 '17 at 13:15
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ nice! TIO is slow sometimes... \$\endgroup\$
    – user73398
    Aug 22 '17 at 23:10
  • 1
    \$\begingroup\$ 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 \$\endgroup\$
    – Luis Mendo
    Aug 22 '17 at 23:35
1
\$\begingroup\$

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

Mathematica, 90 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Welcome to PPCG! c=1 if can be golfed to c=1if \$\endgroup\$
    – Stephen
    Aug 23 '17 at 0:13
  • \$\begingroup\$ 76 bytes: ->n{a=0;b=2;c=1;n.times{if a==b then c=0;b+=2;end;c=1if a==1;a+=c<1?-1:1};a} \$\endgroup\$
    – Mr. Xcoder
    Aug 23 '17 at 8:39
1
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ You don't need the +1, return n>i/2?i-n+2:n is sufficient. \$\endgroup\$
    – Nevay
    Aug 24 '17 at 12:54
  • \$\begingroup\$ Huh. Thanks, integer division. \$\endgroup\$
    – Xanderhall
    Aug 24 '17 at 13:27
1
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ Thank you whoever up voted! Now I have 50 rep so I can comment! dabs intensely \$\endgroup\$ Aug 26 '17 at 19:38
0
\$\begingroup\$

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

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

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
\$\endgroup\$
0
\$\begingroup\$

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

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

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.

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

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;
\$\endgroup\$
0
\$\begingroup\$

Pyth,  19  18 bytes

-yhKs@/Q2 2a*yKhKt

Try it here!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy