X Steps Forward, 1 Step Back

Question

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.
• Please state which of the three options you've used in your answer.
• You'll have to support at least the first 10,000 numbers (10,000th number is 12,497,501).

General rules:

• This is code-golf, 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.
• If possible, please add a link with a test for your code.
• Also, please add an explanation if possible.

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

Answer 1

Python 2, (削除) 32 (削除ここまで) (削除) 28 (削除ここまで) 25 bytes

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

Try it online!

Returns the n-th number (0-indexed)

Answer 2

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

Answer 3

Jelly, 6 bytes

Rj-ḣ8S

Try it online!

0-indexed. Returns nth number.

Explanation:

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

Answer 4

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 ([ x₀, x₁ ... ]) and builds a new list:

[ a₀ = init, a₁ = f(a₀,x₀), a₂ = f(a₁, x₁) ... ]

We set init = 0 and use the flipped ($) application operator (thus it applies a_i to the function x_i), 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.}

Answer 5

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

Answer 6

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)

• Erik the Outgolfer: Hm, interesting approach right there.

Answer 7

Haskell, 25 bytes

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!

Answer 8

05AB1E, 10 bytes

ÎF<NÈi1⁄43⁄4>+

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
 1⁄4 # increment a counter
 3⁄4> # push counter+1
 + # add to current number

Another 10-byter: ÎFNÈN;Ì*<O

• Magic Octopus Urn: ÎGDN+D< generates the sequence, but grabbing the nth element seems... hard in 3 bytes.

Answer 9

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.

Answer 10

APL (Dyalog Unicode), (削除) 16 (削除ここまで) 12 bytes ^SBCS

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

• Erik the Outgolfer: Ah, that was my solution...guess it was similar enough.

Answer 11

PHP, (削除) 73 (削除ここまで) (削除) 64 (削除ここまで) (削除) 55 (削除ここまで) (削除) 51 (削除ここまで) 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!

• Kevin Cruijssen: 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! :)
• Sam Dean: @KevinCruijssen thanks very much!
• Kevin Cruijssen: 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.
• Sam Dean: @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
• Sam Dean: @Wernisch thanks for your formula!

Answer 12

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.

• JayCe: I am a big fan of your 'diffinv' answers.
• Giuseppe: @JayCe credit to user2390246 for introducing diffinv to me!

Answer 13

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!

Answer 14

Matlab/Octave, (削除) 31 (削除ここまで) 26 bytes

5 bytes saved thx to Luis Mendo!

@(n)sum(1:n/2+.5)-fix(n/2)

• Luis Mendo: You can probably use fix instead of floor, and n/2+.5 instead of ceil(n/2)
• Leander Moesinger: @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 :)

Answer 15

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! ;)

Answer 16

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.│
└────┴─────────────────────────────────────────────────┘

Answer 17

QBasic 1.1, 49 bytes

INPUT N
R=1
FOR I=1TO N2円-1
R=R+I
NEXT
?R-N MOD 2

1-indexed.

Answer 18

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

Answer 19

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

Answer 20

PowerShell Core, 26 bytes

0
for(){($c+=++$i)
(--$c)}

Try it online!

Output the sequence indefinitely

Answer 21

Vyxal, 6 bytes

1⁄2ɾ∑:∷+

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 :∷ :)

• emanresu A: ɾ floors its input, so this can be a flagless 6
• lyxal: 5 bytes flagless and a port of Erik's answer

Answer 22

QBasic 1.1, 30 bytes

INPUT N
?(N-1OR 1)^28円+N MOD 2

Uses TFeld's algorithm. 0-indexed.

Answer 23

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.

Answer 24

Japt -x, 6 bytes

Outputs the nth term, 1-indexed.

z oaUv

Try it

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

Answer 25

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;
}

• Kevin Cruijssen: i=1;for(;i<n;i++) can be i=0;for(;++i<n;) and i%2==0 can be i%2<1.
• Mayube: @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
• Kevin Cruijssen: Nope, it checks before the first iteration already. A do-while will check after completing the first iteration. :)
• Kevin Cruijssen: 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.
• Mayube: 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

Answer 26

Husk, (削除) 11 (削除ここまで) (削除) 9 (削除ここまで) 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.

Answer 27

Jelly, 6 bytes

Return the first n numbers.

Rj-ÄŻḣ

Try it online!

• user202729: Very similar to EriktheOutgolfer's answer.

Answer 28

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

Answer 29

Brain-Flak, (削除) 68 (削除ここまで) 42 bytes

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

Try it online!

Answer 30

Charcoal, 15 bytes

I∨ΣEN⎇%ι2±1⊕⊘ι0

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:

 N Input as a number
 E Map over implicit range
 ⎇ Ternary
 %ι2 Current value modulo 2
 ±1 If true (odd) then -1
 ⊕⊘ι Otherwise calculate X as i/2+1
 Σ Take the sum
 ∨ 0 If the sum is empty then use zero
I Cast to string and implicitly print