# X Steps Forward, 1 Step Back

Here the first 100 numbers of an easy sequence:

0,1,0,2,1,4,3,7,6,11,10,16,15,22,21,29,28,37,36,46,45,56,55,67,66,79,78,92,91,106,105,121,120,137,136,154,153,172,171,191,190,211,210,232,231,254,253,277,276,301,300,326,325,352,351,379,378,407,406,436,435,466,465,497,496,529,528,562,561,596,595,631,630,667,666,704,703,742,741,781,780,821,820,862,861,904,903,947,946,991,990,1036,1035,1082,1081,1129,1128,1177,1176,1226


How does this sequence work?

n: 0 1     2           3     4     5     6     7     8      9       10      11      12

0,      1-1=0,      2-1=1,      4-1=3,      7-1=6,       11-1=10,        16-1=15,
0+1=1,      0+2=2,      1+3=4,      3+4=7,      6+5=11,        10+6=16,        15+7=22

• a(0) = 0
• For every odd n (0-indexed), it's a(n-1) + X (where X=1 and increases by 1 every time it's accessed)
• For every even n (0-indexed), it's a(n-1) - 1

## Challenge:

One of:

• Given an input integer n, output the n'th number in the sequence.
• Given an input integer n, output the first n numbers of the sequence.
• Output the sequence indefinitely without taking an input (or taking an empty unused input).

## Challenge rules:

• Input n can be both 0- or 1-indexed.
• If you output (part of) the sequence, you can use a list/array, print to STDOUT with any delimiter (space, comma, newline, etc.). Your call.
• You'll have to support at least the first 10,000 numbers (10,000th number is 12,497,501).

## General rules:

• This is , so shortest answer in bytes wins.
Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.

## Test cases:

Pastebin with the first 10,001 numbers in the sequence. Feel free to pick any you'd like.

Some higher numbers:

n (0-indexed)    Output:

68,690           589,772,340
100,000          1,249,975,000
162,207          3,288,888,857
453,271          25,681,824,931
888,888          98,765,012,346
1,000,000        124,999,750,000


# Python 2, 3228 25 bytes

lambda n:(~-n|1)**2/8+n%2


Try it online!

Returns the n-th number (0-indexed)

# Excel, 31 bytes

Answer is 0 indexed. Outputs the nthe number.

=(A1^2+IF(ISODD(A1),7,-2*A1))/8


The sequence described is ultimately just two sequences interlaced:

ODD:   (x^2+x+2)/2
EVEN:  (x^2-x)/2


Interlacing these into one 0 indexed sequence gives:

a = (x^2 - 2x)/8 if even
a = (x^2 + 7 )/8 if odd


Which gives:

=IF(ISODD(A1),(A1^2+7)/8,(A1^2-2*A1)/8)


which we golf down to the 31 bytes.

Using the same approach, 1 indexed gives 37 bytes:

=(A1^2-IF(ISODD(A1),4*A1-3,2*A1-8))/8


# Jelly, 6 bytes

Rj-ḣ⁸S


Try it online!

0-indexed. Returns nth number.

Explanation:

Rj-ḣ⁸S Arguments: z
R      [1..x]: z (implicit)
j-    Join x with y: ^, -1
ḣ⁸  Take first y of x: ^, z
S Sum: ^


# JavaScript (Node.js), 23 bytes

x=>(7+(x-2|1)**2)/8-x%2


1-indexed. Try it online!

f(x) = f(x+1) + 1 if x is even
= SUM{1..(x-3)/2} if x is odd

SUM{1..(x-3)/2}
= (1+(x-3)/2)*((x-3)/2)/2
= (x-1)*(x-3)/8
= ((x-2)^2-1)/8


# Haskell, 40 38 37 bytes

scanl(flip($))0$[1..]>>=(:[pred]).(+)


Returns an infinite list, try it online!

### Explanation

scanl takes three arguments f, init and xs ([ x0, x1 ... ]) and builds a new list:

[ a0 = init, a1 = f(a0,x0), a2 = f(a1, x1) ... ]

