# Tag Info

1

One way of doing it: long long and(long long a, long long b) { long long x = a^b; long long s = x>>1; while (s) { x = x|s; s >>= 1; } return a&b&~x; } First, the idea is exactly Ross'; starting from the highest bit, check if $\operatorname{bit}_k(a) = \operatorname{bit}_k(b)$ in which case the ...

4

The only bits that will be $1$ will be bits that are common to the upper bits of $A$ and $B$. Everything else will have at least one instance of a $0$ in that range. So just start from the high order bit downwards. Output the matching bits. As soon as you hit a disagreement between the binaries of $A$ and $B$ (which will be $0$ in $A$ and $1$ in $B$) ...

0

If you're doing this on a computer, it seems kind of strange to me that you want to bypass the binary representation of the numbers. But I'll try. Another user already mentioned Sloane's A000120, which includes this recurrence relation: $a(0) = 0, a(2n) = a(n), a(2n + 1) = a(n) + 1$. If your subset starts on $0$ or a power of $2$ and runs consecutively ...

2

The number of ones in the binary representation of $n$ is the greatest integer $r$ such that $2^r$ divides $$\binom{2n}n$$ See https://oeis.org/A000120 It is not too hard (but not too simple, either) to prove this by induction.

0

The fundamental result proven by Cantor's diagonal argument (as applied to the real numbers) is that: For any countable subset $S \subset \mathbb R$ of the real numbers, there is a real number $x \in \mathbb R$ such that $x \notin S$. From this result, it then obviously follows that $\mathbb R$ itself cannot be countable, since otherwise we could ...

1

one and only one irrational number can be generated that is not on the list. That is not true. If you take the number that you generate and add it to the list (say at the top), and then run the same procedure again, you will generate another number that is not on the list. You can do this ad infinitum and still not have all the real numbers in $[0, 1)$ ...

23

Cantor's diagonal argument proves (in any base, with some care) that any list of reals between $0$ and $1$ (or any other bounds, or no bounds at all) misses at least one real number. It does not mean that only one real is missing. In fact, any list of reals misses almost all reals. Cantor's argument is not meant to be a machine that produces reals not in ...

7

The order of the binary numbers $s_n$ are arbitrary. For example, if we swapped the places of $s_2$ and $s_3$, a different number will be formed. Hence there are still an infinite number of irrational numbers that can be generated.

0

