Ciclo aritmético

13

Entrada:

Entero nque es >=0o >=1( f(0)es opcional)

Salida:

El n'th número en la secuencia a continuación, O la secuencia hasta e incluyendo el n' th número.

Secuencia:

(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

¿Cómo se construye esta secuencia?

f(n=0) = 0(opcional)
f(n=1) = f(0) + no 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.

O en seudocódigo:

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
}

Pero como habrás notado, hay dos patrones en la secuencia:

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

por lo tanto, cualquier otro enfoque que dé como resultado la misma secuencia también es completamente correcto.

Reglas de desafío:

  • Las entradas indexadas 0 y 1 indexadas darán como resultado el mismo resultado (por lo que f(0)es opcional para las entradas indexadas 0 si desea incluirlo).
  • Se le permite generar el n'número de esta secuencia. O toda la secuencia e incluyendo el nnúmero 'th. (Por f(5)lo tanto, puede resultar en cualquiera 5o 0,1,-1,-3,0,5.)
    • Si elige generar la secuencia hasta e incluyendo el nnúmero 'th, el formato de salida es flexible. Puede ser una cadena delimitada por lista / matriz, coma / espacio / nueva línea o impresa en STDOUT, etc.
  • El divide ( /) es la división de entero / piso, que se redondea hacia 0 (no hacia el infinito negativo como es el caso en algunos idiomas).

Reglas generales:

  • Este es el , por lo que la respuesta más corta en bytes gana.
    No permita que los lenguajes de code-golf lo desanimen a publicar respuestas con lenguajes que no sean codegolfing. Trate de encontrar una respuesta lo más breve posible para 'cualquier' lenguaje de programación.
  • Se aplican reglas estándar para su respuesta, por lo que puede utilizar STDIN / STDOUT, funciones / método con los parámetros adecuados y programas completos de tipo retorno. Tu llamada.
  • Lagunas predeterminadas están prohibidas.
  • Si es posible, agregue un enlace con una prueba para su código.
  • Además, agregue una explicación si es necesario.

Casos de prueba adicionales anteriores n=100:

Input     Output

1000      0
100000    0
123       -123
1234      -1
12345     12345
123456    0
Kevin Cruijssen
fuente
1
No pude encontrar esto en oeis.org, por lo que es posible que desee enviarlo allí. Es una secuencia interesante, me sorprende que nadie la haya registrado.
tubería
1
@pipe parece bastante arbitrario
qwr

Respuestas:

20

JavaScript (ES6), 19 bytes

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

Pruébalo en línea!

Prueba

Supongamos que tenemos las siguientes relaciones para algunos n múltiplos de 4. Estas relaciones se verifican trivialmente para los primeros términos de la secuencia.

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

Y deja N = n + 4 . Entonces, por definición:

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)

Lo cual, por inducción matemática, prueba que las relaciones se mantienen para cualquier N múltiplo de 4 .

Arnauld
fuente
2
Debido a que la mayoría de las respuestas son puertos de esta solución, quiero agregar que he verificado que es comprobable.
Erik the Outgolfer
Tengo una prueba alternativa.
Erik the Outgolfer
Ah, loco, se distrajo con el trabajo mientras trabajaba en algo muy similar. +1
Shaggy
Por curiosidad, ¿hay alguna razón para preferir "n & 3" sobre "n% 4"?
IanF1
2
@ IanF1 Supongo que esto es solo un hábito de programación de bajo nivel (calcular un bit Y en el ensamblaje es más fácil y rápido que calcular un módulo). Pero no tiene mucho sentido aquí y en realidad estaba medio tentado de cambiarlo n%4después para que funcione con números mayores de 32 bits.
Arnauld
4

05AB1E , 8 bytes

Emite el nthnúmero

ÎD(®s)sè

Pruébalo en línea!

05AB1E , 14 bytes

Emite una lista de números hasta N usando los patrones en la secuencia

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

Pruébalo en línea!

Explicación

Ejemplo usando 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]
Emigna
fuente
4

Python 2 , 25 bytes

La respuesta del puerto de Arnauld:

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

Pruébalo en línea!


Soluciones ingenuas:

Python 3 , 50 49 bytes

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

Pruébalo en línea!


Python 2 , 78 77 76 58 57 53 52 bytes

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

Pruébalo en línea!

Usé un montón de bytes int, porque el piso de python se divide, y no hacia 0, como en la pregunta.

TFeld
fuente
@KevinCruijssen Sí, gracias :)
TFeld
3

TIS -n 2 1 , 123 bytes

Emite el nnúmero th para 0 <= n <= 999. (El límite superior se debe a limitaciones de idioma).

@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

Pruébalo en línea!


TIS -n 2 1 , 124 bytes

Emite el nnúmero th para 0 <= n <= 999. (El límite superior se debe a limitaciones de idioma). Se npueden proporcionar múltiples , separados por espacios en blanco.

@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

Pruébalo en línea!


TIS -n 3 1 , 192 bytes

Emite los valores 0..npara 0 <= n <= 999. (El límite superior se debe a limitaciones de idioma).

