Tip FYI: If the sum of the digits of a number is divisible by 3, then the number is also divisible by 3, and the same rule exists for 9. All numbers have similar laws, it seems. A number divisible by 5 ends with 0 or 5, and so on...
I didn't find a key, but a predominance between the five lists: 9 is the most powerful. 4 or 5 tests are enough, but some have made matrices with more than 25 possible combinations.
A more accurate description of the problem would be binary numbers that start with an even number of zeros but not necessarily those that have or end with an even number of zeros.
Unfortunately, it does not stop lookup tables since 134 factors to 2 and 67, which means it obtains the same result as a lookup table. Kempner(Kempner(Kempner(1535238))) will do 134 -> 67 -> 67 and a lookup table 67->67->67.
Nice solution using the Euler's totient function. I've tried it too, but I couldn't figure out a friendly algorithm like this. I've resorted to my probability knowledge :)