# 2020 CIME II Problems/Problem 4

## Problem

The probability a randomly chosen positive integer $N<1000$ has more digits when written in base $7$ than when written in base $8$ can be expressed in the form $\tfrac mn$, where $m$ and $n$ are relatively prime positive integers. Find $m+n$.

## Solution

If a positive integer $N$ has more digits in base $7$ than base $8$, then $7^k \le N < 8^k$ for some positive integer $k$. There are $8^k-7^k$ positive integers $N$ that satisfy this condition for every positive integer $k$. If $k \geq 4$, $N$ will be greater than $1000$, so we only need to consider $k \le 3$. The number of possible values of $N$ is $$\sum^{3}_{k=1}[8^k-7^k]=8-7+64-49+512-343=185.$$ The requested probability is $$\frac{185}{999}=\frac{5}{27},$$ and so the answer is $5+27=\boxed{032}$.

## Similar Problems

The intuition behind the above solution:

consider 7^3 = 343 <= N < 8^3 = 512 ; notice that any N in this range will have 4 digits in base 7 ( since 1*7^3 <= N) and since  1*8^3 > N , we have almost 3 digits in base 8 representation of N


its easy to see 3 can be replaced by any positive integer k , where k = 1,2,3