18
\$\begingroup\$

Given an input of a single positive integer, output the "cross-alternate sum" that corresponds to that integer.

Take the example of the input n=5. To find the cross-alternate sum, first create a square grid of width and height n that, reading from left to right and top to bottom, starts at 1 and increases by one each position:

 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

Then, take the sums from the grid that form a "cross" (that is, both diagonals combined):

 1           5
    7     9
      13
   17    19
21          25

1 5 7 9 13 17 19 21 25

Finally, take the alternating sum of this sequence:

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

-11

Another example, for n=6 (just to show what the cross looks like for even-numbered 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

Since this is , the shortest code in bytes will win.

Here are the correct outputs for n=1 to n=100, which you can use as test cases:

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
\$\endgroup\$
1
  • 8
    \$\begingroup\$ Nit pick: That's not an alternating sum. You're adding the first two terms. \$\endgroup\$
    – Dennis
    Feb 6, 2016 at 1:10

18 Answers 18

26
\$\begingroup\$

Jelly, 21 19 11 10 7 bytes

²~³¡H+2

Try it online!

Idea

Assume for a second that the first term of the final sum is subtracted rather than added.

Let n be a positive integer.

Even case

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

The differences between the diagonal elements on the lower half of the rows are the first n ÷ 2 odd natural numbers. Since 1 + 3 + 5 + … + (2k + 1) = k2, they sum to (n ÷ 2)2 = n2 ÷ 4.

In this example

- 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

Thus, the sum is 2 × n2 ÷ 4 = n2 ÷ 2.

Odd case

 1           5
    7     9
      13
   17    19
21          25

The differences between the diagonal elements on the corresponding rows from above and below (1 and 5, and 21 and 25; 7 and 9, and 17 and 19) is the same, so they will cancel out in the alternating sum.

In this example

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

All that's left is the negative of the central element, which is the arithmetic mean of the first and last number, so it can be calculated as -(n2 + 1) ÷ 2.

General case

Since ~x = -(x + 1) for two's complement integers (~ denotes bitwise NOT), the formula for the odd case can be rewritten as ~n2 ÷ 2.

Also, since the first term (1) of the original sum is added instead of subtracted, the above formulas leave an error of 2, which has to be corrected.

Therefore, the nth cross-alternate sum is n2 ÷ 2 + 2 if n is even, and ~n2 ÷ 2 + 2 if it is odd.

Finally, bitwise NOT is an involution, i.e., ~~x = x for all x. This way ~~~x = ~x, ~~~~x = x, and, in general, ~nx (meaning that ~ is applied n times) is x if n is even and ~x if it is odd.

Thus, we can rewrite our general formula as ~nn2 ÷ 2 + 2 for all positive integers n.

Code

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

²          Yield n².
 ~         Apply bitwise NOT to n²...
  ³¡           n times.
    H      Halve the result.
     +2    Add 2.
\$\endgroup\$
1
  • 1
    \$\begingroup\$ I knew there was some sort of simple formula, but your explanation and execution is just amazing. +1 \$\endgroup\$ Feb 6, 2016 at 3:25
5
\$\begingroup\$

JavaScript, 40 38 22 bytes

Using that new-fangled, fancy closed form solution that's all the rage!

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

Thanks to ThomasKwa, I can eliminate my costly recursive function.

\$\endgroup\$
1
  • \$\begingroup\$ You just need to bitwise NOT once if n%2. Actually, I think in JS it might be shorter to just do (n%2?3-n*n:4+n*n)/2 \$\endgroup\$
    – lirtosiast
    Feb 6, 2016 at 2:07
4
\$\begingroup\$

Jelly, 12 bytes

RṖµ²+‘×-*$SC

Try it here.

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

CJam, 13 15 bytes

ri2#_{~}*2/2+

Two bytes off thanks to Dennis.

Try it online!

\$\endgroup\$
3
  • 3
    \$\begingroup\$ My first CJam answer! \$\endgroup\$
    – Luis Mendo
    Feb 6, 2016 at 17:01
  • 1
    \$\begingroup\$ Replacing 2%{~}& with {~}* saves two bytes. \$\endgroup\$
    – Dennis
    Feb 6, 2016 at 21:41
  • \$\begingroup\$ @Dennis Very good! Thanks! \$\endgroup\$
    – Luis Mendo
    Feb 7, 2016 at 4:19
3
\$\begingroup\$

Minkolang 0.15, 26 15 13 bytes

Using Dennis' insane algorithm, and golfed off another two bytes thanks to him. That guy is responsible for halving of byte count!

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

Try it here!

Explanation

@VoteToClose n^2, apply bitwise NOT n times, add four, halve. – Thomas Kwa 7 mins ago

See Dennis' answer for the explanation of why that works. In a comment on this answer, he suggested another improvement that works because : is integer division, so I can negate the top of stack and not worry about the +1 from doing the binary complement. Furthermore, n and n^2 have the same parity, which removes the need for a 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.
\$\endgroup\$
0
2
\$\begingroup\$

GolfScript, 12 bytes

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

This uses the algorithm from my Jelly answer. Try it online!

How it works

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

ES7, 17 bytes

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

Simple port of @Dennis's Python 2 answer.

While writing this answer I managed to golf my ES6 port to 17 bytes too!

n=>(n*n^-n%2)/2+2
\$\endgroup\$
2
\$\begingroup\$

MATL, 13 27 bytes

Using Dennis' amazing formulas:

2^t2\?Q_]2/2+

