Summing a sub-square of a quarter of an infinite chessboard

Question

Description of the problem

Imagine a quarter of an infinite chessboard, as in a square grid, extending up and right, so that you can see the lower left corner. Place a 0 in there. Now for every other cell in position (x,y), you place the smallest non-negative integer that hasn't showed up in the column x or the row y.

It can be shown that the number in position (x, y) is x ^ y, if the rows and columns are 0-indexed and ^ represents bitwise xor.

Task

Given a position (x, y), return the sum of all elements below that position and to the left of that position, inside the square with vertices (0, 0) and (x, y).

The input

Two non-negative integers in any sensible format. Due to the symmetry of the puzzle, you can assume the input is ordered if it helps you in any way.

Output

The sum of all the elements in the square delimited by (0, 0) and (x, y).

Test cases

5, 46 -> 6501
0, 12 -> 78
25, 46 -> 30671
6, 11 -> 510
4, 23 -> 1380
17, 39 -> 14808
5, 27 -> 2300
32, 39 -> 29580
14, 49 -> 18571
0, 15 -> 120
11, 17 -> 1956
30, 49 -> 41755
8, 9 -> 501
7, 43 -> 7632
13, 33 -> 8022

Answer 1

Perl 6, 19 bytes

{sum [X+^] 0 X..@_}

Try it online!

The sum of the bitwise xor between all numbers in the range 0 to all inputs.

Answer 2

Python 2, 49 bytes

lambda x,y:sum(k/-~x^k%-~x for k in range(~x*~y))

Try it online!

The usual div-mod trick for iterating over two ranges. Unfortunately, since we want inclusive ranges, we need to raise each input by 1, which we do with -~. Thanks to Bubbler for saving 2 bytes by cancelling the minuses on -~x*-~y.

Python 3 would be a byte longer using //. I tried to use the 3.8 walrus operator to cut down on the -~x repetition, without success.

55 bytes

f=lambda m,n:m|n>0and(m^n)+f(m-1,n)+f(m,n-1)-f(m-1,n-1)

Try it online!

A cute recursion, but unfortunately longer. This doesn't use anything particular about XOR -- this same method can be used to add up any two-variable function over a rectangle. The base case m|n>0 terminates with zero when either m or n becomes negative, or (harmlessly) when both are zero.

This will time out on larger test cases due to the huge degree of recursive branching.

52 bytes

f=lambda m,n,b=1:m|n>0and(m^n)+f(m,n-1)*b+f(m-1,n,0)

Try it online!

A similar shorter recursion. The idea is that we can recursively travel left or down, but once we've gone left, we set to flag b to zero and ignore the results of any further travel down. The result is that we travel to each cell in the rectangle exactly one, like this:

O < O < O < O
            v
O < O < O < O
            v
O < O < O < O

Other ideas

Here are some partial ideas that didn't lead to decent golfs, but maybe someone can make use of them.

The one-dimensional summation (on a half-open range)

w=lambda i,n:sum(i^j for j in range(n))

can be expressed recursively as

w=lambda i,n:i+n and 4*w(i/2,n/2)+n%2*(n^i^1)+n/2

(Python 2 used for floor division.)

We also have an efficient formula

$$f(m-1,n-1) = \sum_{i=0}^{\infty} {\frac{m n - |m \odot 2^{i}||n \odot 2^{i}|}{2} 2^i}$$

where \$ \odot k\$ is the symmetric modulo-\$(2k)\$ operator mapping to the range from \$-k\$ to \$k\$. This summation can be truncated where \$2^i\$ is bigger than the inputs, since further terms will be zero.

Answer 3

Wolfram Language (Mathematica), 28 bytes

