# Now we're thinking in n dimensions!

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.

• tio.run/##bZLbboMwDIav4Sm8SpWSAONQbRfVuhepqgmRsEaioQpU256e2UkZh/… Dec 21, 2017 at 2:04
• ^ a program that can produce results for n=15 easily Dec 21, 2017 at 2:05
• tinyurl.com/ya2kmb24 <-- ported to C which can calculate up to n=20 but suffers heavily from overflow Dec 21, 2017 at 3:51
• How are you measuring distance? Euclidean metric? Or given that it's a lattice are you using L_1? Dec 21, 2017 at 9:28
• @PeterTaylor from the test cases, it's clear that we're using Euclidean distance all pairs are at most a distance of sqrt(2) apart but that should be specified more clearly. Dec 21, 2017 at 14:10

# 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


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

• What interpreter do you use to run this? I want to try it but TIO is too slow for n=5 (timed out after 1 minute) prntscr.com/hqbcph Dec 21, 2017 at 1:02
• @bushdid911 if you try to break the limit, broken the limit will be Dec 21, 2017 at 1:02
• You can replace æ.½ with ÆḊ€. Dec 21, 2017 at 1:04
• @bushdid911 It can run n=5, just not in one minute. (it may take more than the age of the universe, be careful) This is not fastest code, so why bother make your code run fast? Dec 21, 2017 at 1:04
• @bushdid911 I made a fast(er) version. Dec 21, 2017 at 1:36

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

• 135 bytes. (No need to include f=) Dec 21, 2017 at 7:13
• 133 bytes
– ovs
Dec 21, 2017 at 9:59

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

• 35 bytes with +/@,@(-:@<:+/&.:*:@:-"1/~)#~#:i.@^~` Dec 23, 2017 at 8:58