Try it online!

Direct approach (27 bytes):

2^:GtetXdwPXdhutn:-1w^!*s2+
\$\endgroup\$
2
\$\begingroup\$

Pure Bash, 28

Well now that @Dennis has showed us all how to do this, this needs updating:

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

Previous answer:

Bash + GNU utilities, 77

Here's a start:

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

N is passed as a command-line parameter.

paste is really handy here for producing the alternating sum. The -d option allows a list of separator characters, which are used cyclically.

\$\endgroup\$
1
  • \$\begingroup\$ $[-1**$1*$1*$1+4>>1] is even shorter. \$\endgroup\$
    – Neil
    Feb 7, 2016 at 1:06
2
\$\begingroup\$

Julia, 41 40 25 19 16 bytes

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

This is an anonymous function that accepts an integer and returns an integer. To call it, assign it to a variable.

The approach here, devised by Dennis, is as follows. First we get the parity of n, i.e. n (mod 2), and negate it. This gives us 0 for even inputs and -1 for odd. We then bitwise XOR with n2. When n is even, this is just n2 because XOR with 0 is just the number. When n is odd, XOR with -1 is the same as bitwise negation. So at this point we either have n2 or the bitwise NOT of n2. We integer divide this by 2 and add 2 to get the result.

Saved a byte thanks to Sp3000 on a previous version, and saved 9 thanks to Dennis on this one!

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

Jolf, 13 bytes

Try it here!

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

Python 2, 24 bytes

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

This uses the algorithm from my Jelly answer, with a minor modification:

Instead of applying ~ n times, we apply - n times (by multiplying by (-1)n). This is equivalent because ~x = -x - 1 and integer division floors in Python, so ~x / 2 = (-x - 1) / 2 = -x / 2.

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

Pyth, 11 bytes

+2/u_GQ*QQ2

Try it online in the Pyth Compiler.

How it works

This uses the algorithm from my Jelly answer, with a minor modification:

Instead of applying ~ n times, we apply - n times (by multiplying by (-1)n). This is equivalent because ~x = -x - 1 and integer division floors in Pyth, so ~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.
\$\endgroup\$
1
\$\begingroup\$

dc, 17

Using the same tried and tested formula from Dennis:

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

Try it online Oh, why doesn't the Ideone bash sandbox include dc?

Command-line Test:

for i in {1..100}; do echo $i | dc -e '?dd*1+r_1r^*2/2+p'; done 
\$\endgroup\$
1
  • \$\begingroup\$ ?2^1+2~2*1-*2+p saves two bytes. \$\endgroup\$
    – Dennis
    Feb 7, 2016 at 2:17
1
\$\begingroup\$

GS2, 9 bytes

V,@!α2+''

This uses the algorithm from my Jelly answer. Try it online!

V,@e 7+''

is equally short, but notably contains no non-ASCII characters.

How it works

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

J, 16 bytes

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

This uses the same algorithm as my Jelly answer. Test it with J.js.

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

Lua, 33 bytes (Try it online)

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

How it works:

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

Dyalog APL, 13 bytes

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

This uses the same algorithm as my Jelly answer. Test it on TryAPL.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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