We set init = 0 and use the flipped ($) application operator (thus it applies ai to the function xi), now we only need a list of functions - the list [1..]>>=(:[pred]).(+) is an infinite list with the right functions: [(+1),(-1),(+2),(-1),(+3),(-1),(+4),...  ### Interesting alternative, 37 bytes flip having the type (a -> b -> c) -> b -> a -> c we could also use id :: d -> d instead of ($) because of Haskell's type inference the type d would be unified with a -> b, giving us the same.

Try it online!

Edit

-2 bytes by using (>>=) instead of do-notation.

-1 byte by using scanl instead of zipWith.

# Jelly, 6 bytes

HḶS‘_Ḃ


A monadic link accepting (1-indexed) n which returns a(n).

Try it online! Or see the test-suite

### How?

HḶS‘_Ḃ - link: n
H      - halve         -> n/2.0
Ḷ     - lowered range -> [0,1,2,...,floor(n/2.0)-1]
S    - sum           -> TriangleNumber(floor(n/2.0)-1)
‘   - increment     -> TriangleNumber(floor(n/2.0)-1)+1
Ḃ - bit = 1 if n is odd, 0 if it's even
_  - subtract      -> TriangleNumber(floor(n/2.0)-1)+isEven(n)

• Hm, interesting approach right there. Commented Jun 1, 2018 at 7:24

scanl(+)0$(:[-1])=<<[1..]  Try it online! Constructs an infinite list. Haskell, 27 bytes 0:0%1 a%d=a+1:a:(a+d)%(d+1)  Try it online! Haskell, 30 bytes 0:do a<-scanl(+)0[1..];[a+1,a]  Try it online! # 05AB1E, 10 bytes ÎF<NÈi¼¾>+  Try it online! Explanation Î # initialize stack with: 0, input F # for N in [0 ... input-1] do: < # decrement the current number NÈi # if N is even ¼ # increment a counter ¾> # push counter+1 + # add to current number  Another 10-byter: ÎFNÈN;Ì*<O • ÎGDN+D< generates the sequence, but grabbing the nth element seems... hard in 3 bytes. Commented May 31, 2018 at 22:45 # Octave, 32 bytes @(x)fix((x-~(m=mod(x,2)))^2/8)+m  Try it online! Outputs the n-th number, 0-indexed. Uses the same formula as several other answers. # APL (Dyalog Unicode), 16 12 bytesSBCS Anonymous tacit prefix function. 0-indexed. +/⊢↑∘∊¯1,¨⍨⍳  Try it online! +/ the sum of ⊢↑ the first n elements ∘∊ of the ϵnlisted (flattened) ¯1,¨⍨ negative-one-appended-to-each ⍳ first n ɩndices (0 through n–1 • Ah, that was my solution...guess it was similar enough. Commented May 31, 2018 at 8:20 # PHP, 73645551 47 bytes # First method First code golf answer! I'm sure there's PHP tricks to make it shorter and the maths can probably be improved. Takes n as the first argument and outputs the nth number in the sequence. $y=$argv[1]/2;for(;$i<$y+1;)$x+=$i++;echo$x-($y|0);  Minus 9 bytes by removing "$x=0;" and "$i=0". Minus 9 bytes thanks to @Kevin Cruijssen improving the for loop and loss of the end tag. Minus 1 byte using bitwise or "|" rather than "(int)" Minus 3 bytes thanks to @Dennis as you can remove the tags by running it from the command line with "php -r 'code here'" Try it online! # Second method Matched my previous answer with a whole new method! for(;$i<$argv[1];$i++)$x+=($y^=1)?$i/2+1:-1;echo$x;


Using XOR and the tenary operator to switch between sums in the loop.

Edit: This doesn't work for n=0 and I have no idea why. $i isn't assigned so therefore it should be 0, therefore the loop ($i<$argv[1]) should fail as (0<0==false), therefore a non assigned$x should output as 0 and not 1.

Try it online!

# Third method

Converting the excel formula @Wernisch created to PHP gives a 47 byte solution

$z=$argv[1];echo(pow($z,2)+(($z&1)?7:-2*$z))/8;  Try it online! • Hi, welcome to PPCG! If you haven't yet, tips for golfing in PHP and tips for golfing in <all languages> might be interesting to read through. Some things to golf: you can remove the trailing ?>. Removing $x=0 and $i=0 is indeed allowed (if not, $x=$i=0 would have been shorter as well). Also, the loop can be shortened to for(;$i<$y+1;)$x+=$i++;. Which is -15 bytes in total. Enjoy your stay! :) Commented May 31, 2018 at 9:48 • @KevinCruijssen thanks very much! Commented May 31, 2018 at 10:03 • You're welcome. Btw, your TIO is currently still 60 bytes instead of 58. And not sure why you've stated 57. Try it online. Commented May 31, 2018 at 10:07 • @KevinCruijssen I kept posting the wrong TIO! TIO says 58 now but I've posted 55 as you can remove "php" from the opening tag, just not in TIO Commented May 31, 2018 at 10:14 • @Wernisch thanks for your formula! Commented May 31, 2018 at 22:58 # R, 35 bytes diffinv(rbind(n<-1:scan(),-1)[n-1])  Try it online! I thought this was an interesting alternative to @JayCe's answer since it doesn't port very well to languages without built-in support for matrices, and happens to be just as golfy. 1-indexed, returns the first n elements of the sequence. ### How it works: rbind(n<-1:scan(),-1) constructs the following matrix:  [,1] [,2] [,3] [,4] [1,] 1 2 3 4 [2,] -1 -1 -1 -1  Because R holds matrices in column-major order, if we were to convert this to a vector, we would obtain a vector 1 -1 2 -1 3 -1 4 -1  which if we take a cumulative sum of, we would get 1 0 2 1 4 3 7 6  which is the sequence, just without the leading 0. diffinv fortunately adds the leading zero, so we take the first n-1 values from the matrix and diffinv them, obtaining the first n values of the sequence. # R, 35 34 bytes (u=(n=scan())-n%%2-1)-n+(15+u^2)/8  Try it online! First output option.Same formula as many other answers (I'd like to point to the first answer providing the formula, I can't figure which it is). Second and third output options below: ### R, 43 bytes function(m,n=1:m,u=n%%2+1)((n-u)^2-1)/8+2-u  Try it online! ### R, 51 bytes while(T){cat(((T-(u=T%%2+1))^2-1)/8+2-u," ");T=T+1}  Try it online! # Matlab/Octave, 31 26 bytes 5 bytes saved thx to Luis Mendo! @(n)sum(1:n/2+.5)-fix(n/2)  • You can probably use fix instead of floor, and n/2+.5 instead of ceil(n/2) Commented May 31, 2018 at 22:45 • @LuisMendo Ty! Didn't know about fix() and didn't expect 1:n/2+.5 to work - so many things that could go wrong, but they actually don't :) Commented Jun 1, 2018 at 5:05 # Java (JDK 10), 20 bytes x->x%2+(x=~-x|1)*x/8  Try it online! Port of TFeld's Python 2 anwser, so go give them an upvote! ;) # Dodos, 69 bytes  . w w . h + r . ' dab h ' h h ' ' . dab r r dip . dot ' dip  Try it online! Somehow this is the longest answer. Explanation. ┌────┬─────────────────────────────────────────────────┐ │Name│Function │ ├────┼─────────────────────────────────────────────────┤ │. │Alias for "dot", computes the sum. │ ├────┼─────────────────────────────────────────────────┤ │' │Alias for "dip". │ ├────┼─────────────────────────────────────────────────┤ │r │Range from 0 to n, reversed. │ ├────┼─────────────────────────────────────────────────┤ │h │Halve - return (n mod 2) followed by (n/2) zeros.│ └────┴─────────────────────────────────────────────────┘  # QBasic 1.1, 49 bytes INPUT N R=1 FOR I=1TO N\2-1 R=R+I NEXT ?R-N MOD 2  1-indexed. # Uiua, 10 bytes +◿2./+⇡⌊÷2  Try it Based on Shaggy's Japt. Explanation: ⌊÷2  Floor divide by 2 /+⇡  Sum of this range +◿2.  Add the sum mod 2 # Vyxal, 6 bytes Þnuv∴¦  Try it Online! Outputs an infinite list. Þn # All integers, in order 0, 1, -1, 2, -2... v∴ # Max of each and u # -1 ¦ # Cumulative sum  # PowerShell Core, 26 bytes 0 for(){($c+=++$i) (--$c)}


Try it online!

Output the sequence indefinitely

# Vyxal, 6 bytes

½ɾ∑:∷+


Try it Online!

Now flagless, thanks to emanresu A's suggestion. This ties with their solution, though this is less clever.

I just like the :∷ :)

