18

How many bits needed to store a number $55^{2002}$ ?

My answer is $2002\;\log_2(55)$; is it correct?

J. W. Tanner
  • 58,836
  • 3
  • 38
  • 78
TOP KEK
  • 295
  • 1
  • 2
  • 5
  • 2
    That would be bits. Also you need a ceiling function in the end. – Jyrki Lahtonen Jun 19 '12 at 11:57
  • yeah, I meant bits, sorry – TOP KEK Jun 19 '12 at 11:58
  • `00110101 00110101 01011110 00110010 00110000 00110000 00110010` are only 56 bits :) – Hagen von Eitzen Jan 27 '14 at 16:48
  • @HagenvonEitzen: It says number, not string. And fact you can store ASCII at 7 bits per character.;-) – Marc van Leeuwen Jan 27 '14 at 17:52
  • @MarcvanLeeuwen In order to be able to express more, I used UTF-8 ;) - But the answer to the original question should nevertheless depend on the *encoding* to be precise. For example IEEE floats are very well suited to store numbers that are powers of two, or (relatively) small numbers times a power of two. So who stops us from introducing an encoding that is good (and exact) for powers of $55$? – Hagen von Eitzen Jan 28 '14 at 19:31

1 Answers1

26

The number of bits required to represent an integer $n$ is $\lfloor\log_2 n\rfloor+1$, so $55^{2002}$ will require $\lfloor 2002\; \log_2 55\rfloor+1$ bits, which is $11,575$ bits.

Added: For example, the $4$-bit integers are $8$ through $15$, whose logs base $2$ are all in the interval $[3,4)$. We have $\lfloor\log_2 n\rfloor=k$ if and only if $k\le\log_2 n<k+1$ if and only if $2^k\le n<2^{k+1}$, and that’s exactly the range of integers requiring $k+1$ bits.

Brian M. Scott
  • 603,754
  • 56
  • 745
  • 1,230