Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

share|improve this question
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 –  Ask Jun 19 '12 at 11:58
    
00110101 00110101 01011110 00110010 00110000 00110000 00110010 are only 56 bits :) –  Hagen von Eitzen Jan 27 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 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 at 19:31
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.