1
$\begingroup$

We are given some expression, or formula, that outputs a number or expression for a number, we know that this number's decimal expansion is equal to that of Pi for the first 10^10^10^10^10 digits, then differs by 1 digit, is there a practical method to find out if this number is larger or smaller then Pi?

  • 0
    @mixedmath, it was the first problem on the first Putnam I took, and I'm proud to say that I solved it.2011-04-27

3 Answers 3

2

Thought I would point out something that may not be obvious to the OP: it depends on the expression/formula. As a numerically absurd example, look at the truncated "Leibniz" series for $\pi$: $\frac{4}{1}-\frac{4}{3}+\frac{4}{5}-\frac{4}{7}+ \cdots +(-1)^{N}\frac{4}{2N+1}$ As $N\to\infty$, this sum approaches $\pi$, glacially! Let us assume that $1$ gazillion is an even number. If we know that our approximation to $\pi$ was obtained using $N$ equal to $1$ gazillion, then the last term used had a $+$ sign in front of it, meaning that our estimate is an overestimate.

1

Even if we only had a number whose expansion was identical to $\pi$ up to $10^{10^{10^{10^{10}}}}$ (I really just wanted to type that in to see how it was typeset), we could use it for $\pi$. We could then approximate the circumference of the known universe, and the error would be less than the apparent width of a blade of grass on a planet around Alpha Centauri, as seen from the Earth.

On a slightly more serious note: 10^10^10 is already more than the estimated number of atoms in the universe. We only know $\pi$ to a lousy $10^{13}$ number of digits. More problematically, one would have to be incredibly witty to store a number of size 10^10^10^10^10 on a computer, as what sort of memory can hold all that information? Not something in bits - it requires more bits than there are atoms.

But let us assume that we are merely interested in determining how two numbers are ordered. In general, it depends very much on how these two numbers are represented. If it's reasonable, simply subtract them and see what happens. Too small? Multiply by a large number and mod out by 1000. Conceivably, this could be iterated.

  • 0
    No worries, I've made that error quite a few times, too. :)2011-04-27
0

If you only know the first gazillion digits and they are equal to the ones of $\pi$ then you cannot decide the question.

If your question is whether you can somehow "skip" the first gazillion digits and find some that are different, I propose the example of the

$\pi=\sum_{n=0}^{\infty}(4/(8n+1)-2/(8n+4)-1/(8n+5)-1/(8n+6))(1/(16))^n$

by Bailey, Borwein and Plouffe that allows to calculate a certain digit in base $16$ without calculating other digits.

So, if you compared this to another expression that allowed this kind of calculation, you could randomly compare digits without calculating intermediate digits.

  • 0
    I think it still takes O(n) memory to use that formula.2011-04-27