34
$\begingroup$

Your have a scientific calculator such that most of the keys are unable to be pressed. The only keys that work are those for the functions $$ x^2 \;\; \sqrt{x} \;\; x!\;\; \exp\;\; \ln\;\; \sin\;\; \cos\;\; \tan\;\; \cot\;\; \sec\;\; \csc\;\; \arcsin\;\; \arccos\;\; \arctan $$

When a key is pressed it is applied to whatever appears on the screen and the screen changes to the result. The calculator currently displays at $0$. How can we turn the display to read $2015$?

My try was that press $\cos$, we will get 1. Then press $\arctan$, we will get $\pi/4$. Press $\sin$, we will get $\sqrt{2}/2$. Press $x^2$, we will get $1/2$. Press $\arcsin$ then $\csc$, we will get 2. We can keep using the $x^2,x!$ and $\exp$ to get a larger number, but I don't know it is possible to get $2015$? I know $2015 = 5 * 13 * 31$. Can someone help me?

$\endgroup$
  • $\begingroup$ I remember a problem from a USAMO that was like this, or maybe exactly this. Too long ago, I don't remember how was the statement there. Found it! It is not exactly like this. link $\endgroup$ – Hector Feb 21 '15 at 21:43
  • 2
    $\begingroup$ @RossMillikan I don't know, I thought about it, but I figure it requires enough math to be on topic here. $\endgroup$ – Git Gud Feb 21 '15 at 21:47
  • 1
    $\begingroup$ Do we know that this particular puzzle has a solution? What's the source? If it's an old contest problem that used a different year, and you simply updated it with "2015", it may not be solvable. $\endgroup$ – Blue Feb 21 '15 at 21:49
  • 2
    $\begingroup$ What does the $x!$ key do when the current number isn't an integer? $\endgroup$ – Henning Makholm Feb 21 '15 at 21:49
  • 1
    $\begingroup$ Out of curiosity, would it make a good question to ask about the minimum number of button-presses? I think that this would make an interesting follow-up question. $\endgroup$ – nneonneo Feb 22 '15 at 8:49
25
$\begingroup$

Using these provided operations, let's try to define primitives that can be used to build up the numbers we want. This is a constructive answer: the end result is a sequence of keys that should work.

  1. To get 1 from 0, press $x!$, $e^x$ or $\cos$.
  2. To get 1/2 from 1, we can use e.g. your solution ($\arctan$, $\sin$, $x^2$).
  3. To get $1/x$, press $\arctan$ then $\cot$, since $\cot(x) = \frac{1}{\tan{x}}$ and $\tan(\arctan(x)) = x$ for all real $x$.
  4. To get $x-1$ for $x \ge 1$, use the following sequence: $$ 1/x, \sqrt x, \arcsin, \tan, x^2, 1/x $$ This takes advantage of the identity $\tan(\arcsin(x)) = \frac{x}{\sqrt{1-x^2}}$ for $|x| \le 1$. In this case, it resolves into $\tan(\arcsin(\sqrt{1/x})) = \frac{\sqrt{\frac{1}{x}}}{\sqrt{1-\frac{1}{x}}} = \sqrt{\frac{\frac{1}{x}}{\frac{x-1}{x}}} = \sqrt{\frac{1}{x-1}} $, which we then square and invert to get $x-1$.

Now, the way is clear: we derive any number greater than 2015 (e.g. starting from 2, use $x^2, x^2, x^2, x^2$ to get 65536), then repeatedly subtract one to get to 2015. (There are lower easily-obtainable integers, such as 8! = 40320, but this answer is aimed just at finding a possible solution).

So here's one possible key sequence: $$ 0, \cos, \arctan, \sin, x^2 ( = 0.5), \\ \arctan, \cot, x^2, x^2, x^2, x^2 (=65536), \\ \arctan, \cot, \sqrt{x} (=\sqrt{1/65536}), \\ \{ \arcsin, \tan \}^{63521} (=\sqrt{1/2015}), \\ \arctan, \cot, x^2 (=2015). $$

(Note that due to numerical inaccuracy inherent to all numerical calculators, the result is probably not going to be exactly 2015. But it's a math puzzle, not a calculator puzzle, so this doesn't really matter :) )


If we want to be a bit more clever with this, we can use an approach like the one Daniil Agashiyev used in his answer to reduce the number of uses of our primitives.