Array[BitXor,{##}+1,0,Plus]&

Try it online!

Answer 4

Ruby, 36 bytes

->x,y{(0..y+x*y+=1).sum{|r|r/y^r%y}}

Try it online!

Answer 5

APL (Dyalog Extended), 15 bytes

+/,{⊥≠/⊤⍵}¨⍳1+⎕

Try it online!

Full program.

How it works

+/,{⊥≠/⊤⍵}¨⍳1+⎕
              ⎕  ⍝ Take a pair [x y] from stdin
           ⍳1+   ⍝ Generate indices from [0 0] to [x y] inclusive
   {     }¨      ⍝ For each pair,
       ⊤⍵        ⍝   Convert two numbers into two-column bit matrix
                 ⍝   (each column is binary representation of each number)
     ≠/          ⍝   Reduce each row with not-equals (XOR)
    ⊥            ⍝   Convert the resulting binary representation back to integer
+/,              ⍝ Sum all elements and implicit print

Answer 6

05AB1E, 6 bytes

Ý`δ^˜O

Try it online or verify all test cases.

Explanation:

Ý       # Push a list in the range [0,value] for each value in the (implicit) input-pair
 `      # Push both these lists separated to the stack
  δ     # Apply double-vectorized:
   ^    #  XOR them together
    ˜O  # And then take the flattened sum
        # (after which the result is output implicitly)

Answer 7

J, 23 17 bytes

-6 bytes thanks to Bubbler!

1#.1#.XOR/&(i.,])

Try it online!

K (oK), 25 bytes

{+/2/'~=/'(64#2)\''+!1+x}

Try it online!

Most probably can be golfed further.

Answer 8

Jelly, 7 bytes

^þ/;RSS

Try it online!

A monadic link taking a pair of integers and returning an integer.

A couple of alternative 7-byters:

Ż€^þ/SS ‘Ḷ^þ/SS

Answer 9

Burlesque, 18 bytes

psqrzMPcp{q$$r[}ms

Try it online!

ps   # Parse to arr of ints
qrz  # Boxed range [0,N]
MP   # Map push
cp   # Cartesian product
{
 q$$ # Boxed xor
 r[  # Reduce by
}ms  # Map sum

Answer 10

C (gcc), 48 bytes

R;f(x,y){R=++x*++y;for(y=0;--R;y+=R%x^R/x);x=y;}

Try it online!

Answer 11

Japt -x, 6 bytes

ô ï^Vô

Try it

ô ï^Vô     :Implicit input of integers U & V
ô          :Range [0,U]
  ï        :Cartesian product with
    Vô     :Range [0,V]
   ^       :Reduce each pair by XORing
           :Implicit output of sum of resulting array

Answer 12

Clojure, 72 bytes

(defn s[x y](apply +(for[a(range(inc x))b(range(inc y))](bit-xor a b))))

Ungolfed:

(defn sumxy[x y]
  (apply + (for [a (range (inc x))
                 b (range (inc y)) ]
              (bit-xor a b))))

Tests:

(println (s  5 46) " <-> "  6501)
(println (s  0 12) " <-> "    78)
(println (s 25 46) " <-> " 30671)
(println (s  6 11) " <-> "   510)
(println (s  4 23) " <-> "  1380)
(println (s 17 39) " <-> " 14808)
(println (s  5 27) " <-> "  2300)
(println (s 32 39) " <-> " 29580)
(println (s 14 49) " <-> " 18571)
(println (s  0 15) " <-> "   120)
(println (s 11 17) " <-> "  1956)
(println (s 30 49) " <-> " 41755)
(println (s  8  9) " <-> "   501)
(println (s  7 43) " <-> "  7632)
(println (s 13 33) " <-> "  8022)

Try it online!

Answer 13

JavaScript (ES6), 41 bytes

Takes input as (x)(y) (or the other way around). Computes the sum recursively, the obvious way.

x=>g=(y,Y=y)=>~x&&(x^y)+g(y?y-1:x--&&Y,Y)

Try it online!

Answer 14

Python 3, ⁵⁹ 58 bytes

Saved a byte thanks to Neil and HyperNeutrino!!!

lambda x,y:sum(a^b for a in range(x+1)for b in range(y+1))

Try it online!

Answer 15

C (gcc), ⁶¹ 52 bytes

Saved 9 bytes thanks to Arnauld!!!

b;s;f(x,y){for(s=b=y;~x;b--||(b=y,x--))s+=x^b;s-=y;}

Try it online!

Answer 16

Wolfram Language (Mathematica), 33 bytes

Sum[i~BitXor~j,{i,0,#},{j,0,#2}]&

Try it online!

Answer 17

Japt -x, 8 bytes

ò@Vò^XÃc

Try it

Answer 18

Zsh, 31 bytes

eval '<<<$[' +{0..$1}^{0..$2} ]

Try it online!

Uses eval to expand the <<<$[ ] after expanding the lists. The TIO link adds set -x so you can see what the brace expansion looks like.

Answer 19

Java 8, 58 bytes

(x,y)->{int t=++x*-~y;for(y=0;--t>0;)y+=t%x^t/x;return y;}

Port of @xibu's C answer, so make sure to upvote him!

Try it online.

Explanation:

(x,y)->{        // Method with two integer parameters and integer return-type
  int t=++x     //  Increase `x` by 1 first with `++x`
        *-~y;   //  Create a temp integer `t`, with value `x*(y+1)`
  for(y=0;      //  Reset `y` to 0 to reuse as result-sum
      --t>0;)   //  Loop as long as `t-1` is larger than 0,
                //  decreasing it before every iteration with `--t`
    y+=         //   Increase the result-sum by:
       t%x      //    `t` modulo-`x`
          ^     //    Bitwise XOR-ed with:
           t/x; //    `t` integer-divided by `x`
  return y;}    //  And then return the result-sum `y`

Answer 20

Perl 5 -pa, 36 bytes

map{//;map$\+=$_^$',0..$F[0]}0..<>}{

Try it online!

Takes in inputs on separate lines.

Answer 21

Oracle SQL, 126 bytes

This isn't a golfing language and it doesn't have a bitwise XOR operator but:

SELECT SUM(x+y-2*BITAND(x,y))FROM(SELECT LEVEL-1 x FROM T CONNECT BY LEVEL<x+2),(SELECT LEVEL-1 y FROM T CONNECT BY LEVEL<y+2)

Assumes that there is a table T with columns X and Y containing one row that has the input values.

So for the inputs:

CREATE TABLE t(x,y) AS SELECT 5,46 FROM DUAL;

This outputs:

| SUM(X+Y-2*BITAND(X,Y)) |
| ---------------------: |
|                   6501 |

db<>fiddle here

---

As an aside, its only 81 characters in PostgreSQL:

SELECT sum(a#b)FROM t,generate_series(0,t.x)AS x(a),generate_series(0,t.y)AS y(b)

db<>fiddle here

But its less fun as that has a built-in XOR operator and series generation.

Answer 22

Julia 1.0, 33 bytes

(x,y)->sum(i⊻j for i=0:x,j=0:y)

Try it online!

Answer 23

C (gcc), 51 bytes

d,r;f(x,y){for(d=y;~d||(x--,d=y),~x;)r+=x^d--;d=r;}

Try it online!