2
$\begingroup$

In particular, problems like $\lfloor\frac{10^{20000}}{3+10^{100}}\rfloor$. (From a putnam exam many years ago.)

Is there a general technique for attacking such problems?

1 Answers 1

3

In the contest-style problems I have seen which ask you to do something like this, the trick is generally that the number in question is somehow very close to or otherwise closely related to a special integer, and you should compute this special integer's digits (using, probably, modular arithmetic) and then figure out if the number you're interested in is larger or smaller, and by how much. For example, $\phi^n$ turns out to be very close to the Lucas number $L_n$; this is because $\phi^n + \varphi^n$ (the other root of $x^2 = x + 1$) is exactly equal to $L_n$, and $|\varphi| < 1$.

The problem I have in mind, which I can't quite remember the details of, is a question which asks you to compute the first six digits after the decimal point of some seemingly complicated expression; it turns out to be an integer minus a tiny amount, so the answer is $999999$.

In this particular case, you don't seem to be asking about a solution to the problem itself, so I will suggest for now that you think about the identity $(10^{100} + 3)(10^{100} - 3) = 10^{200} - 9$.

The best advice I can give you in general is that you should get a good sense for asymptotics.

  • 0
    Good advice, thanks. And with your hint, my example is quite easy.2010-08-27
  • 1
    This reminds me of the following problem of Richard Stanley: "Find a positive integer $n<10,000,000$ such that the first four digits (in the decimal expansion) of $n^{1,000,000}$ are all different. The problem should be solved in your head." The answer is at http://math.mit.edu/~rstan/milsol.html .2010-08-27