• ɾ floors its input, so this can be a flagless 6 Commented Apr 3 at 1:41
• 5 bytes flagless and a port of Erik's answer Commented Apr 3 at 3:48

# QBasic 1.1, 30 bytes

INPUT N
?(N-1OR 1)^2\8+N MOD 2


Uses TFeld's algorithm. 0-indexed.

# QBasic, 31 bytes

The just-implement-the-spec solution comes in slightly longer than Erik's solution.

DO
?n
i=i+1
n=n+i
?n
n=n-1
LOOP


This outputs indefinitely. For purposes of running it, I recommend changing the last line to something like LOOP WHILE INPUT\$(1) <> "q", which will wait for a keypress after every second sequence entry and exit if the key pressed is q.

# Japt-x, 6 bytes

Outputs the nth term, 1-indexed.

z oªUv


Try it

z oªUv     :Implicit input of integer U
z          :Floor divide by 2
o        :Range [0,Uz)
ª       :Logical OR of each with
Uv     :Parity of U
:Implicit output of sum


# C# (.NET Core), 56 bytes

n=>{int a=0,i=0;for(;++i<n;)a+=i%2<1?-1:i/2+1;return a;}


-2 bytes thanks to Kevin Crujssen

Try it online!

1 indexed. Returns a(n)

