13
\$\begingroup\$

Input:

Integer n which is >=0 or >=1 (f(0) is optional)

Output:

The n'th number in the sequence below, OR the sequence up to and including the n'th number.

Sequence:

(0),1,-1,-3,0,5,-1,-7,0,9,-1,-11,0,13,-1,-15,0,17,-1,-19,0,21,-1,-23,0,25,-1,-27,0,29,-1,-31,0,33,-1,-35,0,37,-1,-39,0,41,-1,-43,0,45,-1,-47,0,49,-1,-51,0,53,-1,-55,0,57,-1,-59,0,61,-1,-63,0,65,-1,-67,0,69,-1,-71,0,73,-1,-75,0,77,-1,-79,0,81,-1,-83,0,85,-1,-87,0,89,-1,-91,0,93,-1,-95,0,97,-1,-99

How is this sequence build?

f(n=0) = 0 (optional)
f(n=1) = f(0) + n or f(n=1) = 1
f(n=2) = f(1) - n
f(n=3) = f(2) * n
f(n=4) = f(3) / n
f(n=5) = f(4) + n
etc.

Or in pseudo-code:

function f(integer n){
  Integer result = 0
  Integer i = 1
  Loop as long as i is smaller than or equal to n
  {
    if i modulo-4 is 1:
      result = result plus i
    if i modulo-4 is 2 instead:
      result = result minus i
    if i modulo-4 is 3 instead:
      result = result multiplied with i
    if i modulo-4 is 0 instead:
      result = result integer/floor-divided with i
    i = i plus 1
  }
  return result
}

But as you may have noted there are two patterns in the sequence:

0, ,-1,  ,0, ,-1,  ,0, ,-1,   ,0,  ,-1,   ,0,  ,-1,   ,...
 ,1,  ,-3, ,5,  ,-7, ,9,  ,-11, ,13,  ,-15, ,17,  ,-19,...

so any other approaches resulting in the same sequence are of course completely fine as well.

Challenge rules:

  • 0-indexed and 1-indexed inputs will result in the same result (which is why the f(0) is optional for 0-indexed inputs if you want to include it).
  • You are allowed to output the n'th number of this sequence. Or the entire sequence up and including the n'th number. (So f(5) can result in either 5 or 0,1,-1,-3,0,5.)
    • If you choose to output the sequence up to and including the n'th number, output format is flexible. Can be a list/array, comma/space/new-line delimited string or printed to STDOUT, etc.
  • The divide (/) is integer/floor division, which rounds towards 0 (not towards negative infinity as is the case in some languages).

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

Additional test cases above n=100:

Input     Output

1000      0
100000    0
123       -123
1234      -1
12345     12345
123456    0
\$\endgroup\$
  • 1
    \$\begingroup\$ I could not find this on oeis.org so you might want to submit it there. It's an interesting sequence, I'm surprised no one has registered it. \$\endgroup\$ – pipe Apr 13 '18 at 20:14
  • 1
    \$\begingroup\$ @pipe it seems pretty arbitrary \$\endgroup\$ – qwr Apr 14 '18 at 16:33

13 Answers 13

20
\$\begingroup\$

JavaScript (ES6), 19 bytes

n=>[0,n,-1,-n][n&3]

Try it online!

Proof

Let's assume that we have the following relations for some n multiple of 4. These relations are trivially verified for the first terms of the sequence.

f(n)   = 0
f(n+1) = n+1
f(n+2) = -1
f(n+3) = -(n+3)

And let N = n + 4. Then, by definition:

f(N)   = f(n+4) = f(n+3) // (n+4) = -(n+3) // (n+4) = 0
f(N+1) = f(n+5) = f(n+4) + (n+5)  = 0 + (n+5)       = N+1
f(N+2) = f(n+6) = f(n+5) - (n+6)  = (n+5) - (n+6)   = -1
f(N+3) = f(n+7) = f(n+6) * (n+7)  = -1 * (n+7)      = -(N+3)

Which, by mathematical induction, proves that the relations hold for any N multiple of 4.

