9
$\begingroup$

I have run into a challenge on Codecademy.com that has me absolutely bewildered. I'm sure I'm just overlooking an obvious solution, but I've been scouring tables of trigonometric and logarithmic identities for days and I still don't know where to start. The original task is here, and it's simply called "Broken Calculator".

I've found other "Broken Calculator" problems online, but this one is the first I've seen that makes use of trig and log functions. Specifically, the only functions available are $e^x$, $ln$, $x^2$, √, $sin$, $cos$, $arcsin$, and $arccos$. The calculator defaults to 0, so you can get the number 1 by hitting $e^x$, and you can get 2 by hitting $e^x$ again, then $x^2 $, then $ln$. That's all simple.

Now, I can get any power of 2 by repeating the steps above, and similarly, given any number to start from, I can multiply or divide by a power of 2. That's easy.

The next challenge is to get 3, which I found using a 1, 2, √3 triangle and the appropriate trig functions:

$e^x$, $e^x$, √, $ln$, $arcsin$, $cos$, $e^x$, $x^2$, $ln$, $x^2$ -> 3

Again, I'm sure you find this trivial, but how would I use the same functions to get the number 11, or really any odd number for that matter other than 3?

Edit

The first two comments point out that the factorial operator is available for the first task where we need to find 3. However, in the very next task, we lose the factorial operator in exchange for the trig functions. I solved it using the steps above, but am stuck on the task to find 11.

$\endgroup$
  • $\begingroup$ The website you link to allows you to use factorials to create numbers $3$ and higher. $\endgroup$ – TMM Apr 24 '13 at 14:26
  • $\begingroup$ (With factorials, things may get easier. For instance, by getting $4! = 24$ you can go $24 \to e^{24} \to e^{12} \to e^{6} \to e^3 \to 3$.) $\endgroup$ – TMM Apr 24 '13 at 14:28
  • 1
    $\begingroup$ You lose the factorial operator by the time they ask for 11. I'm glad you find the problem interesting! $\endgroup$ – Austin Mullins Apr 24 '13 at 14:30
  • 1
    $\begingroup$ This is my original puzzle, glad everyone liked it. $\endgroup$ – TiansHUo Feb 21 '17 at 9:40
5
$\begingroup$

Indeed, all non-negative integers are achievable.

Operation 1: Using $e^x, x^2, \ln$, we can get from $y$ to $2y$.

Operation 2: Using $e^x, \sqrt, \ln$, we can get from $y$ to $\frac{y}{2}$.

Operation 3: Using $\sqrt, \arcsin, \cos, x^2$, we can get from $y$ to $1-y$, for $0<y<1$.

Clearly by operation 1, it suffices to achieve all odd positive integers. We now proceed by induction on $n \geq 1$ to prove that $2n-1$ is achievable.

When $n=1$, clearly $1$ is achievable using $e^x$.

Suppose that the statement holds for $1 \leq n \leq k, k \geq 1$. Consider $2(k+1)-1=2k+1$. Suppose that $2^a<2k+1<2^{a+1}, a \geq 1$. Then $1 \leq 2^{a+1}-(2k+1)<2^a \leq 2k-1$, and $2^{a+1}-(2k+1)$ is odd, so by the induction hypothesis $2^{a+1}-(2k+1)$ is achievable. We then start from this value, and apply operation 2 $a+1$ times to get $1-\frac{2k+1}{2^{a+1}}$, then apply operation 3 to get $\frac{2k+1}{2^{a+1}}$, then apply operation 1 $a+1$ times to get $2k+1$. Thus $2k+1$ is achievable, so we are done by induction.

I suppose a program could be written following the steps we undertook in the proof of the induction step...

$\endgroup$
  • $\begingroup$ I got it working! Thanks so much. $\endgroup$ – Austin Mullins Apr 24 '13 at 15:58
3
$\begingroup$

This solution is admittedly ad hoc, but it works.

Generate $3$ via the triangle $1/2, \sqrt{3}/2, 1$ as you already accomplished. Now, generate $5$ via the triangle $\sqrt{3/8},\sqrt{5/8},1$; finally we generate $11$ through the triangle $\sqrt{5/16},\sqrt{11/16},1$.

The details are messy because one cannot define high-level intermediary operations. But this should definitely work.


In general, the triangles $\sqrt{p/2^n}, \sqrt{(2^n-p)/2^n},1$ will likely provide you with methods to generate every odd number. But this will undoubtedly be a messy circus.

$\endgroup$
  • $\begingroup$ I think in practice, your solution works out to the same as the above. I had to accept the answer that made it more obvious how to put it into my broken calculator. Thanks so much for your insight, though! $\endgroup$ – Austin Mullins Apr 24 '13 at 15:59
  • 1
    $\begingroup$ I would've written a more comprehensive answer, but I had to leave for dinner and just wanted to get the idea across. It's only fair that you accepted the more complete answer. Happy to help. $\endgroup$ – Lord_Farin Apr 24 '13 at 16:11
2
$\begingroup$

Theorem. You can generate every odd positive integer.

Proof: Assume otherwise and let $n$ be the smallest positive odd number that cannot be generated. Clearly, $n>1$ as $$(0), e^x$$ produces $1$. For $n>1$ odd, let $2^k$ be the smallest power of $2$ that is $>n$. Then $2^k<2n$ and $m:=2^k-n$ is a positive odd number $<n$, hence can be generated. Then $$(m),e^x, \underbrace{\sqrt{x} , \ldots,\sqrt{x}}_k,\ln,\arccos,\sin,e^x,\underbrace{x^2,\ldots,x^2}_k,\ln $$ produces $n$. By simply concatenating the sequences thus found one gets a valid, but suboptimal result. Note that one may cancel any subsequences of the form $\ln, e^x$ or $\sqrt x,x^2$. $_\square$

$\endgroup$
  • $\begingroup$ I like your form of the answer because it's easy to translate to the form I need to submit, but I think in comparison to another answer, you're actually missing a step. After taking the square root k times and taking the natural log of the result, I need to take the square root again, and then square the sin of the arccos of that before multiplying by $2^k$. I definitely would never have come up with that on my own, so thank you! $\endgroup$ – Austin Mullins Apr 24 '13 at 15:52

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.