Now we're thinking in n dimensions!

Question

The question: Given an a number n ≥ 2, how many distinct pairs of points on an n-dimensional n x n x n x n x n x n ... x n lattice, where the coordinates range from 0 to n - 1, are a distance at least n apart? The pairs {(2,1,3,1), (3,2,1,3)} and {(3,2,1,3), (2,1,3,1)} are not considered distinct from each other, as they consist of the same two points in reverse order. Note that the total number of pairs grows very rapidly. The number of total pairs goes 6, 351, 32 640, 4 881 250, 1 088 367 840, etc.

Test cases:

2 -> 0 (all pairs are at most a distance of sqrt(2) < 2 apart)
3 -> 28 (They must either be (2,2,1) or a permutation apart, or (2,2,2) apart. Each corner
has three non-corner (2,2,1) points corresponding to it. And each corner is associated 
with a corner pair that is a (2,2,2). Thus. 3.5 * 8 = 28.
4 -> 4,888
5 -> 1,501,948
6 -> 486,039,360 (I would like someone to verify this if possible)

Your code should work for n <= 5, at least in theory. Don't hardcode it, that's a standard loophole.

Answer 1

MATL, 12 bytes

tt:Z^tZPR>~z

Try it online!

Explanation

tt   % Implicit input n. Duplicate twice
     % STACK: n, n, n
:    % Range [1 2 ... n]
     % STACK: n, n, [1 2 ... n]
Z^   % Cartesian power. Gives an n^n × n matrix C where each row is a Cartesian tuple
     % STACK: n, C
t    % Duplicate
     % STACK: n, C, C
ZP   % Euclidean distance. Gives an n^n × n^n matrix D of pairwise distances
     % STACK: n, D
R    % Upper triangular part: sets elements below the main diagonal to 0. Call that U
     % STACK: n, U
>~   % Less than or equal? Element-wise. Gives a true-false matrix B
     % STACK: n, B
z    % Number of nonzeros. Implicitly display
     % STACK: number of entries in B that equal true

Answer 2

Jelly, 14 13 bytes

1 byte thanks to Dennis.

ṗ⁸Œc_/€ÆḊ€<ċ0

Try it online!

Quick maffs version

ŒgL€!P:@L!$×P
²S<
ḶœċçÐḟ²ð>0S’2*×⁸ạ⁹$Ѥð€S

Try it online!

Answer 3

Python 2, 137 133 bytes

lambda n:sum(n*n<=sum((o[i]-p[i])**2for i in range(n))for o,p in q(q(range(n),repeat=n),repeat=2))/2
from itertools import*
q=product

Mr Xcoder & ovs: -4 bytes. Try it online!

Answer 4

J, 40 bytes

2%~[:+/^:_]<:[:+/&.:*:"1[:-"1/~#~#:i.@^~

Try it online!

Will time out on TIO for 5 if you use extended precision (5x instead of 5). I'm not going to bother trying with 6 on my computer since that will no doubt crash the interpreter.

Looking for advice on golfing, specifically the part past the generation of the coordinates. I feel like there ought to be a way to remove some of the caps.

]<:[:+/&.:*:"1 may be equivalently replaced by *:<:[:+/"1[:*:.

Explanation

This explanation is done on the REPL (three spaces indicate a command, no spaces indicate an output). I will be building up to the answer.

Generating the coordinates

#~ #: i.@^~ gives all the coordinates we care about on the lattice.

^~ is a number raised to itself, and i. gives the range [0,n) where n is its input. @ composes those functions.

   i.@^~ 2
0 1 2 3

#~ copies a number by itself, e.g.

   #~ 3
3 3 3

#: converts its right argument to the base specified by the array given as its left argument. The number of digits in the array corresponds to the number of digits in that base output (and you can have a mixed base) For example,

   3 3 3 #: 0
0 0 0
   5 5 #: 120
4 0
NB. If you want 120 base 5 use #.inv
   #.inv 120
4 4 0

So, all together, this says enumerate through all of the values base n (where n is the input) up to n^n, effectively giving us our coordinates.

   (#~ #: i.@^~) 2
0 0
0 1
1 0
1 1

Getting the distances between each pair

First we take the difference of each coordinate with all of the others using the dyad /-table and ~-reflexive. Note that this doesn't account for the fact that order doesn't matter for the pairs: this generates duplicate distances.

  NB. 2 {. takes the first two elements (I'm omitting the rest).
  2 {. -"1/~ (#~ #: i.@^~) 2
 0  0
 0 _1
_1  0
_1 _1

 0  1
 0  0
_1  1
_1  0

Then we use this verb +/&.:*: on each coordinate (at "1, aka rank one). This verb is sum (+/) under (&.:) square (*:). Under applies the right verb (square) then collects its results and gives it as the argument to the left verb (sum). It then applies the inverse of the right verb (which would be square root).

   +/&.:*: 3 4
5
   +/&.:*:"1 ([: -"1/~ #~ #: i.@^~) 2
      0       1       1 1.41421
      1       0 1.41421       1
      1 1.41421       0       1
1.41421       1       1       0

Unsurprisingly, many distances are the same.

Counting the distances greater than or equal to the input

The last part is seeing if the distance is greater than or equal to the input using ]<:. Then all of the results are summed using +/^:_ (sum until converge), counting the number of truthy values. Then this value is divided by 2 (2%~, here ~ means swap the order of the arguments supplied to %). The reason why we can divide by 2 is because for each truthy pairing, there will be another one for the flipped order except for pairings which are a coordinate with itself. That's ok, though, since those will result in a distance of 0.