Neighbour distance in a grid

Problem definition

We know that in an N-dimensional rectilinear grid, each cell has N3-1 neighbours that touch at at least a corner. What is the average distance, in the normal L2 metric, of its neighbours?

Solution

Nneighbours at increasing distancesaverage
1 21.00000000000000000000000
2 4,41.20710678118654752440084
3 6,12,81.41642189265492918976307
4 8,24,32,161.61708439173947943205149
5 10,40,80,80,321.80449083628275725503866
6 12,60,160,240,192,641.97812271726852896962593
7 14,85,280,560,672,448,1282.13926505893029079865077
8 16,112,448,1120,1792,1792,1024,2562.28966414664464746807332
10...numbers...2.56453248999285562411340
100...numbers...8.15982554345577075584239
1000...numbers...25.8182740702771050263350
2000...numbers...36.5136956680059336922984
3000...numbers...44.7204276316904699407121

Pari/GP code to calculate the above

dist(s)=local(pol=(1+2*x)^s);sum(d=1,s,polcoeff(pol,d)*sqrt(d))/(3^s-1)

N.B.: Pari's stack might explode creating pol in the above, but you can do without by generating the coefficients in turn: start with 1, and at each step d in 1..N, multiply by 2*(N+1-d)/d. e.g. in N=3, the coefficient becomes 1*2*3/1=6, then 6*2*2/2=12, then 12*2*1/3=8.


Another hastily constructed page by Phil Carmody
Home / maths / neighbours.html