\$\endgroup\$
  • 2
    \$\begingroup\$ Because most of the answers are ports of this solution, I want to add that I have verified it's provable. \$\endgroup\$ – Erik the Outgolfer Apr 13 '18 at 12:16
  • \$\begingroup\$ I have an alternative proof. \$\endgroup\$ – Erik the Outgolfer Apr 13 '18 at 13:00
  • \$\begingroup\$ Ah, nuts, got distracted by work while working on something very similar. +1 \$\endgroup\$ – Shaggy Apr 13 '18 at 14:12
  • \$\begingroup\$ Out of curiosity, is there a reason to prefer "n&3" over "n%4"? \$\endgroup\$ – IanF1 Apr 14 '18 at 9:24
  • 2
    \$\begingroup\$ @IanF1 I guess this is just a low-level programming habit (computing a bitwise AND in assembly is easier and faster than computing a modulo). But it doesn't make much sense here and I was actually half tempted to change it to n%4 afterwards so that it works with numbers larger than 32-bit. \$\endgroup\$ – Arnauld Apr 14 '18 at 9:32
4
\$\begingroup\$

05AB1E, 8 bytes

Outputs the nth number

ÎD(®s)sè

Try it online!

05AB1E, 14 bytes

Outputs a list of numbers upto N using the patterns in the sequence

ÅÉāÉ·<*āÉ<‚øí˜

Try it online!

Explanation

Example using N=7

ÅÉ               # List of odd numbers upto N
                 # STACK: [1,3,5,7]
  ā              # Enumerate 1-based
   É             # is odd?
                 # STACK: [1,3,5,7],[1,0,1,0]
    ·<           # double and decrement
                 # STACK: [1,3,5,7],[1,-1,1,-1]
      *          # multiply
                 # STACK: [1,-3,5,-7]
       āÉ<       # enumerate, isOdd, decrement
                 # STACK: [1,-3,5,-7],[0,-1,0,-1]
          ‚ø     # zip
                 # STACK: [[1, 0], [-3, -1], [5, 0], [-7, -1]]
            í    # reverse each
             ˜   # flatten
                 # RESULT: [0, 1, -1, -3, 0, 5, -1, -7]
\$\endgroup\$
4
\$\begingroup\$

Python 2, 25 bytes

Port of Arnauld's answer:

lambda n:[0,n,-1,-n][n%4]

Try it online!


Naive solutions:

Python 3, 50 49 bytes

lambda n:n and eval('int(f(n-1)%sn)'%'/+-*'[n%4])

Try it online!


Python 2, 78 77 76 58 57 53 52 bytes

lambda n:n and eval('int(1.*f(n-1)%sn)'%'/+-*'[n%4])

Try it online!

Used a bunch of bytes on int, because python floor divides, and not towards 0, as in the question.

\$\endgroup\$
  • \$\begingroup\$ @KevinCruijssen Yeah, thanks :) \$\endgroup\$ – TFeld Apr 13 '18 at 11:57
3
\$\begingroup\$

J, 12 bytes

Port of Arnauld's answer:

4&|{0,],_1,-

Try it online!

J, 28 bytes

Naive solution:

{(0 _1$~]),@,.(_1^i.)*1+2*i.

Outputs the nth number

Try it online!

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

TIS -n 2 1, 123 bytes

Outputs the nth number for 0 <= n <= 999. (The upper limit is due to language limitations).

@0
MOV UP ACC
MOV ACC ANY
L:SUB 4
JGZ L
JEZ L
ADD 5
JRO -5
@1
MOV UP ACC
JRO UP
SUB ACC
JRO 3
MOV 1 ACC
NEG
MOV ACC ANY
HCF

Try it online!


TIS -n 2 1, 124 bytes

Outputs the nth number for 0 <= n <= 999. (The upper limit is due to language limitations). Multiple n may be provided, separated by whitespace.

@0
MOV UP ACC
MOV ACC ANY
L:SUB 4
JGZ L
JEZ L
ADD 5
MOV ACC ANY
@1
MOV UP ACC
JRO UP
SUB ACC
JRO 3
MOV 1 ACC
NEG
MOV ACC ANY

Try it online!


TIS -n 3 1, 192 bytes

Outputs the values for 0..n for 0 <= n <= 999. (The upper limit is due to language limitations).

