Mock AIME 6 2006-2007 Problems/Problem 14

Problem

A rational $\frac{1}{k}$ , where $k$ is a positive integer, is said to be $\textit{n-unsound}$ if its base $N$ representation terminates. Let $S_n$ be the set of all $\textit{n-unsound}$ rationals. The sum of all the elements in the union set $S_2\cup S_3\cup\cdots\cup S_{14}$ is $\frac mn$ , where $m$ and $n$ are relatively prime positive integers. Find $m+n$ .

Solution

Denote the set of distinct primes dividing into $k$ as $X$ . The rational $\frac{1}{k}$ is only terminating in base $N$ if for all members $x\in X$ , we have $x|N$ . As a result, $2$ , $4$ , and $8$ are identical in this respect, for instance, and we can thus reduce the $n$ to: $2,3,5,7,11,13,2\cdot3,2\cdot5,2\cdot7$ Clearly for each of the primes $p$ in the list above, the sum of all terminating rationals of such a form is $\sum_{i=0}^\infty\frac{1}{p^i}=\frac{p}{p-1}$ Thus the primes $2,3,5,7,11,13$ respectively contribute $2,\frac{3}{2},\frac{5}{4},\frac{7}{6},\frac{11}{10},\frac{13}{12}$ to the total sum. However, each of them overcounts the case $k=1$ , so we must subtract $5$ at the end to account for this.

Next, we consider the three $n$ with multiple distinct prime factors. If we ignore all values already counted above, then the sum of each, for $p=3,5,7$ , is, $\sum_{i=1}^\infty\frac{1}{2^i}\cdot\sum_{i=1}^\infty\frac{1}{p^i}=\frac{1}{p-1}$ Thus the overall sum is $2+\frac{3}{2}+\frac{5}{4}+\frac{7}{6}+\frac{11}{10}+\frac{13}{12}-5+\frac{1}{2}+\frac{1}{4}+\frac{1}{6}=\frac{241}{60}$ The solution is therefore $241+60=\boxed{301}$ .

~ eevee9406

Page

Toolbox

Search

Mock AIME 6 2006-2007 Problems/Problem 14

Problem

Solution