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-ḣ⁸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: ^

Answer 4

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 5

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

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È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

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

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!

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.

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)

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 N\2-1
R=R+I
NEXT
?R-N MOD 2

1-indexed.

Answer 18

QBasic 1.1, 30 bytes

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

Uses TFeld's algorithm. 0-indexed.

Answer 19

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 20

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

Answer 21

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 22

Jelly, 6 bytes

Return the first n numbers.

Rj-ÄŻḣ

Try it online!

Answer 23

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

Answer 24

JavaScript, 49 48 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 !

Answer 25

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

Answer 26

J, 17 bytes

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

A port of Adám's APL solution.

Try it online!

Answer 27

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

Answer 28

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
}

Answer 29

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.

Answer 30

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]%]-]