21
\$\begingroup\$

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 , 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
\$\endgroup\$

39 Answers 39

10
\$\begingroup\$

Python 2, 32 28 25 bytes

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

Try it online!

Returns the n-th number (0-indexed)

\$\endgroup\$
8
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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: ^
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ ÎGDN+D< generates the sequence, but grabbing the nth element seems... hard in 3 bytes. \$\endgroup\$ – Magic Octopus Urn May 31 '18 at 22:45
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Ah, that was my solution...guess it was similar enough. \$\endgroup\$ – Erik the Outgolfer May 31 '18 at 8:20
3
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Hm, interesting approach right there. \$\endgroup\$ – Erik the Outgolfer Jun 1 '18 at 7:24
3
\$\begingroup\$

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!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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! :) \$\endgroup\$ – Kevin Cruijssen May 31 '18 at 9:48
  • \$\begingroup\$ @KevinCruijssen thanks very much! \$\endgroup\$ – Sam Dean May 31 '18 at 10:03
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen May 31 '18 at 10:07
  • \$\begingroup\$ @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 \$\endgroup\$ – Sam Dean May 31 '18 at 10:14
  • \$\begingroup\$ @Wernisch thanks for your formula! \$\endgroup\$ – Sam Dean May 31 '18 at 22:58
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

Matlab/Octave, 31 26 bytes

5 bytes saved thx to Luis Mendo!

@(n)sum(1:n/2+.5)-fix(n/2)
\$\endgroup\$
  • 1
    \$\begingroup\$ You can probably use fix instead of floor, and n/2+.5 instead of ceil(n/2) \$\endgroup\$ – Luis Mendo May 31 '18 at 22:45
  • \$\begingroup\$ @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 :) \$\endgroup\$ – Leander Moesinger Jun 1 '18 at 5:05
3
\$\begingroup\$

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

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

QBasic 1.1, 30 bytes

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

Uses TFeld's algorithm. 0-indexed.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ i=1;for(;i<n;i++) can be i=0;for(;++i<n;) and i%2==0 can be i%2<1. \$\endgroup\$ – Kevin Cruijssen May 31 '18 at 13:40
  • \$\begingroup\$ @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 \$\endgroup\$ – Skidsdev May 31 '18 at 13:56
  • \$\begingroup\$ Nope, it checks before the first iteration already. A do-while will check after completing the first iteration. :) \$\endgroup\$ – Kevin Cruijssen May 31 '18 at 13:59
  • \$\begingroup\$ 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. \$\endgroup\$ – Kevin Cruijssen May 31 '18 at 14:02
  • \$\begingroup\$ 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 \$\endgroup\$ – Skidsdev May 31 '18 at 14:03
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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.│
└────┴─────────────────────────────────────────────────┘
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 15 bytes

I∨ΣEN⎇﹪ι²±¹⊕⊘ι⁰

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
      ﹪ι²       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
I               Cast to string and implicitly print
\$\endgroup\$
1
\$\begingroup\$

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 !

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

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

\$\endgroup\$
1
\$\begingroup\$

J, 17 bytes

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

A port of Adám's APL solution.

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ +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É- \$\endgroup\$ – Kevin Cruijssen Jun 1 '18 at 7:40
  • \$\begingroup\$ @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 \$\endgroup\$ – Erik the Outgolfer Jun 1 '18 at 7:59
  • \$\begingroup\$ 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! \$\endgroup\$ – Kevin Cruijssen Jun 1 '18 at 9:53
1
\$\begingroup\$

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]%]-]
\$\endgroup\$
1
\$\begingroup\$

Jelly, 6 bytes

Return the first n numbers.

Rj-ÄŻḣ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ Very similar to EriktheOutgolfer's answer. \$\endgroup\$ – user202729 Jun 1 '18 at 11:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.