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.

Return to MathPages Main Menu