We can also observe that the inverse of our $x-1$ primitive enables us to get $x+1$. Thus, we can reduce the steps to simply $$ 0, \cos, \arctan, \sin (=1/\sqrt{2}),\\ x^2, \{\arctan, \sin\}^{3} (=1/\sqrt{7}),\\ x^2, \{\arcsin, \tan\}^{4} (=1/\sqrt{45}),\\ x^2, \{\arcsin, \tan\}^{10} (=1/\sqrt{2015}),\\ x^2, \arctan, \cot (=2015). $$ This is a total of just 43 keypresses - not bad! Here we're still not using $\exp$ or $\ln$.


Finally, if our goal is to minimize the amount of button-mashing necessary to enter the number, we can bring in $\exp$ and $\ln$. Combining these with $x^2$ and $\sqrt{x}$ enables us to multiply and divide by 2, as fibonatic observed in his answer. With $x+1$, $x-1$, $2x$ and $x/2$ primitives at our disposal, we can get 2015 with just 20 keypresses:

$$ 0, \cos, \exp, \{\sqrt{x}\}^3, \ln \,(=1/8),\\ \arcsin, \tan, x^2\, (=1/63),\\ \exp, \{\sqrt{x}\}^5, \ln, \,(=1/2016),\\ \sqrt{x}, \arcsin, \cot, x^2 \, (=2015). $$

This has very good numerical stability to boot: it doesn't require any values beyond the range of a standard 32-bit float. Using 64-bit floats for computation, the result is 2014.9999999997042, within $3\cdot 10^{-10}$ of 2015.

