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

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 7

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

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 10

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 11

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 12

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 13

Matlab/Octave, 31 26 bytes

5 bytes saved thx to Luis Mendo!

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

Answer 14

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 15

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 16

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 17

QBasic 1.1, 30 bytes

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

Uses TFeld's algorithm. 0-indexed.

Answer 18

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 19

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 20

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 21

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 22

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

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 25

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 26

J, 17 bytes

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

A port of Adám's APL solution.

Try it online!

Answer 27

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

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

Jelly, 6 bytes

Return the first n numbers.

Rj-ÄŻḣ

Try it online!

Answer 31

Oasis, 7 bytes

>vLSnv-

Try it online!

---

Sequential solution

Oasis, 12 bytes

bn>v>n2%*<+0

Try it online!

Answer 32

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

Stax, 7 bytes

é╛▼¥,▐_

Run and debug it

Answer 34

APL (Dyalog Classic), 9 bytes

+\¯1⌈-\∘⍳

Try it online!

uses ⎕io←1

Answer 35

GMS2, 39 bytes

a=argument0 return a*a/8+(a mod 2?7:a*-2)/8

With GMS1 it takes 43 bytes:

a=argument0 b=a*-2if a mod 2b=7return a*a/8+b/8

Answer 36

Charm, 64 bytes

1 setref [ 1 ] [ 0 getref + put 1 - put 0 [ 1 + ] modref ] while

Try it online!

Answer 37

Ruby, 21 bytes

A straight port of TFeld's answer also works in Ruby:

->n{(~-n|1)**2/8+n%2}

Try it online!

Answer 38

Brain-Flak, 68 42 bytes

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

Try it online!

Answer 39

Common Lisp, 75 bytes

(defun f(n)(+(/((lambda(x)(*(- x 1)x))(+(floor n 2)(mod n 2)))2)(mod n 2)))

Try it online!

Not the best. I'm still learning Lisp.