# Neighbour distance in a grid

## Problem definition

We know that in an N-dimensional rectilinear grid, each cell has N^{3}-1 neighbours that touch at at least a corner. What is the average distance, in the normal L_{2} 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