# 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. 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. 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. 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/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;$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) 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

# 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. 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 May 31, 2018 at 13:56
• Nope, it checks before the first iteration already. A do-while will check after completing the first iteration. :) 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. 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 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. Jun 1, 2018 at 11:26

# 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


# JavaScript, 4948 45 bytes

x=>eval('for(i=0,r=1;++i<x+2;)r+=i%2?-1:i/2')


Try it online!

Not as pretty as @tsh answer, but mine works for bigger numbers.

And now thanks @tsh, for the eval solution !

• <=x+1 can be <x+2 May 31, 2018 at 8:02
• x=>eval('for(i=0,r=1;++i<x+2;)r+=i%2?-1:i/2') should be shorter.
– tsh
May 31, 2018 at 8:11
• Does eval return the last modified value ? I still don't fully understand what it can do. May 31, 2018 at 8:16
• It return the value of statement (which may be covered in do statement in later version).
– tsh
May 31, 2018 at 8:26

# Befunge 93, 26 bytes

<v0p030
>:.130g+:30p+:.1-


Runs indefinitely
Try it online, though output gets a little wonky and goes back down after x=256, presumably TIO can't handle characters above U+256. Works fine at https://www.bedroomlan.org/tools/befunge-playground (Chrome only, unfortunately. With Firefox, endlines get removed at runtime, for some reason...)

# J, 17 bytes

1#.[{._1,@,.~1+i.


A port of Adám's APL solution.

Try it online!

# Pyth, 8 bytes

s<s,R_1S


Returns nth number in the sequence, 0-indexed. Try it online

Explanation, with example for n=5:

s<s,R_1SQQ   Final 2 Q's are implicit, Q=eval(input())

SQ    1-indexed range        [1,2,3,4,5]
,R_1      Map each to [n,-1]     [[1,-1],[2,-1],[3,-1],[4,-1],[5,-1]]
s          Sum (Flatten)          [1,-1,2,-1,3,-1,4,-1,5,-1]
<       Q   Take 1st Q             [1,-1,2,-1,3]
s            Sum, implicit output   4


# Perl 6,  38  26 bytes

{(0,{$_+(($+^=1)??++$!!-1)}...*)[$_]}


Try it

{(+^-$_+|1)**2 div 8+$_%2}


Based on reverse engineering TFeld's Python answer.
Try it

## Expanded

### 38 byte (sequence generator):

{  # bare block lambda with implicit parameter $_ ( # generate a new sequence everytime this function is called 0, # seed the sequence { # bare block that is used to generate the rest of the values$_  # parameter to this inner block (previous value)

+

(
# a statement that switches between (0,1) each time it is run
( $+^= 1 ) ?? # when it is 1 (truish) # a statement that increments each time it is run ++$ # &prefix:« ++ »( state $foo ) !! # or else subtract 1 -1 ) } ... # keep generating until: * # never stop )[$_ ] # index into the sequence
}


Note that this has the benefit that you can pass in * to get the entire sequence, or pass in a Range to more efficiently generate multiple values.

### 26 byte (direct calculation):

{  # bare block lambda with implicit parameter $_ ( +^ # numeric binary negate -$_  # negative of the input
+|   # numeric binary or
1

) ** 2   # to the power of 2

div 8     # integer divide it by 8

+ \$_ % 2  # add one if it is odd
}


# 05AB1E, 8 bytes

;L¨O>¹É-


Try it online!

Based on Jonathan Allan's Jelly approach (which was probably based on OP editing the question with another definition of the sequence), so 1-indexed.

• +1. I had a similar approach prepared in 05AB1E which I planned to post in a few days if no-one else posted one. It's slightly different (I first decrease the halve before creating the list, instead of removing the tail; and I use I instead of ¹), but the general approach and byte-count is exactly the same: ;<LO>IÉ- Jun 1, 2018 at 7:40
• @KevinCruijssen Would've posted yesterday if I had the ability to think more deeply, but, well, this is finals period, thinking too deeply about this is forbidden. :P Jun 1, 2018 at 7:59
• Ah, I'm glad I don't have finals anymore. I am pretty busy at work as well though, and have to postpone code-golf sometimes more often than I would like. ;p Good luck with your exams! Jun 1, 2018 at 9:53

# Convex, 10 9 bytes

_½,ª)\2%-


Try it online!

Based on Jonathan Allan's Jelly approach (which was probably based on OP editing the question with another definition of the sequence). 1-indexed.

Explanation:

_½,ª)\2%- Stack: [A]
_         Duplicate. Stack: [A A]
½        Halve. Stack: [A [A]½]
,       Range, [0..⌊N⌋). Stack: [A [[A]½],]
ª      Sum. Stack: [A [[A]½],]ª]
)     Increment. Stack: [A [[[A]½],]ª])]
\    Swap. Stack: [[[[A]½],]ª]) A]
2   2. Stack: [[[[A]½],]ª]) A 2]
%  Modulo. Stack: [[[[A]½],]ª]) [A 2]%]
- Minus. Stack: [[[[[A]½],]ª]) [A 2]%]-]