Ungolf'd:

int f(int n)
{
// a needs to be outside the for loop's scope,
// and it's golfier to also define i here
int a = 0, i = 1;
// basic for loop, no initializer because we already defined i
for (; ++i < n;)
{
if (i%2 < 1) {
// if i is even, subtract 1
a -= 1;
}
else
{
// if i is odd, add (i / 2) + 1
// this lets us handle X without defining another int
a += i / 2 + 1;
}
}
// a is the number at index n
return a;
}

• i=1;for(;i<n;i++) can be i=0;for(;++i<n;) and i%2==0 can be i%2<1. Commented May 31, 2018 at 13:40
• @KevinCruijssen so I can, thanks! I should've seen the 2nd one, but I didn't thnk the first one would work as I thought for loops only checked the conditional after the first loop. TIL Commented May 31, 2018 at 13:56
• Nope, it checks before the first iteration already. A do-while will check after completing the first iteration. :) Commented May 31, 2018 at 13:59
• In very rare cases you could even merge an if with a for-loop. For example: if(t>0)for(i=0;i<l;i++) to for(i=0;t>0&i<l;i++). I've almost never been able to use this in my answers, though. Commented May 31, 2018 at 14:02
• that's pretty awesome, I'll definitely have to keep that in mind next time I do C# golfing, which is quite rare these days :P most of my C# work is decidedly ungolfy Commented May 31, 2018 at 14:03

# Husk, 119 8 bytes

ΘṁṠe→Θ∫N


Saved a byte thanks to H.PWiz.
Outputs as an infinite list.
Try it online!

### Explanation

ΘṁṠe→Θ∫N
∫N   Cumulative sum of natural numbers (triangular numbers).
Θ     Prepend 0.
ṁṠe→      Concatenate [n + 1, n] for each.
Θ          Prepend 0.


# Jelly, 6 bytes

Return the first n numbers.

Rj-ÄŻḣ


Try it online!

• Very similar to EriktheOutgolfer's answer. Commented Jun 1, 2018 at 11:26

# ><>, 23 bytes

00v
1->:n9o{1+{{:{+:n9o


I've never done any ><> golfing before, so this can almost certainly be shorter! Is there any way to initialize the stack with two zeros on it?

Try it online!

# Brain-Flak, 68 42 bytes

{({}[()]<({}([{}]()))>)}{}({({}[()])}{}{})


Try it online!

# Charcoal, 15 bytes

Ｉ∨ΣＥＮ⎇﹪ι²±¹⊕⊘ι⁰


Try it online! 0-indexed. Link is to verbose version of code. The formula would probably be shorter, but what's the fun in that? Explanation:

    Ｎ           Input as a number
Ｅ            Map over implicit range
⎇          Ternary
﹪ι²       Current value modulo 2
±¹     If true (odd) then -1
⊕⊘ι  Otherwise calculate X as i/2+1
Σ             Take the sum
∨            ⁰ If the sum is empty then use zero
Ｉ               Cast to string and implicitly print