Problem 702

Jumping Flea

A regular hexagon table of side length $N$ is divided into equilateral triangles of side length $1$. The picture below is an illustration of the case $N = 3$.

An flea of negligible size is jumping on this table. The flea starts at the centre of the table. Thereafter, at each step, it chooses one of the six corners of the table, and jumps to the mid-point between its current position and the chosen corner.

For every triangle $T$, we denote by $J(T)$ the minimum number of jumps required for the flea to reach the interior of $T$. Landing on an edge or vertex of $T$ is not sufficient.

For example, $J(T) = 3$ for the triangle marked with a star in the picture: by jumping from the centre half way towards F, then towards C, then towards E.

Let $S(N)$ be the sum of $J(T)$ for all the upper-pointing triangles $T$ in the upper half of the table. For the case $N = 3$, these are the triangles painted black in the above picture.

You are given that $S(3) = 42$, $S(5) = 126$, $S(123) = 167178$, and $S(12345) = 3185041956$.

Find $S(123456789)$.

跳蚤

一个边长为$N$的正六边形被分割成数个边长为$1$的等边三角形，下图展示了$N=3$的情形。

一只可视为质点的跳蚤正在这个正六边形上跳跃，它从正中心出发，每一步它选择正六边形的一个顶点，并跳跃至当前位置和被选中的顶点的中点。

对任意等边三角形$T$，我们记$J(T)$为到达$T$的内部所需要的最少步数。注意$T$的内部不包含其顶点或边缘。

例如，对于途中标有星号的三角形，$J(T)=3$：跳蚤首先由中心跳向F点，再跳向C点，最后跳向E点。

记$S(N)$为正六边形上半部分所有尖端向上的三角形$T$所对应的$J(T)$之和。对于$N=3$的情形，只需考虑上图中被染黑的三角形。

已知$S(3) = 42$，$S(5) = 126$，$S(123) = 167178$，$S(12345) = 3185041956$。

求$S(123456789)$。