$\endgroup$
  • $\begingroup$ Actually using double precision arithmetic (about 16 digits) to implement your solution I get 2015.0000003741022. Nice job! (Running Hector's solution takes slightly longer [a total of 344 milliseconds] and results in 2014.9996181960103.) $\endgroup$ – 2012rcampion Feb 22 '15 at 1:48
  • $\begingroup$ @2012rcampion: try the new solution: it should be a lot more stable because it does fewer calculations. $\endgroup$ – nneonneo Feb 22 '15 at 2:35
  • $\begingroup$ I get 2015.0000000000052 with Mathematica. My TI-89 displays 2015. (2015.0000000001 internally). Maybe now the challenge is to complete in the fewest keypresses? (It looks like my edit to Hector's post hasn't gone through yet, but suffice it to say that the USAMO method used over 16M keypresses!) $\endgroup$ – 2012rcampion Feb 22 '15 at 3:18
  • $\begingroup$ @nneonneo is there also a way to negate numbers too? If there is, you should be able to get any rational number (possibly even any real number), yes? $\endgroup$ – haneefmubarak Feb 22 '15 at 3:22
  • $\begingroup$ @haneefmubarak: Yes, you can negate using 1/x and exp/ln. (Specifically: exp, 1/x, ln). But it doesn't help you get "any real number" - I think that may be impossible. Getting any rational number is possible with the USAMO answer below. $\endgroup$ – nneonneo Feb 22 '15 at 8:18
8
$\begingroup$

This answer is from here.

The problem is a weaker version of USAMO 1995 Problem 2.

So that it has an answer here without having to leave the website.

We can break all the keys except for the trigonometric functions and still we should be able to get any square root of a rational number. In particular $2015$.

To prove the statement : If $m$ and $n$ are relatively prime nonnegative integers such that $n>0$, then the some finite sequence of buttons will yield $\sqrt{m/n}$.

To prove this statement, we apply induction on $m+n$. For our base case, $m+n=1$, we have $n=1$ and $m=0$, and $\sqrt{m/n} = 0$, which is initially shown on the screen. For the inductive step, we consider separately the cases $m=0$, $0<m\le n$, and $n<m$.

If $m=0$, then $n=1$, and we have the base case.

If $0< m \le n$, then by inductive hypothesis, $\sqrt{(n-m)/m}$ can be obtained in finitely many steps; then so can $\cos \tan^{-1} \sqrt{(n-m)/m} = \sqrt{m/n}$.

If $n<m$, then by the previous case, $\sqrt{n/m}$ can be obtained in finitely many steps. Since $\cos \tan^{-1} \sqrt{n/m} = \sin \tan^{-1} \sqrt{m/n}$, it follows that $\tan \sin^{-1} \cos \tan^{-1} \sqrt{n/m} = \sqrt{m/n}$ can be obtained in finitely many steps.

Thus the induction is complete.

The proof pretty much gives us a ready-to-use method for finding the sequence.

  1. Start with an empty sequence and your number $\sqrt{m/n}$.
  2. If $m\leq n$, append $\cos\arctan$ to the sequence, and change your number to $\sqrt{(n-m)/m}$, i.e. set $m' = n - m, n' = m$.
  3. Otherwise, if $m>n$, append $\tan\arcsin\cos\arctan$ to the sequence, and change your number to $\sqrt{m/n}$, i.e. set $m' = n, n' = m$.
  4. Repeat until your number is zero.

We have initially $m,n = m,1$, with $m=N^2$. That means that we will first apply step 3 to obtain $1,m$, then step 2 to obtain $m - 1,1$. This process will repeat $m=N^2$ times until we have $0,1$. Our sequence will therefore consist of:

$$ \underbrace{\tan\arcsin\cos\arctan\cos\arctan}_{N^2\text{ times}}\,0 $$

Which is equivalent to:

$$ \tan\underbrace{\arcsin\cos\arctan\cos}_{N^2\text{ times}}\,0 $$

For $N=2015$, that's $16\,240\,901$ button presses. Have fun!

$\endgroup$
  • $\begingroup$ Per request, I've converted this to community wiki. $\endgroup$ – Aza Apr 8 '15 at 22:57
6
$\begingroup$

We can adapt the idea used in the solution to the 1995 USAMO problem to construct an incrementor. For any positive integer $n$, we can go from $\sqrt{n}$ to $\sqrt{n+1}$ by the following sequence of calculator operations:

[$tan^{-1}$] [$cos$] [$tan^{-1}$] [$cos$] [$sin^{-1}$] [$tan$] (applying left to right)

Similarly, we can construct a decrementor that takes $\sqrt{n}$ to $\sqrt{n-1}$ by inverting and reversing the operations as follows:

[$tan^{-1}$] [$sin$] [$cos^{-1}$] [$tan$] [$cos^{-1}$] [$tan$]

As a shorthand, lets call incrementor sequence $[inc]$ and decrementor $[dec]$.

You already know how to get to 2. From there you can go to $\sqrt{7}$ by:
$[inc]^3$

Then hit [$x^2$] to get $\sqrt{49}$.

Now hit $[dec]^4$ to get $\sqrt{45}$.

Hit [$x^2$] again to get $\sqrt{2025}$.

Now $[dec]^{10}$ to get $\sqrt{2015}$.

And finally, [$x^2$] to get 2015.

There should probably be a faster way to get to 2015 taking advantage of the incrementor and decrementor, but this is the first I came up with.

$\endgroup$
3
$\begingroup$

All the posted answers haven't used $\exp$ and $\ln$, which can also be quite useful, for example the sequence: $[\exp][x^2][\ln]$ multiplies by two, similarly: $[\exp][\sqrt{x}][\ln]$ divides by two. The only downfall of this is that the intermediate results may exceed the largest number that the calculator can represent.

These functions can also be used to calculate $-x$, namely: $[\exp][x^{-1}][\ln]$, which can be achieved with for example with: $[\exp][\tan^{-1}][\cot][\ln]$. Given that: $\cos\left(\sin^{-1}\left(x\right)\right)=\sqrt{1-x^2}$, then the following eight long sequence can also be used to calculate $x-1$: $$ [\sqrt{x}][\sin^{-1}][\cos][x^2][\exp][\tan^{-1}][\cot][\ln] $$ The use for this sequence, instead of the already mentioned sequences in previous answers, will become clear in a bit. In order to get to 2015 from 0 you preferably want to use functions which keep the results integers, but increase as fast as possible. So $!$ and $x^2$ would be the best options. Since the given sequences to either achieve $x+1$ or $x-1$ have length 8, it would be best to minimize the need for them.

Factorial ($!$) does not come very close to 2015, namely $6!=720$ and $7!=5040$, therefore I did not really looked into using it much further. Since 2015 does not have very useful divisors I looked at the adjacent integers, 2014 and 2016. The second can be achieved with $63\cdot32=2016$, which can be achieved relatively easy by multiplying by two and one subtraction. The resulting sequence I came up with: $$ [\exp]^2[x^2]^3[\ln][x^2][x-1][\exp][x^2]^5[\ln][x-1] $$ Now if you substitute my sequence for $x-1$ in here, then the start and end functions cancel with the adjacent functions: $[x^2][\sqrt{x}]=[\ln][\exp]=x$, thus for the final expanded sequence you need 4 less button presses: $$ [\exp]^2[x^2]^3[\ln][\sin^{-1}][\cos][x^2][\exp][\tan^{-1}][\cot][x^2]^5[\ln][\sqrt{x}][\sin^{-1}][\cos][x^2][\exp][\tan^{-1}][\cot][\ln] $$ Thus only requiring 26 button presses, however $\exp{2016}\approx3.44886\cdot10^{875}$ which is very likely to exceed the largest number that the calculator can represent.

$\endgroup$
  • $\begingroup$ There's a 22-button press sequence that has no numerical stability problems. I wonder what the minimum length of the sequence is. $\endgroup$ – nneonneo Feb 22 '15 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.