At 09:09 AM 1999/06/29 -0400, Jud McCranie <[EMAIL PROTECTED]>
wrote:
>At 04:16 AM 6/29/99 -0400, Lucas Wiman wrote:
>>All,
>>Here is version 1.1 of the FAQ.
>
>Here's a question that needs to be addressed: how to go from digits to
>exponents, and exponent to digits.
By all means include it in the faq; there's been too much repetition,
including wrong responses, now and in past months. Here's a draft:
Sometimes it is useful to know the relationship between the exponent
of a mersenne number and the number of digits it has in some number base.
How do we calculate in either direction?
(q) How many digits are there in the binary representation of 2^n-1 (or any
number 2^(n-1) <= x <= 2^n - 1) ?
(a) n
Examples:
n=1, 2^(1-1)=2^0=1= 1(2); 2^1-1= 1 = 1(2).
n=2, 2^(2-1)=2^1=2= 10(2); 2^2-1= 3 = 11(2).
n=3, 2^(3-1)=2^2=4= 100(2); 2^3-1= 7 = 111(2).
n=4, 2^(4-1)=2^3=8=1000(2); 2^4-1= 15 = 1111(2).
Hey, a pattern's emerging here.
(q) How many digits are there in the hexadecimal representation of 2^n-1?
(a1) int((n+3)/4)
(a2) take the number of binary digits, divide by 4, then round up.
(q) How many digits are there in the decimal representation of 2^n-1 ?
(a) D = int(n * log_10_(2) + 1);
log_10_(2) ~= 0.301029995664 = log (base 10) of 2
Examples:
n=1, int(1* .3010... + 1) = 1;
n=2, int(2* .3010... + 1) = 1;
n=3, int(3* .3010... + 1) = 1;
n=4, int(4* .3010... + 1) = 2;
...
n=10, 2^n-1=1023; int(10*.3010...+1) ~= int(4.01029995664) = 4;
n= 3321925, int(3321925* .3010...+1) ~= int(1000000.068346) = 10^6
n= 33219281, int(33219278* .3010...+1)~= int(10000000.1123) = 10^7
n= 332192807,int(332192807*.3010...+1)~=int( 100000000.2508)= 10^8
n= 3321928095,int(3321928092*.3010..+1)~=int(1000000000.131)= 10^9
(q) What about in some arbitrary number base?
(a) For base a as in arbitrary, 2^n -1 will have r digits where
r=int(n*log_a_(2) + 1-epsilon), or rather r=ceil(n*log_a_(2))
(allowing for the base a to possibly be a prime number),
Example: a=7, n=3, log_2_(7)~= 2.807354922058; log_7_(2)~= 0.356207187108
2^3-1= 7 = 10(base 7)
Derivation:
2^n-1 <= a^r-1 or it won't fit in r digits in base a
2^n <= a^r
n * log_a_(2) <= r
(q) What is the minimum exponent n for 2^n - 1 to have at least D decimal
digits?
(a) 2^n-1 > 10^(D-1) -1
2^n > 10^(D-1)
n > log_2_( 10^(D-1) )
n > log_2_(10) * (D-1); log_2_(10) ~= 3.321928094887
Examples:
D=1, n> log_2_(1); n> 0
D=2, n> log_2_(10); n> 3.321...; 2^4-1=15; 2^3-1-7
D=3, n> log_2_(100); n> 6.642...; 2^7-1=127; 2^6-1=63
D=10, n> log_2_(10)*9; n> 29.897... 2^30=1,073,741,824
D=100, n> log_2_(10)*99; n>328.87.. 2^329= 1.093625362392e+99
D=1000, n>3318.6
D=10000, n>33215.95
D=100,000, n>332189.48
D=1,000,000, n> 3321924.772959
D=10,000,000, n> 33219277.62694
D=100,000,000, n> 332192806.1668
D=1,000,000,000, n> 3321928091.565
Ken
________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
