# 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.

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

• vaguely related
– RGS
Feb 26 '20 at 22:16
• Interesting, I'm curious if there's a bitwise way to express this without summing everything.
– xnor
Feb 26 '20 at 22:20
• We'll see what you guys come up with :)
– RGS
Feb 26 '20 at 22:21
• The main diagonal is A224923. Feb 26 '20 at 22:56

# 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.

# 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.

• Feb 27 '20 at 2:51
• Also, an attempt to remove some -~s turned out to be 53 bytes. Feb 27 '20 at 2:53
• Good work here! +1
– RGS
Feb 27 '20 at 19:18

# Wolfram Language (Mathematica), 28 bytes

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


Try it online!

• Nice use of the fourth argument! Feb 27 '20 at 10:52
• Wow, this is incredibly short for a Mathematica submission! +1
– RGS
Feb 27 '20 at 19:20
• You can save three bytes by taking a list as input Feb 28 '20 at 14:47

# Ruby, 36 bytes

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


Try it online!

• What is the |r| doing?
– RGS
Feb 27 '20 at 19:25
• @RGS It defines the name of the variable which is used inside the block, iterating over every value between 0 and y+x*y+=1. Kind of like for( r = 0; r <= y+x*(y+1); r = r + 1 ){ Feb 28 '20 at 11:26

# 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

• Nice APL submission +1
– RGS
Feb 27 '20 at 19:19

# 05AB1E, 6 bytes

Ýδ^˜O


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)

• Thanks for your submission! Was it after or before the morning meetings? ;)
– RGS
Feb 27 '20 at 19:19
• @RGS Uhh, dunno anymore haha. I think slightly before based on that '13 hours ago'. ;) Feb 27 '20 at 21:13
• Alright! I see you like golfing :D
– RGS
Feb 27 '20 at 21:55
• @RGS What makes you think that, haha. Is it my multiple answers a day? My 65k+ rep? My 7+ gold badges? Me joining 3.5 years ago, but still active today? xD But yes, I indeed like golfing while I'm waiting for things to compile/build at work. Feb 28 '20 at 7:30
• Oh man, I wish I was coding in a compiled language :P I am gonna propose that back at work, so that I can enjoy some code golf while everything builds...
– RGS
Feb 28 '20 at 8:20

# 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.

• J, 17 bytes using outer product instead of catalogue. Feb 27 '20 at 9:27
• @Bubbler Of course! That's much, much better! Feb 27 '20 at 9:29
• Thanks for your two solutions +1 Why don't you have two different answers?
– RGS
Feb 27 '20 at 19:23
• @RGS Well, I'm not sure... They turned out to be quite different. Feb 28 '20 at 7:29

# 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:

• So short! Thanks for the alternatives +1
– RGS
Feb 26 '20 at 23:48

# 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

• Nice solution +1 Do the several letters together represent a single function name?
– RGS
Feb 27 '20 at 19:23
• @RGS there's no such things as a function, it's all stack. The q is shorthand for putting it in a block. e.g. qrz = {rz}. Operations are elements of the stack too, and most operations are 2 chars. Some, like maps and reduce, take blocks of operations as an argument and apply them. Feb 27 '20 at 19:33
• I understand, thanks for the explanation!
– RGS
Feb 27 '20 at 19:37

# 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!

• Thanks for your C submission +1
– RGS
Feb 27 '20 at 19:20
• Nice! How does this work? Mar 1 '20 at 2:49
• @S.S.Anne xnor has used the same algorithm for his python solution and written a good explanation.
– xibu
Mar 2 '20 at 16:22

# 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

• Straightforward! Thanks +1
– RGS
Feb 27 '20 at 19:25

# 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!

• So many parenthesis :p +1
– RGS
Feb 27 '20 at 19:26
• Lisp (of which Clojure is a variant) was one of the earliest high-level languages. It probably would have been more widely adopted were it not for the high costs incurred by the untimely post-war depletion of the Strategic Parenthesis Reserve. However, despite such setbacks, Lisp and its derivatives have been influential in key algorithmic techniques such as recursion and condescension. See the "...History of Programming Languages" page. :-) Feb 27 '20 at 22:52
• I don't think I even understand all the jokes and references, but that blog post is making me laugh so much :D thanks for this!
– RGS
Feb 27 '20 at 22:56

# 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

• I like the two eyes ô at the ends of the code +1
– RGS
Feb 27 '20 at 19:21

# 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!

• Good answer! I thought you were going to find some weird formula with the bits of x and y! Nothing came to mind?
– RGS
Feb 26 '20 at 23:47
• @RGS The carries implied by a sum usually doesn't mix well with bitwise operations. So I doubt a magic formula exists. (But I'd love to see one.) Feb 26 '20 at 23:56
• If time efficiency were the goal, there are some simple formulas that come quite close (and can then be corrected by brute-forcing a much shorter list). Feb 27 '20 at 21:24

# Python 3, 59 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!

• You have an extra space that you can remove after the ) in range(x+1) Feb 26 '20 at 22:43

# C (gcc), 61 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!

• Do you really have to have the three variables before the f? Can't you stuff them somewhere else or something? :/
– RGS
Feb 26 '20 at 23:50
• @RGS Tried several variations and they had either more or the same byte count. :( Feb 26 '20 at 23:51
• 52 bytes Feb 26 '20 at 23:51
• @Arnauld That's diabolical - thanks! :-) Feb 26 '20 at 23:57

# Wolfram Language (Mathematica), 33 bytes

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


Try it online!

# 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.

• Thanks for your zsh submission!
– RGS
Feb 27 '20 at 19:24

# Perl 5-pa, 36 bytes

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


Try it online!

Takes in inputs on separate lines.

• Thanks for your Perl 5 submission! Why did you go for Perl 5 and not any other version? Like a more recent version?
– RGS
Feb 27 '20 at 21:29
• @RGS Perl 5 is very different from Perl 6, so much so that the latter has been renamed to Raku to prevent confusion. Perl 5 is what most people refer to as just Perl
– Jo King
Feb 28 '20 at 2:09

# 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.

• Really cool solution! thanks for it +1
– RGS
Feb 27 '20 at 21:29

# Japt-x, 8 bytes

ò@Vò^XÃc


Try it

• 8 bytes: ò@Vò^XÃc. Feb 27 '20 at 7:30
• I also like the eyes and nose here: ò@ò
– RGS
Feb 27 '20 at 19:25

# Julia 1.0, 33 bytes

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


Try it online!

• This Julia answer is really short +1 good job
– RGS
Mar 1 '20 at 9:26

# 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!

• Nice answer! +1 keep up the good work
– RGS
Mar 1 '20 at 9:26
• 50 bytes Jul 4 '20 at 6:57