Neighbour distance in a grid

Problem definition

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

Solution

N	neighbours at increasing distances	average
1	2	1.00000000000000000000000
2	4,4	1.20710678118654752440084
3	6,12,8	1.41642189265492918976307
4	8,24,32,16	1.61708439173947943205149
5	10,40,80,80,32	1.80449083628275725503866
6	12,60,160,240,192,64	1.97812271726852896962593
7	14,85,280,560,672,448,128	2.13926505893029079865077
8	16,112,448,1120,1792,1792,1024,256	2.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