@0
MOV UP ACC
ADD 1
MOV ACC ANY
JRO -1
@1
SUB UP
JLZ C
HCF
C:ADD UP
MOV ACC ANY
ADD 1
SWP
ADD 1
MOV ACC ANY
SUB 4
JEZ W
ADD 4
W:SWP
@2
MOV UP ACC
JRO UP
SUB ACC
JRO 3
MOV 1 ACC
NEG
MOV ACC ANY

Try it online!


All use numeric I/O (the -n flag). The first two solutions use two compute nodes, one positioned above the other. The third has a stack of three nodes.

For the first two solutions, the upper node reads input, sends the original number on, then repeatedly subtracts 4 until we go negative, then adds 5 to index for our jump table. This is equivalent to (n % 4) + 1.

The third solution split this task across two nodes; the top one just repeats the limit until the end of time, and the middle node counts up in parallel the index (compared against that limit) and the modulo like above.

The lower node of all three solutions is the same; it has a jump table, and this is where the magic happens. We store the original number in ACC, then JRO (probably Jump Relative Offset) forward by 1, 2, 3, or 4, depending on what the node above says.

Working backward:

  • 4 will a) NEGate ACC, and b) move ACC down for output.
  • 3 will put 1 into ACC, then perform steps 4a and 4b.
  • 2 will jump directly to step 4b.
  • 1 will SUBtract ACC off itself (effectively zeroing ACC), then do step 2, which jumps to 4b.
\$\endgroup\$
2
\$\begingroup\$

C (gcc), 62 bytes

f(n,k){k=~-n;n=n?n%4?k%4?n-2&3?f(k)*n:f(k)-n:f(k)+n:f(k)/n:0;}

Try it online!

\$\endgroup\$
  • \$\begingroup\$ You could exactly halve your byte-count (31 bytes) by creating a port of OlivierGrégoire's Java answer: f(n){n=n%2>0?n*(2-n%4):n%4/-2;} I would add it as a second answer though, because I like your recursive approach as well. :) \$\endgroup\$ – Kevin Cruijssen Apr 13 '18 at 14:48
  • \$\begingroup\$ @KevinCruijssen I did see their Java 10 solution and noticed its brevity, though I did not want to simply copy their solution, as the two language's arithmetic syntaxes are too similar. \$\endgroup\$ – Jonathan Frech Apr 13 '18 at 19:02
1
\$\begingroup\$

Jelly, 8 bytes

,-;N;0⁸ị

Try it online!

-1 thanks to Lynn.

What others are doing (port of Arnauld's solution), supports 0.

Jelly, 17 bytes

A:A}××Ṡ¥
R_×ç+4ƭ/

Try it online!

0 is not supported.

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

Java (JDK 10), 25 bytes

n->n%2>0?n*(2-n%4):n%4/-2

Try it online!

Shorter than the contender algorithm in other languages with 28 bytes

n->new int[]{0,n,-1,-n}[n%4]

Try it online!

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

Retina, 46 bytes

.+
*
r`(____)*$
_$.=
____
-
___.*
-1
__

_.*
0

Try it online! Explanation:

.+
*

Convert to unary.

r`(____)*$
_$.=

Convert back to decimal, but leave n%4+1 underlines.

____
-

In the case that that's 4, then the result is -n.

___.*
-1

Case 3: -1

__

Case 2: n

_.*
0

Case 1: 0

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

Haskell, 50 bytes

f 0=0
f n=([(+),(-),(*),quot]!!mod(n-1)4)(f(n-1))n

Try it online!

Arnauld's solution, ported to Haskell is 23 bytes:

z n=cycle[0,n,-1,-n]!!n
\$\endgroup\$
1
\$\begingroup\$

APL (Dyalog Classic), 22 12 bytes

Massive 10 bytes saved due to Erik the Outgolfer's remarks. Thank you!

4∘|⊃0,⊢,¯1,-

Try it online!

Outputs the nth number

I don't know APL, I just tried to make my J port of Arnauld's solution work in Dyalog APL.

