Let f N rightarrow N be the function that maps each natural

Let f : N rightarrow N be the function that maps each natural number to the sum of its digits. Describe the sets f^-1(n) for n = 1, 2, 3, 4. How do the sets f^-1 (n) relate o congruence modulo 3 and congruence modulo 9?

Solution

f^-1(1) = {1s| s any string consisting of only 0\'s}

f^-1 (2) = {2s| s any string consisting of only 0\'s} U { 1t| t any string of 0\'s and 1\'s consisting of exactly one 1}

f^-1 (3) = {3s| s any string consisting of only 0\'s} U { 2t| t any string of 0\'s and 1\'s consisting of exactly one 1}U {1u| u any string consisting of only 0\'s and either two ones or one 2}

f^-1 (4) = {4s| s any string consisting of only 0\'s} U { 3t| t any string of 0\'s and 1\'s consisting of exactly one 1}U {2u| u any string consisting or 2\'s and 0s with exactly one 2 or 0s and 1s consisting of exactly two 1\'s} U {1v| v any string of 0\'s and 3\'s consisting of exactly one 3 or v any string consisting of exactly one 2 and one 1 and 0s or any string with 0s and 1s with exactly 3 1s}

Not clear what is to be proved.