|
Main Diagonals and Euler's Totient |
|
|
|
A rectangular box-like (cuboid) object 150 x 324 x 375 is made up of glued 1 x 1 x 1 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 N x M x K rectangular solid must be |
|
|
|
|
|
|
|
so in our example with N=150, M=324, and K=375 we have |
|
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
Interestingly, if S happens to be the first n positive integers then |
|
|
|
|
|
|
|
where ϕ(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. |
|
|
