Encuentra la enésima suma alterna cruzada

17

Dada la entrada de un solo entero positivo, genera la "suma alterna cruzada" que corresponde a ese entero.

Tome el ejemplo de la entrada n=5. Para encontrar la suma alternativa cruzada, primero cree una cuadrícula cuadrada de ancho y alto nque, leyendo de izquierda a derecha y de arriba a abajo, comience 1y aumente en uno en cada posición:

 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25

Luego, tome las sumas de la cuadrícula que forman una "cruz" (es decir, ambas diagonales combinadas):

 1           5
    7     9
      13
   17    19
21          25

1 5 7 9 13 17 19 21 25

Finalmente, tome la suma alterna de esta secuencia:

1+5-7+9-13+17-19+21-25

-11

Otro ejemplo, para n=6(solo para mostrar cómo se ve la cruz para los pares n):

 1  2  3  4  5  6
 7  8  9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
25 26 27 28 29 30
31 32 33 34 35 36

 1              6
    8       11
      15 16
      21 22
   26       29
31             36

1+6-8+11-15+16-21+22-26+29-31+36

20

Como se trata de code-golf , ganará el código más corto en bytes.

Estas son las salidas correctas para n=1to n=100, que puede usar como casos de prueba:

1
4
-3
10
-11
20
-23
34
-39
52
-59
74
-83
100
-111
130
-143
164
-179
202
-219
244
-263
290
-311
340
-363
394
-419
452
-479
514
-543
580
-611
650
-683
724
-759
802
-839
884
-923
970
-1011
1060
-1103
1154
-1199
1252
-1299
1354
-1403
1460
-1511
1570
-1623
1684
-1739
1802
-1859
1924
-1983
2050
-2111
2180
-2243
2314
-2379
2452
-2519
2594
-2663
2740
-2811
2890
-2963
3044
-3119
3202
-3279
3364
-3443
3530
-3611
3700
-3783
3874
-3959
4052
-4139
4234
-4323
4420
-4511
4610
-4703
4804
-4899
5002
code-golf sequence Pomo de la puerta
fuente
8
Nit pick: Eso no es una suma alterna. Estás agregando los dos primeros términos.
Dennis

Respuestas:

26

Jalea, 21 19 11 10 7 bytes

²~³¡H+2

Pruébalo en línea!

Idea

Suponga por un segundo que el primer término de la suma final se resta en lugar de sumar.

Sea n un número entero positivo.

Incluso caso

 1              6
    8       11
      15 16
      21 22
   26       29
31             36

Las diferencias entre los elementos diagonales en la mitad inferior de las filas son los primeros n ÷ 2 números naturales impares. Como 1 + 3 + 5 +… + (2k + 1) = k 2 , suman (n ÷ 2) 2 = n 2 ÷ 4 .

En este ejemplo

- 1 + 6 - 8 + 11 - 15 + 16 - 21 + 22 - 26 + 29 - 31 + 36  =
-(1 - 6)-(8 - 11)-(15 - 16)-(21 - 22)-(26 - 29)-(31 - 36) =
(    5   +   3    +    1  )+(   1    +    3    +    5   ) =
             9             +              9               = 18

Por lo tanto, la suma es 2 × n 2 ÷ 4 = n 2 ÷ 2 .

Caso extraño

 1           5
    7     9
      13
   17    19
21          25

Las diferencias entre los elementos diagonales en las filas correspondientes de arriba y abajo ( 1y 5, y 21y 25; 7y 9, y 17y 19) son las mismas, por lo que se cancelarán en la suma alterna.

En este ejemplo

- 1 + 5 - 7 + 9 - 13 + 17 - 19 + 21 - 25  =
-(1 - 5)-(7 - 9)- 13 +(17 - 19)+(21 - 25) =
    4   +   2   - 13 -    2    -    4     = -13

Todo lo que queda es el negativo del elemento central, que es la media aritmética del primer y último número, por lo que se puede calcular como - (n 2 + 1) ÷ 2 .

Caso general

Dado que ~ x = - (x + 1) para enteros complementarios de dos ( ~ denota NO a nivel de bits), la fórmula para el caso impar se puede reescribir como ~ n 2 ÷ 2 .

Además, dado que el primer término ( 1 ) de la suma original se agrega en lugar de restar, las fórmulas anteriores dejan un error de 2 , que debe corregirse.

Por lo tanto, la enésima suma alternativa cruzada es n 2 ÷ 2 + 2 si n es par, y ~ n 2 ÷ 2 + 2 si es impar.