\$\endgroup\$
  • 2
    \$\begingroup\$ Nice attempt! A few remarks: 1) You can replace (0,⍵,¯1,-⍵) with (0⍵¯1,-⍵). 2) You can remove the 1+ by assuming that the ⎕IO system variable is assigned to 0 (yes, that's allowed). 3) We usually don't count the f← part when submitting functions. 4) You can use the function instead of [] indexing. All those together form this: ⎕IO←0 (don't count this) {(4|⍵)⊃0⍵¯1,-⍵} \$\endgroup\$ – Erik the Outgolfer Apr 13 '18 at 14:11
  • \$\begingroup\$ @Erik the Outgolfer Thank you! \$\endgroup\$ – Galen Ivanov Apr 13 '18 at 14:19
  • 2
    \$\begingroup\$ More advanced golfing based on this approach: 4∘|⊃0,⊢,¯1,-. \$\endgroup\$ – Erik the Outgolfer Apr 13 '18 at 15:15
  • 1
    \$\begingroup\$ @Erik the Outgolfer - Yes, indeed! I think your 4∘|⊃0,⊢,¯1,- is exactly what my J solution 4&|{0,],_1,- would look like in APL. Thanks again! \$\endgroup\$ – Galen Ivanov Apr 13 '18 at 15:32
  • 1
    \$\begingroup\$ Actually, J is an APL variant, although more distant than other more APL-like ones like Dyalog and NARS2000. \$\endgroup\$ – Erik the Outgolfer Apr 13 '18 at 15:36
1
\$\begingroup\$

Cubix, 20 19 bytes

Iun:^>s1ns:u@Ota3s0

Try it online!

Ports the same approach to cubix.

On a cube:

    I u
    n :
^ > s 1 n s : u
@ O t a 3 s 0 .
    . .
    . .

The first bit ^Iu:n>s1ns:u0s builds the stack and then 3at copies the appropriate item to TOS, then O outputs and @ ends the program.

\$\endgroup\$
0
\$\begingroup\$

Whitespace, 84 83 bytes

[S S S N
_Push_0][S N
S _Duplicate_0][T   T   S _Store][S S S T   S N
_Push_2][S S T  T   N
_Push_-1][T T   S _Store][S S S T   N
_Push_1][S N
S _Duplicate_1][T   N
T   T   _Read_STDIN_as_integer][S S S T T   N
_Push_3][S S S T    N
_Push_1][T  T   T   ][S S T T   N
_Push_-1][T S S N
_Multiply][T    T   S _Store][T T   T   _Retrieve_input][S S S T    S S N
_Push_4][T  S T T   _Modulo][T  T   T   _Retrieve_result][T N
S T _Print_as_integer]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Try it online (with raw spaces, tabs and new-lines only).

Port of @Arnauld's JavaScript answer.

Explanation (example input n=7):

Command   Explanation         Stack        Heap                  STDIN   STDOUT   STDERR

SSSN      Push 0              [0]
SNS       Duplicate top (0)   [0,0]
TTS       Store               []           {0:0}
SSSTSN    Push 2              [2]          {0:0}
SSTTN     Push -1             [2,-1]       {0:0}
TTS       Store               []           {0:0,2:-1}
SSSTN     Push 1              [1]          {0:0,2:-1}
SNS       Duplicate top (1)   [1,1]        {0:0,2:-1}
TNTT      Read STDIN as nr    [1]          {0:0,1:7,2:-1}        7
SSSTTN    Push 3              [1,3]        {0:0,1:7,2:-1}
SSSTN     Push 1              [1,3,1]      {0:0,1:7,2:-1}
TTT       Retrieve input      [1,3,7]      {0:0,1:7,2:-1}
SSTTN     Push -1             [1,3,7,-1]   {0:0,1:7,2:-1}
TSSN      Multiply (-1*7)     [1,3,-7]     {0:0,1:7,2:-1}
TTS       Store               [1]          {0:0,1:7,2:-1,3:-7}
TTT       Retrieve input      [7]          {0:0,1:7,2:-1,3:-7}
SSSTSSN   Push 4              [7,4]        {0:0,1:7,2:-1,3:-7}
TSST      Modulo (7%4)        [3]          {0:0,1:7,2:-1,3:-7}
TTT       Retrieve            [-7]         {0:0,1:7,2:-1,3:-7}
TNST      Print as integer    []           {0:0,1:7,2:-1,3:-7}           -7
                                                                                  error

Stops with error: Exit not defined.

\$\endgroup\$

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.