Tag Info

New answers tagged

0

Note: This answer is a supplement to the comment of @1999. Let $(a_n)_{n\geq 0}$ denote a sequence of numbers. We can encode this information using different kinds of generating functions. Two customary variants are ordinary generating functions: $\sum_{n=0}^{\infty}a_nx^n$ exponential generating functions: $\sum_{n=0}^{\infty}a_n\frac{x^n}{n!}$ ...


0

No, the terms unary and binary only refer to the number of arguments taken by an operation. Usually, an operation on a (non-empty) set $A$ is a function $$ A^k \to A $$ for some $k \geq 0$. An operation is said to be nullary, unary, or binary if $k$ is $0,1$, or $2$, respectively, and $k$-ary otherwise. The term external operation is rarely used, although ...


4

From right to left, the binary place values (mod 10) are $1, 2, 4, 8, 6, 2, 4, 8, 6, \dots$. You can add the reduced (mod 10) place values with $1$s in them, and then mod your answer by ten. In your example, $11001$, you would add $8 + 6 + 0 + 0 + 1=15\equiv 5 \pmod{10}$.


0

Let $ N= \{0,1,...,n-1\}$, $ I_Z(i) $ be the characteristic function of $ Z \subseteq N $, $ a=\{ I_A(i)\}_i, $ $ b=\{ I_B(i)\}_i, $ $w(a)=|A|, w(b)=|B|, w(a+b)=|A\cup B|.$ So $ |A\cup B|=|A|+|B| \Leftrightarrow A\cap B=\oslash. $


0

Perhaps this will help. First suppose you only have one symbol, so there's only one string of each length. The exponential generating function which counts these is $$\sum_{n\ge0}\frac{x^n}{n!}=e^x.$$ Now suppose you have a binary string, so there are two symbols $0$ and $1$. Say you want to know how many strings there are with $k$ zeros and $n-k$ ones. ...


1

If you know the product theorem for exponential generating functions, the result is quite understandable. I will slightly paraphrase the version presented in Miklós Bóna, Introduction to Enumerative Combinatorics: Theorem. Denote by $f_n$ the number of ways to carry out a task on $[n]$, and denote by $g_n$ the number of ways to carry out another task on ...


1

Nice statement and I agree that your proof is valid. I'll flesh it out a little bit. I'll denote that language you defined above as $\{0, 1\}^*$. This language must have a countable number of elements since it is the countable union of finite sets. Now suppose every real number can be encoded uniquely as an element of this language. That means we have ...


0

Thank you for the suggestion. Here is my proof. If $k=1 +4q$ for some $q>0$, then $$bin(k)=bin(1)+bin(4)\cdot bin(q)$$ $$b_n b_{n-1}\ldots b_2b_1b_0=001 +100 \times a_ta_{t-1}\ldots a_2a_1a_0$$ $$b_n b_{n-1}\ldots b_2b_1 1=001 + a_ta_{t-1}\ldots a_2a_1a_0 0 0$$ $$b_n b_{n-1}\ldots b_2b_1 1=001 + a_ta_{t-1}\ldots a_2a_1a_0 0 0$$ $$b_n b_{n-1}\ldots ...


0

Consider the value $k' = b_nb_{n-1}b_{n-2}...b_3b_200$. This value is divisible by 4 (specifically, it is $4 \times b_nb_{n-1}b_{n-2}...b_3b_2$), and therefore it is equal to zero, modulo 4. But $k = k' + b_1b_0$ So $$k \mod 4 = (k' + b_1b_0) \mod 4$$ $$ = ((k' \mod 4) + (b_1b_0 \mod 4)) \mod 4$$ $$ = (0 + b_1b_0) \mod 4$$ $$ = b_1b_0$$ Now since $k$ ...


3

Hint Think of the binary number $k=b_{n}b_{n-1}...b_{2}b_{1}b_{0}$ as $k=b_{0}(1)+b_{1}(2)+b_{2}(4)+b_{3}(8)+b_{4}(16)+b_{5}(32)+...$ If $b_{0}$ and $b_{1}$ are both equal to zero, then every other term in that sum is divisible by $4$.


1

Starting with $N$ zero bits and performing $F$ flips. Let's look at a single bit. There are $(N-1)^{F-k}\binom{N}{k}$ ways that our bit can be flipped $k$ times. There are $N^F$ ways the random choices can go, so define $p_k$: $$p_k = \frac{(N-1)^{F-k}}{N^F}\binom{N}{k}$$ The generating function $G(x)$ for the number of flips is: $$G(x) = \sum_k p_kx^k ...


5

After $N=2T$ toggles, the average value of any bit is $$\sum_{k=0}^{T-1}\frac{(W-1)^{2T-2k-1}}{W^{2T}}{2T\choose 2k+1}\\ =\frac12-\frac12\left(\frac{W-2}W\right)^{2T}$$ and the second term is roughly $\frac12e^{-2N/W}$. Use enough toggles to make that difference small enough.


1

As, reversing the order, $$\sum_{i=0}^{n-2}2^{i-n+2}=\sum_{i=0}^{n-2}2^i$$ the global sum is $$2(2^{n-1}-1).$$


0

You already have the representation in binary. You can just find the position of the most significant 1 for the integer part. Then for the fractionary part, if close to 0, just use $b/2^{|\log_2 b|}-1$, if on the other hand close to 1, you can use $1-(b/2^{|\log_2 b|}-1) = 2 - b/2^{|\log_2 b|}$. The first one is because of linearization of log(x+1) close ...


