재귀 정의 함수

[출제의도] 조건을 만족시키는 자연수의 개수를 추론한다. $f ( 1 ) = 1$, $f ( 2 ) = 1$, $f ( 3 ) = 2$, $f ( 4 ) = 1$, $f ( 5 ) = 2$, $f ( 6 ) = 2$, $f ( 7 ) = 3$, $f ( 8 ) = 1$, $f ( 9 ) = 2$, $f ( 10 ) = 2$, $f ( 11 ) = 3$, $f ( 12 ) = 2$, $f ( 13 ) = 3$, $f ( 14 ) = 3$, $f ( 15 ) = 4$, $f ( 16 ) = 1$, $f ( 17 ) = 2$, $\cdots$ 따라서 $f ( n ) = 2$를 만족시키는 $n$을 나열하면 $3 = 2 + 1$, $5 = 2 ^{2} + 1$, $6 = 2 ^{2} + 2$, $9 = 2 ^{3} + 1$, $10 = 2 ^{3} + 2$, $12 = 2 ^{3} + 2 ^{2}$, $17 = 2 ^{4} + 1$, $\cdots$ ∴ $n = 2 ^{m} + 1$ 또는 $n = 2 ^{m} + 2 ^{k}$ (단, $m$과 $k$는 자연수이고, $k < m$) $( i )$ $n = 2 ^{m} + 1$일 때 $n = 2 ^{m} + 1 \leq 100$에서 $1 \leq m \leq 6$ $( ii )$ $n = 2 ^{m} + 2 ^{k}$일 때 $n = 2 ^{m} + 2 ^{k} \leq 100$에서 $1 \leq k < m \leq 6$ …… ㉠ ㉠을 만족시키는 두 자연수 $k$, $m$의 순서쌍 $( k , m )$의 개수는 $1$부터 $6$까지 서로 다른 $6$개의 자연수에서 $2$개의 수를 택하는 조합의 수 ${} _{6} \mathrm{C} \mathit{_{2}}$$= 15$와 같다. $( i )$, $( ii )$에서 $f ( n ) = 2$를 만족시키는 $n$의 개수는 $6 + 15 = 21$ [참고] $f ( n )$의 값은 $n$을 이진법의 수로 나타내었을 때 1의 개수이다.