Finalmente, NO bit a bit es una involución, es decir, ~~ x = x para todo x . De esta manera ~~~ x = ~ x , ~~~~ x = x , y, en general, ~ n x (lo que significa que ~ se aplica n veces) es x si n es par y ~ x si es impar.

Por lo tanto, podemos reescribir nuestra fórmula general como ~ n n 2 ÷ 2 + 2 para todos los enteros positivos n .

Código

²~³¡H+2    Main link. Input: n

²          Yield n².
 ~         Apply bitwise NOT to n²...
  ³¡           n times.
    H      Halve the result.
     +2    Add 2.
Dennis
fuente
1
Sabía que había algún tipo de fórmula simple, pero su explicación y ejecución es simplemente increíble. +1
ETHproductions
5

JavaScript, 40 38 22 bytes

¡Usar esa solución nueva y elegante de forma cerrada es furor!

n=>(n%2?3-n*n:4+n*n)/2

Gracias a ThomasKwa, puedo eliminar mi costosa función recursiva.

Conor O'Brien
fuente
Solo necesita NO bit a bit una vez si n% 2. En realidad, creo que en JS podría ser más corto simplemente hacer(n%2?3-n*n:4+n*n)/2
lirtosiast
4

Jalea, 12 bytes

RṖµ²+‘×-*$SC

Pruébalo aquí .

lirtosiast
fuente
4

CJam, 13 15 bytes

ri2#_{~}*2/2+

Dos bytes de descuento gracias a Dennis.

Pruébalo en línea!

Luis Mendo
fuente
3
Mi primera respuesta CJam!
Luis Mendo
1
Reemplazar 2%{~}&con {~}*guarda dos bytes.
Dennis
@ Dennis Muy bien! ¡Gracias!
Luis Mendo
3

Minkolang 0.15 , 26 15 13 bytes

Usando el algoritmo loco de Dennis, y aproveché otros dos bytes gracias a él. ¡Ese tipo es responsable de reducir a la mitad el conteo de bytes!

n2;d[~]4+2:N.

Pruébalo aquí!

Explicación

@VoteToClose n^ 2, aplique bit a bit NO nveces, agregue cuatro, reduzca a la mitad. - Thomas Kwa hace 7 minutos

Vea la respuesta de Dennis para la explicación de por qué eso funciona. En un comentario sobre esta respuesta, sugirió otra mejora que funciona porque :es la división de enteros, por lo que puedo negar la parte superior de la pila y no preocuparme de que el +1 haga el complemento binario. Además, n y n ^ 2 tienen la misma paridad, lo que elimina la necesidad de un intercambio.

n                Take number from input - n
 2;              n**2
   d             Duplicates top of stack
    [~]          For loop that negates the top of stack n times
       4+        Add 4
         2:      Divide by 2
           N.    Output as number and stop.
El'endia Starman
fuente
2

GolfScript, 12 bytes

~2?.{~}*2/2+

Esto usa el algoritmo de mi respuesta Jelly . Pruébalo en línea!

Cómo funciona

~            # Evaluate the input.
 2?          # Square it.
   .         # Push a copy of the square.
    {~}      # Push a code block that applies bitwise NOT.
       *     # Execute it n² times. Since n² and n have the same parity,
             # this is equivalent to executing in only n times.
        2/   # Halve the result.
          2+ # Add 2.
Dennis
fuente
2

ES7, 17 bytes

n=>-1**n*n*n+4>>1

Puerto simple de la respuesta de @ Dennis Python 2.

Mientras escribía esta respuesta, ¡también logré jugar mi puerto ES6 a 17 bytes!

n=>(n*n^-n%2)/2+2
Neil
fuente
2

MATL , 13 27 bytes

Usando las increíbles fórmulas de Dennis:

2^t2\?Q_]2/2+

Pruébalo en línea!

Enfoque directo ( 27 bytes ):

2^:GtetXdwPXdhutn:-1w^!*s2+
Luis Mendo
fuente
2

Pure Bash, 28

Bueno, ahora que @Dennis nos ha mostrado a todos cómo hacer esto, esto necesita actualizarse:

echo $[-1**$1*($1*$1+1)/2+2]

Respuesta anterior:

Bash + utilidades GNU, 77

Aquí hay un comienzo:

a=$1
(seq 1 $[a+1] $[a*a]
seq $1 $[a>1?a-1:1] $[a*a])|sort -un|paste -sd+-|bc

N se pasa como un parámetro de línea de comandos.

pastees realmente útil aquí para producir la suma alterna. La -dopción permite una lista de caracteres separadores, que se usan cíclicamente.

Trauma digital
fuente
$[-1**$1*$1*$1+4>>1]Es aún más corto.
Neil
2