You have ten bits and two "barriers": the digit changes when you hit a barrier. So you have to place two barriers within 2 of 9 possible slots. (A barrier can't be at the very end of the number, nor before the beginning. For an $n$ bit number (starting with first bit $1$) we thus have $\binom{n-1}{2}$. But be careful of two things: The two barriers ...

0

It looks like you don't consider leading zeroes, so the first digit of a number will always be an 1. If $G(n)=2$, then the last digit is 1 too. Now imagine that you extend all of your $n$s with leading zeroes until it has exactly 11 bits. The first bit will be 0, and the bit will change three times if $G(n)=2$. Now there are ten possible places where the ...

0

Since the probability of getting $x$ tails out of $y$ tosses is ${y\choose x}P^{y-x}(1-P)^x$, we just need to solve ${y\choose x}P^{y-x}(1-P)^x=0.005$ for $P.$

2

Solve the linear system $\mathbf A \mathbf c = \mathbf y$ over $\mathbb Z_2$, where the columns of $\mathbf A$ are the given vectors $\mathbf x_i$. The values of $\mathbf c$ will then indicate which $\mathbf x_i$ to include in your function $f$.

0

Well suppose you have 9 observations of Y: 0 0 0 0 1 1 1 1 1 then the 50th percentile will be 1 and you can similarly calculate percentiles as you would any other list of numbers. Also, remember that quantile regressions assign the check-fucntion to the residual, not Y directly.

0

If your input is a binary number, x2, entered in decimal format, this should work: x10=0; for i=3:-1:0 d=floor(x2/10^i); x2=x2-d*10^i; x10=x10+d*2^i; end x10 will be the decimal representation you want.

0

One stupid way: let the input be $n$. I don't know octave, so consider this pseudo-code. Usually constants in programming languages are in base $10$ If n=0, output "0" If n=1, output "1" etc Presumably you need to output a string. Another similar idea. Define an array out as ["0","1","2" ,\dots "15"] Print out(n)

0

Recall what each location in the binary form represents: the locations of the 1's describe which powers of two make up the number. For a 4-bit number, the 4 locations represent $2^3$, $2^2$, $2^1$, and $2^0$, in that order (increasing powers of two from right to left). Thus in your example, 0001: $2^0 = 1$ 1010: $2^3 + 2^1 = 8+2 = 10$ So, for the code, a ...

0

Multiply by 2 so that it becomes an integer, 13. 13 is odd so the last digit equals 1. Subtract 1, divide by 2 to determine the next digit to the left: 12/2 = 6 6 is even so the next digit is 0. Divide by 2 to determine the next digit: 6/2 = 3 3 is odd so the next digit is 1. Subtract 1 and divide by 2 to determine the next digit: (3 - 1)/2 = 1 We ...

0

You can also do other fractions; if the denominator is not a power of 2, the answer will repeat just like for decimals. To calculate, do long division. 3 into 1 goes 0, remainder 1 - digit is 0 before the binary point. Double 1, get 2 3 into 2 goes 0, remainder 2 - digit is 0 after the binary point. Double 2, get 4 3 into 4 goes 1, remainder 1 - digit is 1 ...

0

"decimals" in other bases are done the same way as regular decimals: just as $6.5 = 6\frac{5}{10}$, $110.1_2=110_2\frac{1_2}{10_2}=6\frac{1}{2}$. Similarly, $5.25=5\frac{1}{4}=110_2\frac{1_2}{100_2}=101.01_2$.

5

$13$ in binary is $8 + 4 + 1 = 1101_2$. $6.5$ is half of thirteen, so move the decimal place once: $110.1_2$.

0

$$6.5_{10} = 110.1_{2}$$ Before dot you have non-negative powers of base, after - negative. Same in decimal system. $6.5 = 6 \cdot 10^0 + 5 \cdot 10^{-1}$, $5$ is after dot. Other example $24.75 = 2 \cdot 10^1 + 4 \cdot 10^0 + 7 \cdot 10^{-1} + 5 \cdot 10^{-2}$

1

Using a subscript to denote the base we're writing in, the answer is $$6.5_{10}=110.1_2$$ In general, for any base $b$, $${1\over b}=0.1_b$$

4

Take $N$ large. Then the number of integers in $[1,N]$ which have a prime factor greater than $\sqrt N$ is asymptotic to $N \log 2$ (see http://en.wikipedia.org/wiki/Dickman_function). These numbers all require at least $\pi(\sqrt{N}) \sim 2 \sqrt{N}/\log N$ bits. Therefore the average number of bits used will be asymptotically at least as high as $(2\log ... 6 Primes are rare, but numbers with large prime factors are common. If$n$is around$2^{100}$, it will take about 100 bits to represent it in the usual base-2 way. It will take more than 100 bits to represent it your way, if it is divisible by any prime exceeding the 100th prime, and most numbers in the neighborhood of$2^{100}$are divisible by some prime ... 3 It depends on what you mean by a binary representation of all numbers and by most compact. One interpretation is a mapping$\varphi$from the natural numbers to binary strings such that given a binary string encoding possibly more than one number, there is at most one way of decoding it. For example, suppose we encode the numbers$0,1,2,3,\ldots$using the ... 1 The composition operation$R\circ S$of two relations$R$and$S$is a relation such that that$x (R\circ S) y$exactly when there exists a$z$such that$xRz$and$zSy$(e.g., if$A$is a relation between vertices of a graph representing adjacency, then$v(A\circ A)w$represents the relation of there existing a trail of length two between$v$and$w$). The ... 1 To represent$x \in [0,1]$is the same as writing$x= \sum_{n=1}^\infty \frac{x_n}{2^n}$, where$x_n$is$1$or$0$. Note that $$x > \sum_{n=1}^K \frac{x_n}{2^n}$$ for any finite natural number$K$. To find out$x_n$'s, first set$x_1= 0$if$x < 1/2$and$x_1= 1$if$x \geq 1/2$. Now consider$x- x_1/2$. Use this to set$x_2 = 0$if$x- x_1/2 < ...

0

Note: You could model the situation with generating functions. We start with some preliminary considerations, introducing a symbolic method for combinatorial structures from which we can easily derive corresponding generating functions. Problem: Let's consider binary strings containing $0s$ and $1s$. We are looking for the number of strings with length ...

0

Using fixed-point representation will work here. In such a representation the value of a given $n$-sequence of bits $\mathrm{fx}(b_{n-1} \ldots b_0)$ is scaled by a factor of $2^{-f}$. This has the effect of giving the $f$-least significant bits fractional weights. For example, a $4$-bit, two's complement, fixed point representation with $2$ fractional bits ...

1

00 starts with 00 which is non-decreasing so k=2 01 starts with 01 which is non-decreasing so k=2 10 starts with 1, but 10 is not non-decreasing, so k=1 11 starts which 11, so k=2 Three of them have k=2, one has k=1, so T(2,1)=1,T(2,2)=3

1

Since you ask for any method, I will add that making an exhaustive search for a solution is perfectly viable here. For the first exercise, you only have $2^3=8$ cases to try and in the second $2^4=16$. It may not be as elegant or give as much insight and understanding, but sometimes it's the most practical way to go.

1

Substitution works fine. Plug your second into the first to get $x_3=1$ and so on. Another ways is that the second gives you $x_1=x_2$ and you can plug that in to eliminate one of the variables.

1

Ordered sets exist and are often called sequences. The entire space of six-bit numbers might be written as $\{0,1\}^6$. Even better, use $\Bbb Z_2^6$ to give you some implicitly understood operations you can exploit, with multiplication being bitwise and, and addition being bitwise xor.

0

You could actually use a modulus other than 2 to make this work, but the process will not be necessarily convenient. Below is an example using base-10 representation, but doing doubling and halving, and after that, an example using base-10 representation, but doing tripling and taking thirds. The difference with taking thirds, is that sometimes, you have ...

0

No, it only applies to base 2. Look at this link: http://mathforum.org/dr.math/faq/faq.peasant.html#binary It explains in depth for the Russian Peasant method of multiplication, and indeed it only applies to base 2. Normally you can use it to multiply two numbers together, yet converting to base 2 is just something you can do with it. Here is a quick ...

Top 50 recent answers are included