0

You need to specify what counts as a matching substring. For example, if 3 consecutive digits match, does that count as 1 substring, or is it 1 substring of length 3, plus 2 of length 2, and 3 of length 1? In the later case we have. $$E(\text{number of substrings}) = \sum_{k=1}^n(n-k+1)/2^k$$ where n-k+1 is the number of substrings of length k, and ...


1

Applying the proof of the geometric series to this particular case: $$ MaxInt(n) = S(n) = \sum_{i=0}^{n-2} 2^i = 2^0 + 2^1 ... + 2^{n-3} + 2^{n-2} $$ Adding up each term in the series: $$ 2S(n) = (2^0 + 2^0) + (2^1 + 2^1) ... + (2^{n-3} + 2^{n-3}) + (2^{n-2} + 2^{n-2}) $$ Simplifying: $$ 2S(n) = 2^1 + 2^2 ... + (2 \cdot \frac{2^{n}}{2^3}) + (2 \cdot ...


1

$$\large\begin{align} \sum_{i=0}^{n-2} 2^{-i+n-2} + 2^i &=\sum_{\begin{matrix}j\ +\ k\ =\ n-2\\ 0\;\le\; j,\ k\;\le\; n-2\end{matrix}}2^j+2^k\\\\ &=2\sum_{r=0}^{n-2}2^r\\ &=\sum_{r=1}^{n-1}2^r\\ &=\sum_{r=1}^{n-1}2^{r+1}-2^r\\ &=2^n-2\qquad\text{by telescoping}\quad \blacksquare \end{align}$$


3

The thing you've asked to show isn't too hard: \begin{align} \sum_{i=0}^{n-2} \left(2^{-i+n-2} + 2^i\right) &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \sum_{i=0}^{n-2}\left(2^i\right) \\ &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \left(1 + 2 + \ldots + 2^{n-2}\right) \\ &= \sum_{i=0}^{n-2} \left(2^{-i+n-2}\right) + \left(2^{n-1} - ...


1

First notice that for any $m$, $\sum_{i=0}^{m-1} 2^i = 2^m-1$. To see this (and really this is the geometric series proof applied to your situation), let $$S=\sum_{i=0}^{m-1} 2^i=1+2+4+8+\cdots+2^{m-1}.$$ Then \begin{eqnarray*} 2S&=&2+4+8+\cdots+2^{m-1}+2^m\\ &=& (-1+1)+2+4+\cdots+2^{m-1}+2^m\\&=& -1+(1+2+4+\cdots+2^{m-1})+2^m\\ ...


1

Note that xor'ing with $2^m$ simply inverts the $m+1$-th binary digit from the right, and $\!\! \mod 2^{k+i}$ simply trunctates the binary number to the last $k+i$ binary digits. $a_1\times 2^{k+i}$ ends with $k+i$ zeroes, so all the equation requires is that $2^m$ ends with $k+i$ zeroes as well, that is $m\ge k+i$.


1

Whatever the answer is, it's definitely asymptotically much less than $n/2$. For example, suppose you build a string of a single 0, followed by 2 1's, followed by 3 0's, followed by 4 1's, etc. Then the maximal palindrome substring length will be $O(\sqrt{n})$. So the answer is definitely less than or equal to $c \sqrt{n}$ for some universal constant $c$.


1

EDIT: This answer is wrong, as I neglected that the contribution of $63780$ to the interval sum is $1$, not $0$. EDIT: This answer assumes we consider all numbers in the range $0 \dots 10^{100} - 1$, i.e. including $42$. The last digit is $0$. Since we're only interested in the last digit, we can do everything mod $10$. Consider any interval of numbers ...


0

Hint: The exact sum of all products is $$ (1+1+2+3+4+5+6+7+8+9)^{100}. $$


0

This means calculating $$ d_N = S_N \bmod 10 $$ for the sum, which for $N > 1$ is \begin{align} S_N &= \sum_{k=10^{N-1}}^{10^N-1} \prod_{i=0}^{N-1} d_i^{(k)} \end{align} and $N=100$. Let us try some small instances first: $$ S_1 = \sum_{k=0}^{9} \prod_{i=0}^{0} d_i^{(k)} = 1 + \sum_{k=1}^{9} d_0^{(k)} = 1 + \sum_{k=1}^{9} k = 1 + 45 = 46, ...


0

If you need to get away with using just one index, then you can represent $2^{10}=1024$ distinct values. But if you are allowed to use two values you could have one point at some vector of index offsets. This is what is needed to be done in 32 bit OS:es when disks and/or internal memory larger than $2^{32} = 4 gigs$ of memory, and also the famous "640 kB ...


2

Mathematically, possibly the most "pure" numbering system is the system consisting of zero and the successor function $S$. In this system, instead of writing the first several non-negative integers as $0, 1,2,3,4,5,6$ and so forth, we write $$ 0,$$ $$ S(0),$$ $$ S(S(0)),$$ $$ S(S(S(0))),$$ $$ S(S(S(S(0)))),$$ $$ S(S(S(S(S(0))))),$$ and so forth. It's ...


0

Ten bits of binary give you $2^{10}=1024$ options. If you start counting at $0$, you can count up to $1023$.



Top 50 recent answers are included