Republic of Mathematics blog

Experimenting in mathematics to get a feel for what's what. Quantifying what you don't know.

Posted by: Gary Ernest Davis on: December 16, 2010

In: Uncategorized
3 Comments

Easy to state, hard to solve, mathematics problems

Some easily stated mathematical problems are just too had for anyone currently to be able to solve.

Some outstanding examples are:

Goldbach’s conjecture: every even number $n\geq 4$ is a sum of two prime numbers.
the $3n+1$ conjecture: when we start with a positive integer and repeatedly apply one of the following two operations:

(1) if a number is even divide it by 2

(2) if a number is odd, multiply it by 3 and add 1

do we always end up with an answer of 1?

The Tower of Hanoi problem with more than 3 pegs.

The problem is to show that the conjectured smallest number of moves to solve the puzzle is in fact smallest.

Whether the fractional parts $\{(\frac{3}{2})^n\} :=(\frac{3}{2})^n-Floor((\frac{3}{2})^n)$ of the powers of $\frac{3}{2}$ are equi-distributed in the interval $[0,1]$

Whether the base 3 representation of $2^n$ always contains a 2 digit for $n\geq 9$ .
Whether $\{(\frac{3}{2})^n\}< 1-(\frac{3}{4})^n$ for all $n > 1$ .

This inequality is the remaining obstacle in the proof of Waring’s problem – a famous and outstanding problem in number theory. So even very simply stated unsolved probe can have far-reaching consequences.

The digit 2 in the base 3 representation of $2^n$

The problem of whether the base 3 representation of $2^n$ contains a 2 digit for $n\geq 9$ seems a simple curiosity that no one has the tools to tackle.

Extensive calculations indicate it seems to be true, but those calculations have to end somewhere, and maybe, just a bit further along, there will be a power of 2 whose base 3 representation does not contain a 2 digit.

So apart from more calculations of powers of 2, conversion of them to base 3, and examining the digits for a 2, what else could we do? What other experimental evidence could we bring to bear on this problem.

A sensible technique to “mathematize” any problem is to count: to ask how many “whatevers” are there?

So, instead of asking is there a 2 digit in the base 3 representation of $2^n$ , let’s ask how many 2 digits are there in the base 2 representation of $2^n$ ?

The question has now changed from an existential question (“Is there a needle in this haystack?”) to a quantitative question (“How many needles are there in this haystack?”).

To address this question let’s count and use basic descriptive statistics.

In other words, let’s gather some data and do a little exploratory data analysis.

How many 2’s are there in the base 3 representation of $2^n$ ?

To calculate large powers of 2, convert to base 3, and count the digit 2, can be very time consuming.

This calls for a computational device.

A great programming language to do these calculations is Python.

But I’m not much of a Python programmer, not much of a programmer period, so I’m going to use a simple Mathematica program:

L = {};
Do[
A = IntegerDigits[2^n, 3];
L = Append[L, {n, Count[A, 2]}],
{n, 0, 10000}]
ListPlot[L, Joined -> True, PlotStyle -> {Blue}]

Here’s the resulting plot:

The number of occurrences of the digit 2 in the base 3 representation of $2^n$ seems to grow roughly linearly with $n$ with a bit of a wobble around an average value.

Not only does the base 3 representation of $2^n$ contain a 2 digit, it appears to contain lots of them!

Let’s denote by $X(n)$ the number of occurrences of the digit 2 in the base 3 representation of $2^n$ .

How does $X(n)$ compare with the running average $\frac{X(1)+\ldots X(n)}{n}$ ?

Some calculations indicate that $X(n)$ wobbles around twice the running average. In the plot below $X(n)$ is shown in blue and $2\times \frac{X(1)+\ldots X(n)}{n}$ is shown in red:

We might loosely imagine that the closeness of the blue portion of this plot to the red line tells us that for large enough $n, X(n)$ is very roughly $2\times\frac{X(1)+\ldots +X(n)}{n}$ ; that is:

