Trouver la nième somme croisée

17

Étant donné l'entrée d'un seul entier positif, sortez la "somme croisée" qui correspond à cet entier.

Prenons l'exemple de l'entrée n=5. Pour trouver la somme croisée, créez d'abord une grille carrée de largeur et de hauteur nqui, en lisant de gauche à droite et de haut en bas, commence à 1et augmente d'une position à chaque:

 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

Ensuite, prenez les sommes de la grille qui forment une "croix" (c'est-à-dire les deux diagonales combinées):

 1           5
    7     9
      13
   17    19
21          25

1 5 7 9 13 17 19 21 25

Enfin, prenez la somme alternée de cette séquence:

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

-11

Un autre exemple, pour n=6(juste pour montrer à quoi ressemble la croix pour les nombres pairs 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

Puisqu'il s'agit de , le code le plus court en octets gagnera.

Voici les sorties correctes pour n=1to n=100, que vous pouvez utiliser comme cas de test:

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
Poignée de porte
la source
8
Nit pick: Ce n'est pas une somme alternée. Vous ajoutez les deux premiers termes.
Dennis

Réponses:

26

Gelée, 21 19 11 10 7 octets

²~³¡H+2

Essayez-le en ligne!

Idée

Supposons une seconde que le premier terme de la somme finale est soustrait plutôt que ajouté.

Soit n un entier positif.

Même cas

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

Les différences entre les éléments diagonaux dans la moitié inférieure des rangées correspondent aux n ÷ 2 premiers nombres naturels impairs. Puisque 1 + 3 + 5 +… + (2k + 1) = k 2 , ils totalisent (n ÷ 2) 2 = n 2 ÷ 4 .

Dans cet exemple

- 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

Ainsi, la somme est 2 × n 2 ÷ 4 = n 2 ÷ 2 .

Cas étrange

 1           5
    7     9
      13
   17    19
21          25

Les différences entre les éléments diagonaux sur les lignes correspondantes d'en haut et en bas ( 1et 5, et 21et 25; 7et 9, et 17et 19) sont les mêmes, ils s'annuleront donc dans la somme alternée.

Dans cet exemple

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

Il ne reste que le négatif de l'élément central, qui est la moyenne arithmétique du premier et du dernier nombre, de sorte qu'il peut être calculé comme - (n 2 + 1) ÷ 2 .

Cas général

Étant donné que ~ x = - (x + 1) pour les entiers de complément à deux ( ~ indique NON au niveau du bit), la formule pour le cas impair peut être réécrite comme ~ n 2 ÷ 2 .

De plus, comme le premier terme ( 1 ) de la somme d'origine est ajouté au lieu d'être soustrait, les formules ci-dessus laissent une erreur de 2 , qui doit être corrigée.

Par conséquent, la n e somme croisée est n 2 ÷ 2 + 2 si n est pair, et ~ n 2 ÷ 2 + 2 s'il est impair.

Enfin, NOT au niveau du bit est une involution, c'est-à-dire ~~ x = x pour tout x . De cette façon ~~~ x = ~ x , ~~~~ x = x , et, en général, ~ n x (ce qui signifie que ~ est appliqué n fois) est x si n est pair et ~ x s'il est impair.

Ainsi, nous pouvons réécrire notre formule générale comme ~ n n 2 ÷ 2 + 2 pour tous les entiers positifs n .

Code

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

²          Yield n².
 ~         Apply bitwise NOT to n²...
  ³¡           n times.
    H      Halve the result.
     +2    Add 2.
Dennis
la source
1
Je savais qu'il y avait une sorte de formule simple, mais votre explication et votre exécution sont tout simplement incroyables. +1
ETHproductions
5

JavaScript, 40 38 22 octets

En utilisant cette nouvelle solution de forme fermée fantaisie qui fait fureur!

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

Grâce à ThomasKwa, je peux éliminer ma fonction récursive coûteuse.

Conor O'Brien
la source
Il vous suffit de NE PAS bit à bit une fois si n% 2. En fait, je pense que dans JS, il pourrait être plus court de le faire(n%2?3-n*n:4+n*n)/2
lirtosiast
4

Gelée, 12 octets

RṖµ²+‘×-*$SC

Essayez-le ici .

lirtosiast
la source
4

CJam, 13 15 octets

ri2#_{~}*2/2+

Deux octets de moins grâce à Dennis.

Essayez-le en ligne!

Luis Mendo
la source
3
Ma première réponse CJam!
Luis Mendo
1
Le remplacement 2%{~}&par {~}*enregistre deux octets.
Dennis
@Dennis Très bien! Merci!
Luis Mendo
3

Minkolang 0,15 , 26 15 13 octets

En utilisant l'algorithme insensé de Dennis, et grâce à lui, il a joué encore deux octets. Ce mec est responsable de réduire de moitié le nombre d'octets!

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

Essayez-le ici!

Explication

@VoteToClose n^ 2, appliquez des ntemps NON au niveau du bit , ajoutez quatre, divisez par deux. - Thomas Kwa Il y a 7 minutes

Voir la réponse de Dennis pour l'explication de pourquoi cela fonctionne. Dans un commentaire sur cette réponse, il a suggéré une autre amélioration qui fonctionne parce que :c'est la division entière, donc je peux annuler le haut de la pile et ne pas me soucier du +1 de faire le complément binaire. De plus, n et n ^ 2 ont la même parité, ce qui supprime la nécessité d'un swap.

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
la source
2

GolfScript, 12 octets

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

Cela utilise l'algorithme de ma réponse Jelly . Essayez-le en ligne!

Comment ça fonctionne

~            # 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
la source
2

ES7, 17 octets

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

Port simple de @ Dennis's Python 2 answer.

En écrivant cette réponse, j'ai réussi à jouer mon port ES6 à 17 octets aussi!

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

MATL , 13 27 octets

En utilisant les formules étonnantes de Dennis:

2^t2\?Q_]2/2+

Essayez-le en ligne!

Approche directe ( 27 octets ):

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

Pure Bash, 28

Eh bien maintenant que @Dennis nous a montré comment faire cela, cela doit être mis à jour:

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

Réponse précédente:

Utilitaires Bash + GNU, 77

Voici un début:

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

N est passé en tant que paramètre de ligne de commande.

pasteest vraiment pratique ici pour produire la somme alternée. L' -doption permet une liste de caractères de séparation, qui sont utilisés de manière cyclique.

Traumatisme numérique
la source
$[-1**$1*$1*$1+4>>1]est encore plus court.
Neil
2

Julia, 41 40 25 19 16 octets

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

Il s'agit d'une fonction anonyme qui accepte un entier et renvoie un entier. Pour l'appeler, affectez-le à une variable.

L'approche ici, conçue par Dennis, est la suivante. D'abord, nous obtenons la parité de n , c'est-à-dire n (mod 2), et la nions. Cela nous donne 0 pour les entrées paires et -1 pour les impaires. Nous avons ensuite XOR au niveau du bit avec n 2 . Lorsque n est pair, ce n'est que n 2 car XOR avec 0 n'est que le nombre. Lorsque n est impair, XOR avec -1 est identique à la négation au niveau du bit. Donc, à ce stade, nous avons soit n 2, soit le NOT binaire de n 2 . Nous divisons cet entier par 2 et ajoutons 2 pour obtenir le résultat.

Enregistré un octet grâce à Sp3000 sur une version précédente, et enregistré 9 grâce à Dennis sur celle-ci!

Alex A.
la source
1

Jolf, 13 octets

Essayez-le ici!

½?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
la source
1

Python 2, 24 octets

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

Il utilise l'algorithme de ma réponse Jelly , avec une modification mineure:

Au lieu d'appliquer ~ n fois, nous appliquons - n fois (en multipliant par (-1) n ). C'est équivalent car ~ x = -x - 1 et les étages de division entiers en Python, donc ~ x / 2 = (-x - 1) / 2 = -x / 2 .

Dennis
la source
1

Pyth, 11 octets

+2/u_GQ*QQ2

Essayez-le en ligne dans le compilateur Pyth .

Comment ça fonctionne

Cela utilise l'algorithme de ma réponse Jelly , avec une modification mineure:

Au lieu d'appliquer ~ n fois, nous appliquons - n fois (en multipliant par (-1) n ). C'est équivalent car ~ x = -x - 1 et les étages de division entiers en Pyth, donc ~ 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
la source
1

dc, 17

En utilisant la même formule éprouvée de Dennis:

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

Essayez-le en ligne Oh, pourquoi le bac à sable Ideone bash ne comprend-il pas dc?

Test en ligne de commande:

for i in {1..100}; do echo $i | dc -e '?dd*1+r_1r^*2/2+p'; done 
Traumatisme numérique
la source
?2^1+2~2*1-*2+penregistre deux octets.
Dennis
1

GS2, 9 octets

V,@!α2+''

Cela utilise l'algorithme de ma réponse Jelly . Essayez-le en ligne!

V,@e 7+''

est également court, mais ne contient notamment aucun caractère non ASCII.

Comment ça fonctionne

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
la source
1

J, 16 octets

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

Cela utilise le même algorithme que ma réponse Jelly. Testez - le avec J.js .

Dennis
la source
0

Lua, 33 octets ( Essayez-le en ligne )

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

Comment ça fonctionne:

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
                                )
Leaky Nun
la source
0

Dyalog APL, 13 octets

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

Cela utilise le même algorithme que ma réponse Jelly. Testez-le sur TryAPL .

Dennis
la source