5
$\begingroup$

A powder can be compressed by packing it down. Each time it is packed down it loses $\frac{1}{2}$ then $\frac{1}{4}$ then $\frac{1}{8}$ ... etc. of it's total volume.

This powder is placed in to a container of unit volume and packed down. Then the remaining space is filled with fresh powder and packed down again. The packing action acts on the powder multiple times. So, for example, here is the volume of powder after the first few packings:

$(1)(\frac12) = \frac12$

$(1)(\frac12)(\frac34) + (\frac12)(\frac12) = \frac58$

$(1)(\frac12)(\frac34)(\frac78) + (\frac12)(\frac12)(\frac34) + (\frac38)(\frac12) = \frac{45}{64}$

$(1)(\frac12)(\frac34)(\frac78)(\frac{15}{16}) + (\frac12)(\frac12)(\frac34)(\frac78) + (\frac38)(\frac12)(\frac34) + (\frac{19}{64})(\frac12)$

$\vdots$

I would like to know how much powder is in the container after it has been packed n times, in terms of n.

  • 0
    In your last line, the amount added in the last step is 19/64, not 45/642010-11-07
  • 4
    Oh, so it's "powder series", not "power series"... :)2010-11-07
  • 1
    As far as the limit goes, see http://en.wikipedia.org/wiki/Pentagonal_number_theorem .2010-11-07

3 Answers 3

3

The amount of powder remaining at each point is $(1-1/2),(1-1/4),\ldots$, and so the constant you're looking for (in the limit) is

$\prod_{n=1}^{\infty} (1 - 2^{-n}) \approx 0.288788095086602$

This is also the limiting probability that an $n \times n$ matrix over $GF(2)$ be regular.

Denote the exact result for $n$ by $R_n$. We want to estimate the error $R_n - R_\infty$. Note that

$R_n = \frac{R_\infty}{\prod_{m=n+1}^{\infty} (1 - 2^{-m})}$

The logarithm of the denominator is

$-\Theta(\sum_{m=n+1}^\infty 2^{-m}) = -\Theta(2^{-n})$

and so the denominator itself is $1 - \Theta(2^{-n})$. Thus

$R_n = R_\infty (1 + \Theta(2^{-n})) = R_\infty + \Theta(2^{-n})$


The product can be converted to a sum (exercise!)

$R_\infty = \sum_{n=2}^\infty \frac{(-1)^n}{\prod_{k=2}^n (2^k-1)} = \frac{1}{3} - \frac{1}{3\cdot 7} + \frac{1}{3 \cdot 7 \cdot 15} - \cdots$

Using this sum, it's easy to prove that this constant is irrational (hint: same as the usual proof that $e$ is irrational using its series representation $\sum_{n=0}^\infty 1/n!$).

You can also obtain excellent rational approximations this way:

$1/3, 2/7, 13/45, 188/651, 5731/19845, \ldots$

Since the series is Leibniz, you know that the error after summing $k$ terms is at most the next term. For example, $5731/19845$ is at most $1/78129765$ too large than the actual constant.

  • 2
    I gave an explanation of how we might approximate $\prod_{n=1}^\infty (1-2^{-n})$ here: http://math.stackexchange.com/questions/3776/limit-of-a-particular-variety-of-infinite-product-series/3810#38102010-11-07
  • 0
    I was hoping it was simpler than this. But, on 2nd thought, this is not so bad. Thank you.2010-11-08
2

Not much help, but the limiting packing density is a factor 3.462746619. The inverse symbolic calculator finds the compression (limiting volume of the initial unit volume) as 0.2887880950866024 with the correct formula.

  • 0
    which is exactly Q from http://mathworld.wolfram.com/TreeSearching.html2010-11-07
2

The best I can come up with is horribly recursive (not so bad if you store intermediary values, as mine does below), but it would work to use Mathematica or some other software to calculate.

Define $f(0) = 0$.

$$f(n)=\displaystyle\sum_{i=0}^{n-1}\bigg(\displaystyle\prod_{j=1}^{n-i}(1-\frac{1}{2^j})\bigg)(1-f(i))$$

Mathematica code:

f[0] = 0;
f[n_] := f[n] = Sum[Product[(1 - 1/2^j), {j, 1, n - i}] (1 - f[i]), {i, 0, n - 1}]