# Tag Info

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.

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 ...

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$.

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$) ...

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 ... 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 ... 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$. 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. 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 ... 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$$ 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)$... 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 < ...

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

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

No. The dot product of float vectors can be fractional, but the dot product of integers is always an integer. You can certainly just scale up the floats to just before you overflow ints and round to get pretty close.

Only top voted, non community-wiki answers of a minimum length are eligible