Julia, 41 40 25 19 16 bytes

n->-n%2$n^2÷2+2

Esta es una función anónima que acepta un entero y devuelve un entero. Para llamarlo, asígnelo a una variable.

El enfoque aquí, ideado por Dennis, es el siguiente. Primero obtenemos la paridad de n , es decir, n (mod 2), y la negamos. Esto nos da 0 para entradas pares y -1 para impares. Entonces XOR bit a bit con n 2 . Cuando n es par, esto es solo n 2 porque XOR con 0 es solo el número. Cuando n es impar, XOR con -1 es lo mismo que la negación bit a bit. Entonces, en este punto, tenemos n 2 o el NOT bit a bit de n 2 . Enteros dividimos esto entre 2 y sumamos 2 para obtener el resultado.

¡Ahorré un byte gracias a Sp3000 en una versión anterior y ahorré 9 gracias a Dennis en esta!

Alex A.
fuente
1

Jolf, 13 bytes

Pruébalo aquí!

½?mρj-3Qj+4Qj
 ?mρj         if parity of j
     -3Qj     return 3 - j*j
         +4Qj else return 4 + j*j
½             (and halve the result)
Conor O'Brien
fuente
1

Python 2, 24 bytes

lambda n:(-1)**n*n*n/2+2

Esto usa el algoritmo de mi respuesta Jelly , con una modificación menor:

En lugar de aplicar ~ n veces, aplicamos - n veces (multiplicando por (-1) n ). Esto es equivalente porque ~ x = -x - 1 y los pisos de división de enteros en Python, entonces ~ x / 2 = (-x - 1) / 2 = -x / 2 .

Dennis
fuente
1

Pyth, 11 bytes

+2/u_GQ*QQ2

Pruébelo en línea en el compilador Pyth .

Cómo funciona

Esto usa el algoritmo de mi respuesta Jelly , con una modificación menor:

En lugar de aplicar ~ n veces, aplicamos - n veces (multiplicando por (-1) n ). Esto es equivalente porque ~ x = -x - 1 y los pisos de división entera en Pyth, entonces ~ x / 2 = (-x - 1) / 2 = -x / 2 .

+2/u_GQ*QQ2  Evaluated input: Q

       *QQ   Yield Q².
   u  Q      Set G = Q². For each non-negative integer below Q:
    _G         Set G = -G.
             Return G.
  /       2  Halve the result.
+2           Add 2.
Dennis
fuente
1

dc, 17

Usando la misma fórmula probada de Dennis:

?dd*1+r_1r^*2/2+p

Pruébelo en línea Oh, ¿por qué no incluye el sandbox de Ideone bash?dc ?

Prueba de línea de comando:

for i in {1..100}; do echo $i | dc -e '?dd*1+r_1r^*2/2+p'; done
Trauma digital
fuente
?2^1+2~2*1-*2+pGuarda dos bytes.
Dennis
1

GS2, 9 bytes

V,@!α2+''

Esto usa el algoritmo de mi respuesta Jelly . Pruébalo en línea!

V,@e 7+''

es igualmente corto, pero notablemente no contiene caracteres no ASCII.

Cómo funciona

V          Parse the input as an integer n.
 ,         Compute n².
  @        Push a copy of n².
   !       Bitwise NOT.
    α      Make a block of the previous instruction.
     2     Execute the block n² times. Since n² and n have the same parity,
           this is equivalent to executing in only n times.
      +    Halve the result.
       ''  Increment twice.
Dennis
fuente
1

J, 16 bytes

[:<.2%~4+*:*_1^]

Esto usa el mismo algoritmo que mi respuesta Jelly. Prueba con J.js .

Dennis
fuente
0

Lua, 33 bytes ( Pruébelo en línea )

i=(...)print((-1)^i*i*i/2-.5*i%2)

Cómo funciona:

i=(...)print((-1)^i*i*i/2-.5*i%2)
i=(...)                           Take input and store to i
       print(
             (-1)^i               Raise (-1) to the i-th power: -1 if odd, 1 if even
                   *i*i/2         Multiply by i squared and halved.
                         -.5*i%2  i%2 is the remainder when i is divided by 2
                                  if i is odd, then i%2 will be 1, and this expression
                                  will evaluate to -0.5
                                  but if i is even, then i%2 will be 0, which makes
                                  this expression evaluate to 0
                                )
Monja permeable
fuente
0

Dyalog APL, 13 bytes

⌊2+.5××⍨ׯ1*⊢

Esto usa el mismo algoritmo que mi respuesta Jelly. Pruébelo en TryAPL .

Dennis
fuente