## Main Daigonals and Euler's Totient

```A rectangular box-like (cuboid) object 150 x 324 x 375 is made up
of glued 1x1x1 cubes.  The diagonal passes through the interior
of how many of these cubes?

The diagonal enters a new little cube each time it passes through a
"wall", and (starting from the negative region) we know it passes
through 150 walls in the x direction, 324 in the y direction, and
375 in the z direction, for a total of 849.  However, some of these
transitions from one cell to another occur when the diagonal line
passes through more than one wall at once.  For example, the diagonal
enters the very first cell at one of its vertices (the 0,0,0 point),
so it's passing through 3 walls but entering only one new region.
At other points it enters a cell through an "edge", so it's passing
through 2 walls at once as it enters a new cell.

Taking this into account, the total number of cells entered by the
diagonal of an NxMxK rectangular solid must be

T = N + M + K - gcd(N,M) - gcd(N,K) - gcd(M,K) + gcd(N,M,K)

so in our example with N=150, M=324, and K=375 we have

T    =   150 + 324 + 375 - 6 - 3 - 75 + 3    =    768

This is sort of an interesting number-theoretic function.  Given
any set S of n positive integers, let G(S,k) for k < = n denote
the sum of the greatest common divisors of every set of k elements
of S.  Then we can define the inclusion-exclusion function

f(S)  =  G(S,1) - G(S,2) + G(S,3) - ...  - (-1)^n G(S,n)

Interestingly, if S happens to be the first n positive integers
then
n
f({1,2,3,..,n}) =  SUM  phi(k)
k=1

where phi(n) is the Euler totient function of n.  Other sets of
integers (such as the first n odd numbers, or the squares, etc)
give other interesting number-theoretic sums.
```