The CSAT and Practice[+] are designed by the Climb Foundation to help candidates. We are advocates for more opportunity to shine and less opportunity to fail, and we strive to level the playing field.

The Computer Laboratory

Practice Paper 4 Question 15

In base 10, or decimal, we use the digits from 0 to 9 to represent any positive integer. In base 2, or binary, we use the digits from 0 to 1 to do the same. An integer is called a repunit (repeated unit) if it can be written in some base using only the digit 1. Find all \(n,p>0\) such that a binary repunit with \(n\) digits is equal (in value) to a decimal repunit with \(p\) digits. Prove your answer.

The above links are provided as is. They are not affiliated with the Climb Foundation unless otherwise specified.

Warm-up Questions

  1. What is the value of \(2222_3\) in base \(10?\)
  2. Let \(a\) be a number in base \(b\) with digits \(a_na_{n-1}\ldots a_0.\) Show that \(a \equiv a_0 \mod b.\)

Hints

  • Hint 1
    Which values of \(n\) and \(p\) work and which don't?
  • Hint 2
    Are there any constraints relating \(n\) and \(p?\)
  • Hint 3
    More specifically, pay attention to the number of digits used to express a number in base \(2\) compared to in base \(10.\)
  • Hint 4
    You should have found that \(n=p=1\) is a solution. If there are other solutions, could you try to establish a lower bound on \(p?\)
  • Hint 5
    Are any other solutions? Could you prove your hypothesis?
  • Hint 6
    How can you mathematically express that "a binary repunit with \(n\) digits is equal in value to a decimal repunit with \(p\) digits"?
  • Hint 7
    ... as an equality of two geometric series?
  • Hint 8
    Have you tried simplifying and rearranging the expression into a form which you can apply your constraints to get a contradiction?

Solution

We can easily see that \(n=p=1\) works. What about other values? We can also see that \(n>p,\) since any number greater than \(1\) needs more binary digits than base \(10\) digits to be represented.

By inspection it's also clear that \(p=2,3\) would not work since those are the decimal repunits \(11\) and \(111,\) neither of which are equal to any binary repunits. The closest are \(111_2=8\) and \(1111111_2=127.\) Therefore \(p>3.\)

The original condition can be written as \(\sum_{i=0}^{n-1}2^i=\sum_{i=0}^{p-1}10^i,\) which gives \(2^n-1=\) \({(10^p-1) \over 9}.\) We can rearrange this to get \(9\cdot2^{n-p}-5^p=2^{3-p}.\)

Together with the above conditions, \(n>p\) and \(p>3,\) we get a contradiction, since \(2^{3-p}\) is a rational less than 1 and \(9\cdot2^{n-p}-5^p\) is an integer. Therefore \(n=p=1\) is the only solution.

If you have queries or suggestions about the content on this page or the CSAT Practice Platform then you can write to us at oi.foo[email protected]. Please do not write to this address regarding general admissions or course queries.