@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

Pruébalo en línea!


Todos usan E / S numérica (la -n bandera). Las dos primeras soluciones utilizan dos nodos de cálculo, uno colocado encima del otro. El tercero tiene una pila de tres nodos.

Para las dos primeras soluciones, el nodo superior lee la entrada, envía el número original, luego resta 4 repetidamente hasta que nos volvemos negativos, luego agrega 5 al índice para nuestra tabla de salto. Esto es equivalente a(n % 4) + 1 .

La tercera solución dividió esta tarea en dos nodos; el superior solo repite el límite hasta el final de los tiempos, y el nodo medio cuenta en paralelo el índice (en comparación con ese límite) y el módulo como se indicó anteriormente.

El nodo inferior de las tres soluciones es el mismo; tiene una mesa de salto, y aquí es donde sucede la magia. Almacenamos el número original enACC , entonces JRO(probablemente J UMP R elativo O ffset) presentada por 1, 2, 3, o4 , dependiendo de lo que dice el nodo anterior.

Trabajando hacia atrás:

  • 4hará una ) NEGcomió ACC, y b ) se mueven ACChacia abajo para la salida.
  • 3pondrá 1en ACC, a continuación, realizar los pasos 4una y 4b .
  • 2saltará directamente al paso 4b .
  • 1se SUBseparará ACC(efectivamente a cero ACC), luego hará un paso 2, que salta a 4b .
Phlarx
fuente
2

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

Pruébalo en línea!

Jonathan Frech
fuente
Podrías exactamente reducir a la mitad tu número de bytes (31 bytes) creando un puerto de la respuesta Java de OlivierGrégoire : f(n){n=n%2>0?n*(2-n%4):n%4/-2;}aunque lo agregaría como segunda respuesta, porque también me gusta tu enfoque recursivo. :)
Kevin Cruijssen
@KevinCruijssen Vi su solución Java 10 y noté su brevedad, aunque no quería simplemente copiar su solución, ya que las sintaxis aritméticas de los dos idiomas son demasiado similares.
Jonathan Frech
1

Retina , 46 bytes

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

_.*
0

Pruébalo en línea! Explicación:

.+
*

Convierte a unario.

r`(____)*$
_$.=

Convierta de nuevo a decimal, pero deje n%4+1subrayados.

____
-

En el caso de que sea 4, entonces el resultado es -n.

___.*
-1

Caso 3: -1

__

Caso 2: n

_.*
0

Caso 1: 0

Neil
fuente
1

Haskell , 50 bytes

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

Pruébalo en línea!

La solución de Arnauld, portada a Haskell es de 23 bytes:

z n=cycle[0,n,-1,-n]!!n
Angs
fuente
1

APL (Dyalog Classic) , 22 12 bytes

10 bytes masivos guardados debido a los comentarios de Erik the Outgolfer. ¡Gracias!

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

Pruébalo en línea!

Emite el enésimo número

No conozco APL, solo intenté hacer que mi puerto J de la solución de Arnauld funcione en Dyalog APL.

Galen Ivanov
fuente
2
Buen intento! Algunas observaciones: 1) Puede reemplazar (0,⍵,¯1,-⍵)con (0⍵¯1,-⍵). 2) Puede eliminar el 1+asumiendo que la ⎕IOvariable del sistema está asignada a 0(sí, eso está permitido). 3) Por lo general, no contamos la f←parte al enviar funciones. 4) Puede usar la función en lugar de []indexar. Todos juntos forman esto: ⎕IO←0(no cuentes esto){(4|⍵)⊃0⍵¯1,-⍵}
Erik the Outgolfer
@Erik the Outgolfer ¡Gracias!
Galen Ivanov
2
Más golf avanzado basado en este enfoque: 4∘|⊃0,⊢,¯1,-.
Erik the Outgolfer
1
@Erik the Outgolfer - ¡Sí, de hecho! Creo que tu 4∘|⊃0,⊢,¯1,- es exactamente como 4&|{0,],_1,-se vería mi solución J en APL. ¡Gracias de nuevo!
Galen Ivanov
1
En realidad, J es una variante APL, aunque más distante que otras más parecidas a APL como Dyalog y NARS2000.
Erik the Outgolfer
1

Cubix , 20 19 bytes

Iun:^>s1ns:u@Ota3s0

Pruébalo en línea!

Puertos el mismo enfoque para cubix.

En un cubo:

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

El primer bit ^Iu:n>s1ns:u0sconstruye la pila y luego 3atcopia el elemento apropiado a TOS, luego Ogenera y @finaliza el programa.

Giuseppe
fuente
0

Espacio en blanco, 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]

Se agregaron letras S(espacio), T(tabulación) y N(nueva línea) solo como resaltado.
[..._some_action]agregado solo como explicación.

Pruébalo en línea (solo con espacios en bruto, pestañas y nuevas líneas).

Puerto de la respuesta de JavaScript de @Arnauld .

Explicación (entrada de ejemplo 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

Se detiene con error: Salida no definida.

Kevin Cruijssen
fuente