Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 7 down vote favorite
2

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.

share|improve this question
The website you link to allows you to use factorials to create numbers $3$ and higher. – TMM Apr 24 at 14:26
(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$.) – TMM Apr 24 at 14:28
1  
You lose the factorial operator by the time they ask for 11. I'm glad you find the problem interesting! – Austin Mullins Apr 24 at 14:30

3 Answers

up vote 5 down vote accepted

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...

share|improve this answer
I got it working! Thanks so much. – Austin Mullins Apr 24 at 15:58
up vote 3 down vote

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.

share|improve this answer
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! – Austin Mullins Apr 24 at 15:59
1  
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. – Lord_Farin Apr 24 at 16:11
up vote 2 down vote

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$

share|improve this answer
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! – Austin Mullins Apr 24 at 15:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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