Intereting Posts

Any two norms on finite dimensional space are equivalent
What's the probability that there's at least one ball in every bin if 2n balls are placed into n bins?
How do you prove that $p(n \xi)$ for $\xi$ irrational and $p$ a polynomial is uniformly distributed modulo 1?
Intuitive explanation of Four Lemma
prove or disprove that every positive integer is the sum of a perfect square and a prime number or 1
Infinite product
How can I show that a sequence of regular polygons with $n$ sides becomes more and more like a circle as $n \to \infty$?
If $f\colon \mathbb{R} \to \mathbb{R}$ is such that $f (x + y) = f (x) f (y)$ and continuous at $0$, then continuous everywhere
What does double vertical lines $\|$ mean in number theory?
Are there Hausdorff spaces which are not locally compact and in which all infinite compact sets have nonempty interior?
Max and min value of $7x+8y$ in a given half-plane limited by straight lines?
Finite group with elements of given order
Should isometries be linear?
Find $\sum\limits_{k=1}^{12}\tan \frac{k\pi}{13}\cdot \tan \frac{3k\pi}{13}$
Good ways to integrate $\int_0^1 x^{k+1} (1-x)^k dx$?

**Problem:**

Let $x, y,$ and $z$ be three integers. Suppose that the binary representation of

$x$ uses $n$ bits, the binary representation of $y$ uses $n$ bits and the binary representation

of $z$ uses $n$ bits. How many bits does the binary representation of the product $xyz$ use?

**Thoughts:**

- Converting $\frac{2}{7}$ to a binary number in a $32$ bit computer
- binary representation of a real number
- Binary long division for polynomials in CRC computation
- Rounding to nearest
- Determining the position of a binary value with $k$ one bits and $n-k$ zeros in an enumeration of $C_k^n$ bit strings
- Using 8x8 Binary Matrices as a hash

My first impulse is to consider the case where $x,y,z$ are all the maximal number that can be represented by $n$ bits in binary, namely that

$x=y=z=2^n -1 $.

Then $xyz = (2^n -1)^3 = 2^{3n}-2^{2n}-2^{2n+1}+2^{n+1}+2^n-1$

$=2^{2n}(2^n-1)-2^{n+1}(2^n-1)+2^n-1 = (2^{n}-1)(2^n-2^{n+1}+1)$

Expanding in this manner has not really helped me clarify what the solution should be. Any different approaches or hints would be much appreciated.

- Clarification of a remark of J. Steel on the independence of Goldbach from ZFC
- Triangular Numbers Modulo $k$ - Hit All Values?
- $\text{lcm}(1,2,3,\ldots,n)\geq 2^n$ for $n\geq 7$
- What is the significance of the power of $3$ in the sequence of primes given by $\lfloor A^{3^n}\rfloor ?$
- Value of cyclotomic polynomial evaluated at 1
- Formula for prime counting function
- Predicting the number of decimal digits needed to express a rational number
- Proving that $\sum\limits_{i=1}^k i! \ne n^2$ for any $n$
- Explicit Derivation of Weierstrass Normal Form for Cubic Curve
- Compute discrete logarithm

When you write out $(2^n-1)^3=2^{3n}-3\cdot 2^{2n}+3\cdot 2^n-1$ in binary, you get

$$\begin{align*}

\color{crimson}{1\underbrace{00\ldots 00}_{3n}-11\underbrace{00\ldots 00}_{2n}}+\color{blue}{11\underbrace{00\ldots 00}_n-1}&=\color{crimson}{\underbrace{11\ldots 11}_{n-2}01\underbrace{00\ldots 00}_{2n}}+\color{blue}{10\underbrace{11\ldots 11}_n}\\

&=\underbrace{11\ldots 11}_{n-2}01\underbrace{00\ldots 00}_{n-2}10\underbrace{11\ldots 11}_n\;,

\end{align*}$$

which has $3n$ bits. (I am assuming that $n\ge 3$.)

Note that

$$(2^n-1)^3\ge2^{3n-1}\iff\left(1-{1\over2^n}\right)^3

\ge{1\over2}$$

By Bernoulli’s inequality (or simply by expanding the cube), we have

$$\left(1-{1\over2^n}\right)^3\ge1-{3\over2^n}\ge1-{3\over8}\gt{1\over2}\quad\text{if }n\ge3$$

Thus the maximum product of three $n$-bit numbers will have $3n$ bits if $n\ge3$. As noted in Rob Arthan’s comment below Brian Scott’s answer, if $n=1$ then $(2^n-1)^3=1$ has $1$ bit (not $3$), and if $n=2$ then $(2^n-1)^3=27=11011_2$ has $5$ bits (not $6$).

- limit of a sequence. might be related to Cesaro theorem
- Derivative of a Matrix with respect to a vector
- General McNugget problem
- Proof of dividing fractional expressions
- Countable family of Hilbert spaces is complete
- Explicit descriptions of groups of order 45
- Find $f:C\to\mathbb{R}^2$ continuous and bijective but not open, $C\subset\mathbb{R}^2$ is closed
- suppose $|a|<1$, show that $\frac{z-a}{1-\overline{a}z}$ is a mobius transformation that sends $B(0,1)$ to itself.
- Continuity of function
- Exercising divergent summations: $\lim 1-2+4-6+9-12+16-20+\ldots-\ldots$
- Normalization of a quotient ring of polynomial rings (Reid, Exercise 4.6)
- Example to show the distance between two closed sets can be 0 even if the two sets are disjoint
- Can there be two distinct, continuous functions that are equal at all rationals?
- Concecutive last zeroes in expansion of $100!$
- Fourier transform of $\frac{1}{f(t)}$