How many digits in base 2 do I need to represent any odd integer from 1 to $sqrt{N}$?
up vote
2
down vote
favorite
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$An example here seems best. How many digits in base 2 do I need to represent any odd integer from $1$ to $sqrt{77}$, inclusive? It seems to be essentially half the digits required for $77$ --- in base 2. We can represent $77$ with $7$ digits in base 2. Half of that is $3.5$, so we need $4$ digits in base 2. So let's change "essentially half" to "exactly $floor{n/2} + 1$, where $n$ is the number of digits in base 2 held by $N$.
Since I'm interested in the odd integers (from $1$ to $sqrt{77}$), this means that the last digit must be $1$. But if $4$ is the number of bits, then I get the wrong list in base 2: $$0001_2 = 1_{10}, 0011_2 = 3_{10}, 0101_2 = 5_{10}, 0111_2 = 7_{10}, 1001_2 = 9_{10}, ...$$
That's wrong because $9 > sqrt{77}$. So the number must be less than $4$ digits in base 2. When I try $3$, I get the correct list
$$001_2 = 1_{10}, 011_2 = 3_{10}, 101_2 = 5_{10}, 111_2 = 7_{10},$$
but I haven't found an argument to convince myself I'm right. (Will this always work? Why?)
elementary-number-theory
asked Dec 3 at 12:54
Luitpold Ambre
133
add a comment |
up vote
2
down vote
favorite
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$An example here seems best. How many digits in base 2 do I need to represent any odd integer from $1$ to $sqrt{77}$, inclusive? It seems to be essentially half the digits required for $77$ --- in base 2. We can represent $77$ with $7$ digits in base 2. Half of that is $3.5$, so we need $4$ digits in base 2. So let's change "essentially half" to "exactly $floor{n/2} + 1$, where $n$ is the number of digits in base 2 held by $N$.
Since I'm interested in the odd integers (from $1$ to $sqrt{77}$), this means that the last digit must be $1$. But if $4$ is the number of bits, then I get the wrong list in base 2: $$0001_2 = 1_{10}, 0011_2 = 3_{10}, 0101_2 = 5_{10}, 0111_2 = 7_{10}, 1001_2 = 9_{10}, ...$$
That's wrong because $9 > sqrt{77}$. So the number must be less than $4$ digits in base 2. When I try $3$, I get the correct list
$$001_2 = 1_{10}, 011_2 = 3_{10}, 101_2 = 5_{10}, 111_2 = 7_{10},$$
but I haven't found an argument to convince myself I'm right. (Will this always work? Why?)
elementary-number-theory
asked Dec 3 at 12:54
Luitpold Ambre
133
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$An example here seems best. How many digits in base 2 do I need to represent any odd integer from $1$ to $sqrt{77}$, inclusive? It seems to be essentially half the digits required for $77$ --- in base 2. We can represent $77$ with $7$ digits in base 2. Half of that is $3.5$, so we need $4$ digits in base 2. So let's change "essentially half" to "exactly $floor{n/2} + 1$, where $n$ is the number of digits in base 2 held by $N$.
Since I'm interested in the odd integers (from $1$ to $sqrt{77}$), this means that the last digit must be $1$. But if $4$ is the number of bits, then I get the wrong list in base 2: $$0001_2 = 1_{10}, 0011_2 = 3_{10}, 0101_2 = 5_{10}, 0111_2 = 7_{10}, 1001_2 = 9_{10}, ...$$
That's wrong because $9 > sqrt{77}$. So the number must be less than $4$ digits in base 2. When I try $3$, I get the correct list
$$001_2 = 1_{10}, 011_2 = 3_{10}, 101_2 = 5_{10}, 111_2 = 7_{10},$$
but I haven't found an argument to convince myself I'm right. (Will this always work? Why?)
elementary-number-theory
asked Dec 3 at 12:54
Luitpold Ambre
133
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$An example here seems best. How many digits in base 2 do I need to represent any odd integer from $1$ to $sqrt{77}$, inclusive? It seems to be essentially half the digits required for $77$ --- in base 2. We can represent $77$ with $7$ digits in base 2. Half of that is $3.5$, so we need $4$ digits in base 2. So let's change "essentially half" to "exactly $floor{n/2} + 1$, where $n$ is the number of digits in base 2 held by $N$.
Since I'm interested in the odd integers (from $1$ to $sqrt{77}$), this means that the last digit must be $1$. But if $4$ is the number of bits, then I get the wrong list in base 2: $$0001_2 = 1_{10}, 0011_2 = 3_{10}, 0101_2 = 5_{10}, 0111_2 = 7_{10}, 1001_2 = 9_{10}, ...$$
That's wrong because $9 > sqrt{77}$. So the number must be less than $4$ digits in base 2. When I try $3$, I get the correct list
$$001_2 = 1_{10}, 011_2 = 3_{10}, 101_2 = 5_{10}, 111_2 = 7_{10},$$
but I haven't found an argument to convince myself I'm right. (Will this always work? Why?)
elementary-number-theory
elementary-number-theory
asked Dec 3 at 12:54
Luitpold Ambre
133
asked Dec 3 at 12:54
Luitpold Ambre
133
asked Dec 3 at 12:54
Luitpold Ambre
133
asked Dec 3 at 12:54
Luitpold Ambre
133
asked Dec 3 at 12:54
Luitpold Ambre
133
133
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
The number of digits of a number $N$ in base $b$ is $log_b N+1$. So the number of digits of $sqrt{N}$ in base $2$ is
$$log_2 sqrt{N}+1 = frac{1}{2}log_2 N +1.$$
The $frac{1}{2}$ shows why it takes half as many digits for $sqrt{N}$ as $N$.
answered Dec 3 at 13:16
B. Goddard
18.2k21340
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$I think you mean $floor{log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $frac{1}{2}floor{log_b sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens.
– Luitpold Ambre
Dec 3 at 13:34
You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $lceil log_2 N rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $lceil log_2 lfloor sqrt{N} rfloor rceil.$
– B. Goddard
Dec 3 at 16:52
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
The number of digits of a number $N$ in base $b$ is $log_b N+1$. So the number of digits of $sqrt{N}$ in base $2$ is
$$log_2 sqrt{N}+1 = frac{1}{2}log_2 N +1.$$
The $frac{1}{2}$ shows why it takes half as many digits for $sqrt{N}$ as $N$.
answered Dec 3 at 13:16
B. Goddard
18.2k21340
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$I think you mean $floor{log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $frac{1}{2}floor{log_b sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens.
– Luitpold Ambre
Dec 3 at 13:34
You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $lceil log_2 N rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $lceil log_2 lfloor sqrt{N} rfloor rceil.$
– B. Goddard
Dec 3 at 16:52
add a comment |
up vote
1
down vote
The number of digits of a number $N$ in base $b$ is $log_b N+1$. So the number of digits of $sqrt{N}$ in base $2$ is
$$log_2 sqrt{N}+1 = frac{1}{2}log_2 N +1.$$
The $frac{1}{2}$ shows why it takes half as many digits for $sqrt{N}$ as $N$.
answered Dec 3 at 13:16
B. Goddard
18.2k21340
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$I think you mean $floor{log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $frac{1}{2}floor{log_b sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens.
– Luitpold Ambre
Dec 3 at 13:34
You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $lceil log_2 N rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $lceil log_2 lfloor sqrt{N} rfloor rceil.$
– B. Goddard
Dec 3 at 16:52
add a comment |
up vote
1
down vote
up vote
1
down vote
The number of digits of a number $N$ in base $b$ is $log_b N+1$. So the number of digits of $sqrt{N}$ in base $2$ is
$$log_2 sqrt{N}+1 = frac{1}{2}log_2 N +1.$$
The $frac{1}{2}$ shows why it takes half as many digits for $sqrt{N}$ as $N$.
answered Dec 3 at 13:16
B. Goddard
18.2k21340
The number of digits of a number $N$ in base $b$ is $log_b N+1$. So the number of digits of $sqrt{N}$ in base $2$ is
$$log_2 sqrt{N}+1 = frac{1}{2}log_2 N +1.$$
The $frac{1}{2}$ shows why it takes half as many digits for $sqrt{N}$ as $N$.
answered Dec 3 at 13:16
B. Goddard
18.2k21340
answered Dec 3 at 13:16
B. Goddard
18.2k21340
answered Dec 3 at 13:16
B. Goddard
18.2k21340
answered Dec 3 at 13:16
B. Goddard
18.2k21340
18.2k21340
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$I think you mean $floor{log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $frac{1}{2}floor{log_b sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens.
– Luitpold Ambre
Dec 3 at 13:34
You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $lceil log_2 N rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $lceil log_2 lfloor sqrt{N} rfloor rceil.$
– B. Goddard
Dec 3 at 16:52
add a comment |
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$I think you mean $floor{log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $frac{1}{2}floor{log_b sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens.
– Luitpold Ambre
Dec 3 at 13:34
You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $lceil log_2 N rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $lceil log_2 lfloor sqrt{N} rfloor rceil.$
– B. Goddard
Dec 3 at 16:52
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$I think you mean $floor{log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $frac{1}{2}floor{log_b sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens.
– Luitpold Ambre
Dec 3 at 13:34
$newcommand{floor}[1]{leftlfloor #1 rightrfloor}$I think you mean $floor{log_b N} + 1$. This is only part of the answer. I'm not interested in all integers from $0$ to $sqrt{N}$, but only the odd integers. In the example I gave, we could take one bit less than $frac{1}{2}floor{log_b sqrt{N}} + 1$. If we use this exact quantity, we go up to $15$ instead of $7$. I haven't understood why this happens.
– Luitpold Ambre
Dec 3 at 13:34
You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $lceil log_2 N rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $lceil log_2 lfloor sqrt{N} rfloor rceil.$
– B. Goddard
Dec 3 at 16:52
You're just rounding funny. If the log comes out to be an integer, then the number is a power of 2 and hence even, so you don't have to worry about integer logs. So you might as well round up and use $lceil log_2 N rceil,$ And to get rid of your little endpoint problem, note that you might as well round the square-root down. So how about $lceil log_2 lfloor sqrt{N} rfloor rceil.$
– B. Goddard
Dec 3 at 16:52
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3024025%2fhow-many-digits-in-base-2-do-i-need-to-represent-any-odd-integer-from-1-to-sqr%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
