3

In particular, once you get into large numbers, does any given number's binary representation ever become a shorter string of digits than the decimal representation of the same number?

it's a hire car baby
  • 9,243
WoosterJeeves
  • 31
  • No, binary representation of $n$ always has a longer length than decimal for $n\geq 2$. In fact, try proving that for a number $n$ and two bases $b$ and $b'$ such that $b\geq b'$, the representation of $n$ in base $b$ always has length $\le$ than the representation in base $b'$. The inequality in length becomes strict for $n\geq b'$ – Prasun Biswas Jan 28 '21 at 01:40
  • In short, no, The higher the base the less digits you need to write a number. 2 is one digit in decimal, but two digits in binary – Vasili Jan 28 '21 at 01:40
  • 1
    Is shortness only one example of efficiency? Maybe you want computation speed as your efficiency. Maybe the capacity to be represented in ram is a form of efficiency. – it's a hire car baby Jan 31 '21 at 21:54

1 Answers1

4

No. Think about the positions as bins which empties into the next bin when it fills, and the base being the size of the first bin. You will always need less bins if each bin can hold more things. This means if $n > m$ then the string representing a number in base $n$ will always be shorter than or equal to the length of the same number in base $m$.

CyclotomicField
  • 11,018
  • 1
  • 12
  • 29
  • What if shortness is only one example of efficiency? – it's a hire car baby Jan 31 '21 at 21:53
  • 1
    @samerivertwice the question was specifically about the length of the representation. I can only answer questions they ask, not other questions. – CyclotomicField Jan 31 '21 at 23:27
  • What I meant is, by my reading of the OP, shortness is only given as one example of "efficiency" and efficiency isn't well-defined, however I've asked for clarification. – it's a hire car baby Feb 01 '21 at 09:30
  • 1
    @samerivertwice the length of the string of digits is perfectly well-defined. The question leaves no ambiguity as to what measure of efficiency they're interested in. Your ponderings are out of scope. – CyclotomicField Feb 01 '21 at 14:38
  • Do you not think they say shorter number of digits is an example? – it's a hire car baby Feb 01 '21 at 16:45
  • 1
    @samerivertwice I meant the number of digits – WoosterJeeves Feb 02 '21 at 17:29
  • @Musskk In that case I've edited your question to say precisely what I think you mean, including restricting it to integers. If this answer answers your question you should accept it. Because 2 factors 10 there are no binary representations which are shorter than the decimal representation of the same number but in general for any two given bases this isn't always the case. For example $0.1_3$ is shorter than $0.333..._{10}$ despite $3<10$. – it's a hire car baby Feb 03 '21 at 09:40