Intereting Posts

Convergence of a sequence of non-negative real numbers $x_n$ given that $x_{n+1} \leq x_n + 1/n^2$.
If $T^n$ is $q$-contractive, $T$ exactly has one fixed point
How do I compute binomial coefficients efficiently?
Solving a radical equation for real $x$
Showing the set $A+B$ is closed.
Proving $x^n – y^n = (x-y)(x^{n-1} + x^{n-2} y + … + x y^{n-2} + y^{n-1})$
Intermediate Text in Combinatorics?
Examples when vector $(X,Y)$ is not normal 2D distribution, but X and Y are.
Variational formulation of Robin boundary value problem for Poisson equation in finite element methods
How would you evaluate $I:=\int_ {0}^{\infty} \frac {\cos(ax)} {(x^2 + b^2)^n} \ \mathrm{d}x$?
Is $\pmb{\eta}\cdot\pmb{\omega_1} = (\pmb{\eta} + \pmb{1})\cdot\pmb{\omega_1}$?
Simple optimization trick
Verifying the examples of Dual Space
Proof that ideals in $C$ are of the form $M_c$ that should not involve Zorn's Lemma
Why is the set of integers in $\mathbb{R}$ closed?

So given any binary string B:

$$b_1 b_2 \dots b_n$$

$$b_i \in \{0,1\}$$

It would seem it is always possible to make a partitioning of B:

- Decomposing a discrete signal into a sum of rectangle functions
- Combinatorics Pigeonhole problem
- Simplifying $\sum_{k=0}^{\lfloor{\frac{n}{2}}\rfloor}\binom{n}{2k}2^{2k}$
- Find $g$ using euclids algorithm
- Prove that $\lfloor\lfloor x/2 \rfloor / 2 \rfloor = \lfloor x/4 \rfloor$
- How many fours are needed to represent numbers up to $N$?

$$ b_1 b_2 \dots b_{p_1}|b_{p_1 + 1}b_{p_1 + 2}\dots b_{p_2}|\dots|b_{p_m + 1}b_{p_m + 2}\dots b_n$$

$$= P_0 | P_1 |\dots|P_m$$

such that when $P_i$ is interpreted as the binary representation of an integer then:

$$\exists{k}:\sum_{i=0}^{m}P_i = 2^k$$

For example here is the first few:

```
1 = 1
10 = 2
1|1 = 2
100 = 4
1|01 = 2
11|1 = 4
1000 = 8
1|00|1 = 2
10|10 = 4
1|0|11 = 4
...
```

Additional examples are here: http://pastebin.com/3B2P4asC

How can we prove this for all binary strings?

- Thoughts on the Collatz conjecture; integers added to powers of 2
- Coupon Collector Problem with Batched Selections
- Prove that: $2^n < n!$ Using Induction
- Number of ways to put $n$ unlabeled balls in $k$ bins with a max of $m$ balls in each bin
- On Shanks' quartic approximation $\pi \approx \frac{6}{\sqrt{3502}}\ln(2u)$
- Efficient Method to find funsum$(n) \pmod m$ where funsum$(n)= 0^0 + 1^1 + 2^2 + … n^n$
- Prove that $\sim$ defines an equivalence relation on $\mathbb{Z}$.
- Clever use of Pell's equation
- Prove $1(1!)+\dots+n(n!) = (n+1)!-1$ using induction
- Does Chaitin's constant have infinitely many prime prefixes?

This is (essentially) problem 6 in the MSRI newsletter, Emissary, for Fall 2011:

You are allowed to transform positive integers $n$ in the following

way. Write $n$ in base 2. Write plus signs between the bits

at will (at most one per position), and then perform the indicated

additions of binary numbers. For example, $123_{10} = 1111011$

can get + signs after the second, third and fifth bits to become

$11+1+10+11 = 9_{10}$; or it can get + signs between all the bits

to become $1+1+1+1+0+1+1 = 6_{10}$; and so on.

Prove that it is possible to reduce arbitrary positive integers to 1 in

a bounded number of steps. That is, there is an absolute constant $C$

such that for any $n$ there is a sequence of at most $C$ transformations

that starts with $n$ and ends at 1.

Comment: The best possible bound is a real shocker.

No solution is given.

Look at two and three bit strings starting with 1, and the minimum and maximum ways they can contribute to the sum.

$$

\begin{array}{c|c|c}

T & A(T) & B(T) \\

\hline \\

1 & 1 & 1 \\

10 & 1 & 2 \\

11 & 2 & 3 \\

100 & 1 & 4 \\

101 & 2 & 5 \\

110 & 2 & 6 \\

111 & 3 & 7

\end{array}

$$

For example, we can count 110 as $1+1+0=A(110)$ or as $6=B(110)$ (the only other possibilities are $1+2$ and $3+0$). So for the two-bit strings $B(T)=A(T)+1$, and for the three-bit

strings $B(T)-A(T)\in\{3,4\}$.

Now consider a number $k$ and let $w(k)\ge 6$ be the number of 1 bits in

its binary representation.

Split $k$ into components like this:

$$

(k)_2 = T_1 0^* T_2 0^* T_3 \ldots T_{c+3} 0^* T_{end}

$$

where each $T$ starts with 1, each of $T_1,T_2,T_3$ has exactly two