$X(n) \approx 2\times \frac{(X(1)+\ldots + X(n))}{n}$

Rearranging this approximation we get:

$X(n) \approx \frac{2}{n-2}\times (X(1)+\ldots + X(n-1))$

for $n\geq 3$ .

Statistically, we can think of this as:

$X(n) = \frac{2}{n-2}\times (X(1)+\ldots +X(n-1)) +\epsilon (n)$

for $n\geq 3$ , where $\epsilon (n)$ is an “error” term.

From a statistical point of view we want to know how is the error $\epsilon(n):=X(n) - \frac{2}{n-2}\times (X(1)+\ldots +X(n-1))$ distributed.

Below is a histogram of the error $\epsilon (n)$ for $n\leq 50000$ :

This error distribution seems quite symmetric, with a mean of approximately 0, but quite “peaky” – more so than a normal distribution.

The descriptive statistics for this distribution are:

mean = 0.0277584
stdev =59.0305
skewness = -0.0435969
kurtosis = 3.98242

So, indeed, the mean is almost 0, the distribution is quite symmetric, and the kurtosis is higher than that (3) for a normal distribution.

This is more like a logistic distribution.

As we alter the range over which we look at the error we get a distribution with a different variance.

For example, when we look at $\epsilon(n)$ for $n\leq 10000$ we get the following histogram:

This has similar features to the distribution of $\epsilon (n)$ for $n\leq 50000$ except that, notably, it has much smaller variance.

mean = 0.765212
stdev =26.2593
skewness = 0.0684994
kurtosis = 3.95492

How does the variance of $\epsilon (n)$ for $n\leq N$ vary with $N$ ?

Almost exactly linearly it seems:

Variance of $\epsilon (n)$ for $n\leq N$ with $N$ varying from 1000 to 21000 in steps of 500

What does this tell us?

This, of course, does NOT tell us that the base 3 representation of $2^n$ will always have a 2 digit.

However, it does induce a degree of confidence that not only is this true, but that we can see a good reason why it might be true: namely, the number of occurrences of the digit 2 seems to grow in a relatively orderly way with increasing $n$ and that the variations we see in the number of 2’s might be understandable statistically.

This is still a long, long way off an argument, but perhaps simple counting and basic exploratory data analysis might give us the germ of a productive idea to understand better how the digit 2 occurs in the base 3 representation of $2^n$ .

Alongside proof, mathematics is beginning to utilize techniques of statistical analysis to obtain information about quantities of interest in mathematics.

Increasingly, statistics is being used to obtain information about mathematical quantities that previously were only analyzed in a Boolean way: either they existed or did not.

Republic of Mathematics blog

Experimenting in mathematics to get a feel for what's what. Quantifying what you don't know.

Easy to state, hard to solve, mathematics problems

The digit 2 in the base 3 representation of $2^n$

How many 2’s are there in the base 3 representation of $2^n$ ?

Variance of $\epsilon (n)$ for $n\leq N$ with $N$ varying from 1000 to 21000 in steps of 500

What does this tell us?

Hans Rosling's 200 Countries, 200 Years, 4 Minutes

Math Blogging

Great mathematics sites

Visitor map

Republic of Mathematics blog

Experimenting in mathematics to get a feel for what's what. Quantifying what you don't know.

The digit 2 in the base 3 representation of

How many 2’s are there in the base 3 representation of ?

Variance of for with varying from 1000 to 21000 in steps of 500

What does this tell us?

Hans Rosling's 200 Countries, 200 Years, 4 Minutes

Math Blogging

Great mathematics sites

Visitor map

The digit 2 in the base 3 representation of $2^n$

How many 2’s are there in the base 3 representation of $2^n$ ?

Variance of $\epsilon (n)$ for $n\leq N$ with $N$ varying from 1000 to 21000 in steps of 500