bits, and each of $T_4,\ldots,T_{c+3}$ has exactly three bits, and $T_{end}$ can be empty or can contain 1,10 or 11 if $(k)_2$ ends that way without allowing another 3-bit term. In

other words, gather terms in a greedy fashion starting with the next

available 1-bit taking two or three bits as required, skipping

extra zeros, and assigning the left-over to $T_{end}$. For example

$$

(999999)_2 = 11~~11~~0~~10~~000~~100~~0~~111~~111

$$

so for $n=999999$ we would get

$$T_1=T_2=11,T_3=10,T_4=100,T_5=111,T_6=111,c=3,T_{end}=\text{empty}$$

For each type of term $A(T)$ counts the bits in $T$, so $\sum A(T_i) =

w(k)$ (including $T_{end}$ in the sum).

Now we can use our terms as a counter as follows.

- Start counting each term with $A(T)$ to sum to $w(k)$.
- To increment, count $T_1$ as $B(T_1)$ to get $w(k)+1$.
- Count $T_2$ as $B(T_2)$ to get $w(k)+2$.
- Count $T_3$ as $B(T_3)$ to get $w(k)+3$.
- Count $T_4$ as $B(T_4)$ and reset to $A(T_i),i=1,2,3$ to get either

$w(k)+3$ or $w(k)+4$.

Repeat this, counting more 3-bit terms as $B(T)$ to add 3 or 4 at a time (and finally $B(T_{end})$ if applicable),

counting $T_1,T_2,T_3$ as $A$ or $B$ to get the increments in between.

By this counting method we find partitions that sum to each number between $w(k)=\sum A(T_i)$ and $\sum B(T_i)$.

Let $z$ be the number of terms that are $T=111, A(T)=3, B(T)=7$.

Then

$$

\begin{align}

w(k) = \sum A(T_i) & \le 6+(2c+z)+2 \\

w(k)-8 & \le 2c+z \le 3c \\

c & \ge w(k)/3-8/3 \\

\sum B(T_i) & \ge \sum A(T_i)+3+3c+z \\

& \ge w(k)+3+w(k)/3-8/3+w(k)-8 \\

& = 7w(k)/3-23/3

\end{align}

$$

So for any $k$ we can find a partition that sums to each value in $[w(k),\max(w(k)+3,7w(k)/3-23/3)]$. For all $w(k)\ge 6, w(k)\ne 9, w(k)\ne 10$ this interval contains a power of 2.

We handle the remaining possible values for $w(k)$ as special cases.

For $w(k)=10$ we can just use a refinement of the bound above. In this case $c\ge 1$, so $\sum B(T_i) \ge \sum A(T_i)+6$, so 16 will be included.

$w(k)=1,2,4$ are immediate, just add the bits. For $w(k)=3$ we can always partition the number into $10,1,1$ or $11,1$ and possibly some zeros. For $w(k)=5$ if all 1 bits are adjacent, we can write it as $1111,1$, otherwise we can write it as $101,1,1,1$ or $100,1,1,1,1$.

For $w(k)=9$ if all bits are adjacent, then we can take $11111111,1$. Otherwise there is either a 100 or 101 which we take as $T_1$. From the remaining bits make a three-bit term $T_2$ and a two-bit term $T_3$. Then either $B(T_1)+B(T_2)$ or $B(T_1)+B(T_2)+B(T_3)$ plus the remaining bits makes 16.

This answers the original question.

As an addendum, we can extend this technique taking longer terms, e.g. for 4-bit terms $A(T)+7 \le B(T) \le A(T)+11$, so we can take 11 two-bit terms and $c$ 4-bit terms and count from $w(k)$ to at least $w(k)+11+7c$.

For 5-bit terms $A(T)+15 \le B(T) \le A(T)+26$ and with 26 two-bit terms we can count from $w(k)$ to $w(k)+26+15\lfloor (w-26)/5\rfloor$. For $w(k)$ large enough this upper bound is larger than $3w(k)$, so the interval will contain a power of 3.

Carrying it further, taking $l$-bit terms for larger $l$ we can extend this interval to any multiple of $w(k)$. Thus, for choice of any $q>1$ there is a bound $W(q)$ so that any number $k$ with Hamming weight large enough $w(k)>W(q)$ can be partitioned into $P_i$ with $\sum P_i = q^m$ for some $m$.

- When do the Freshman's dream product and quotient rules for differentiation hold?
- Using induction to prove that $2 \mid (n^2 − n)$ for $n\geq 1$
- Best Algebraic Topology book/Alternative to Allen Hatcher free book?
- One last question on the concept of limits
- Exponential of matrices and bounded operators
- Preconditioning for an LBFGS
- Nested exponent modulus, $2^{2^517} ( mod 23)$
- Does $\lfloor \sqrt{p} \rfloor$ generate all natural numbers?
- Why $\lim\limits_{n\to \infty}\left(1+\frac{1}{n}\right)^n$ doesn't evaluate to 1?
- What's the intuition with partitions of unity?
- Strictly associative coproducts
- A proof for the inequality $\sum_{i=0}^{t-2}{\frac{1}{t+3i}} \leq \frac{1}{2} $ for all $t \geq 2$
- Prove that an infinite ring with finite quotient rings is an integral domain
- Closed-form of sums from Fourier series of $\sqrt{1-k^2 \sin^2 x}$
- If space of bounded operators L(V,W) is Banach, V nonzero, then W is Banach (note direction of implication)