```Author: migo (Mikhael Goikhman)
Date: 2003-Oct-29 14:27:50

<preambule>
Sorry for my poor English, it is not my native language. It is not even my
second natural language. :)
</preambule>

Here is an easy puzzle (easy if you know the solution, of course).

Using any mathematical operations and only three numbers "2" express any
natural number.

For example, using only two "2" you may express 4 as:

4 = 2^2   or   4 = 2*2   or   4 = 2+2

Returning to our task, a naive approach shows:

0 = 2 * (2 - 2)
1 = 2 ^ (2 - 2)
2 = 2 + 2 - 2
3 = 2 + 2 / 2
4 = sqrt(2 + 2) + 2
5 = ?
6 = 2 + 2 + 2
7 = ?

How would you express 2003?

If you know the answer, please don't post it for several days.

Author: tomc (Tom Carmichael)
Date: 2003-Oct-29 15:07:09

I'd say there is probably more than one solution to this problem, since you
could simply write:

2^(2-2) + 2^(2-2) + 2^(2-2) + . . . {repeat 2003 times}

Or alternatively

2 + 2 + 2 + ... {repeat 1001 times} + 2^(2-2)

Or

2*2 + 2*2 + 2*2 + ... {repeat 500 times} + 2 + 2^(2-2)

Etc.

Are there other constraints?

Author: tomc (Tom Carmichael)
Date: 2003-Oct-29 15:11:37

Sorry, I just reread the problem and say that you are limited to only 3
'2's, ignore my previous post.

Author: bandsmer (Michael Bandsmer)
Date: 2003-Oct-29 17:05:59

I don't know if this solution counts, since it kind of feels like
cheating...

First define the function
f(x) := x+(2/2),
which uses two 2's.  From this, any natural number >=2 can be expressed
using the third 2, in the form
f(f(...f(f(2))...))

Is this the solution you were looking for?  If not, then exactly which
mathematical operations are we allowed to use?

Mike

Author: migo (Mikhael Goikhman)
Date: 2003-Oct-29 17:26:54

Mike: your solution is nice, but it uses some unknown mathematical function
f(), my solution uses only known mathematical operations. :)

Author: migo (Mikhael Goikhman)
Date: 2003-Oct-29 17:30:20

Let's call the original problem "2.2.2.c".

If "2.2.2.c" is too hard for you, solve these easier problems.

Problem "2.2.2.a"
=================

How many positive integers (including 0) can you express using some
mathematical operations and three numbers "2" only? I already expressed
6 numbers, here are two additional expressions:

8 = 2 * 2 * 2 = several more ways
16 = 2 ^ (2 + 2) = (2 + 2) ^ 2 = 2 ^ 2 ^ 2 = several more ways

Are there other numbers except for these seven (the expression for 4 uses
sqrt so it does not count)?

You may use only operators "+", "-", "/", "*", "^" and grouping.

Problem "2.2.2.b"
=================

The same like the previous, but you may join digits, i.e. 22.

You may also use any reasonable mathematical functions, like sin() or
sqrt(), but you can't use such unreasonable functions like floor() or
rand(). You are also not allowed to use factorial for simlicity.

Post a list of additional numbers that you were able to express this way.

P.S. So, what is the difference between "2.2.2.b" and "2.2.2.c"? None,
except that "2.2.2.c" includes a solution for "2003" and you are not
expected to post it until November 2. :)

Author: tomc (Tom Carmichael)
Date: 2003-Oct-29 21:10:21

Well, I'm *SURE* this is not the intended solution, but an answer is
simply:

222

So long as you are using base [sqrt(4003)-1]/2.  :-)

(The positive solution to the equation 2x^2 + 2x + 2 = 2003)

Author: plewylli (Peter Lewyllie)
Date: 2003-Oct-29 22:53:52

I *SURE* hope that's not the answer, it was one of the first ideas I had,
but immediately dismissed because of "being too disappointing/unrewarding".

In the same style -> 22E-2

Peter

Author: jason (Jason Jordan)
Date: 2003-Oct-29 23:04:02

sqrt(x) = x^(1/2) = x^(2/(2*2)), which eats up all of your twos.  ;-)

There must be some trick to this.  Can you give an example of how to do it
for some number > 1000 (but not 4194304, heh), or would that give it away?

Author: migo (Mikhael Goikhman)
Date: 2003-Oct-29 23:26:50

Ok, I may give one hint (I will add one small hint every day). :)

The solution for "2.2.2.c" does not use joining like 22, i.e. separate
numbers 2 only, so I guess your tricks with a different base can't work.

But what about "easier" problems?
We may skip obvious integers 11, 20, 24, 44, 222, 484 and 4194304.
Can you produce 5 or 7, for example? ;-)

Author: jason (Jason Jordan)
Date: 2003-Oct-30 09:08:35

> The solution for "2.2.2.c" does not use joining like 22, i.e. separate
> numbers 2 only, so I guess your tricks with a different base can't work.

I can verify that joining of 2s is in fact not used in the solution.  ;-)

> But what about "easier" problems?
> We may skip obvious integers 11, 20, 24, 44, 222, 484 and 4194304.
> Can you produce 5 or 7, for example? ;-)

Now I can!  Neat puzzle.  At first I thought it was impossible, and that a
"solution" would only exist due to a clever play on words, or some
advantageous bending of the rules.  It turns out that there really is a
mathematical solution, and several of you are more or less on the right
track to finding it.

That's all I'll say for now, lest I give too much away...  ;-)

Author: plewylli (Peter Lewyllie)
Date: 2003-Oct-30 09:48:54

Does it include
- recursion
- integration
- summation/product
- stuff with variables x or n
?

Author: migo (Mikhael Goikhman)
Date: 2003-Oct-30 11:07:27

jason: I am glad someone solved it. After all this is the MATH room.
To be honest, I don't know whether I would solve it myself, but I try my
best to give hints. You see, my hint about producing 5 or 7 helped. :)

You already mentioned my next daily hint. The incorrect solutions suggested
by some people are not quite in the right direction, but they are also not
in the opposite direction, so investigating them may help.

plewylli: I have a counter question. Does all of these help you?
If yes, use it. :) However, the intended solution does not use anything
like this.

Author: migo (Mikhael Goikhman)
Date: 2003-Oct-30 11:25:08

Yesterday Peter sent me this totally incorrect, but still nice solution. :)

>> floor(sqrt(exp(ceil(sqrt(exp(2))))))
ans = 4
>> floor(exp(exp(2)))+ceil(ceil(exp(4))*floor(exp(2)))
ans = 2003

I post it here so others don't try to do it this way.

Author: tomc (Tom Carmichael)
Date: 2003-Oct-30 16:52:16

What operations are allowed exactly?  I would have thought that exp (or
e^x) would be off limit, since e is a number as well.

ln x I can see (log base e), as well as log x (log base 10), but lg x is
also commonly used (log base 2).  If the last is allowed, 5 is easy:

lg(2) + 2 + 2

So again...what is 'legal' in the problem?

Author: n4r0d (Davor)
Date: 2003-Oct-30 17:00:30

This one is like too easy...

Author: tomc (Tom Carmichael)
Date: 2003-Oct-30 17:00:16

Following up on what I just said,

(lg(2)+2)! - lg(2) = 5
(lg(2)+2)! + lg(2) = 7

Author: bandsmer (Michael Bandsmer)
Date: 2003-Oct-30 18:51:46

Believe it or not, I think I've found a way to express 2003 using ONLY TWO
2's, without using any dubious functions like floor, ceiling, or round.  (I
can also do it with three 2's, but the two-2 solution is nicer.)

So here's a question for the other people who've solved it with three 2's:
Does your method work with only two 2's?

In any case, I won't post my solution yet.

Mike

Author: jason (Jason Jordan)
Date: 2003-Oct-30 18:55:15

> So here's a question for the other people who've solved it with three 2's:
> Does your method work with only two 2's?

Technically, yes... ;)

Author: migo (Mikhael Goikhman)
Date: 2003-Oct-30 21:52:58

tomc: Finding the mathematical operations to be used is a part of the task.
In my next hint I planned to say how many different operations are used in
my solution, and in the hint after that mention one or two of them.

But, ok, I will give you a better hint. :)

If we suppose your equations for 5 and 7 are true (something that is
quastionable), then it is possible to express 2003 using ONLY ONE 2.

Author: bandsmer (Michael Bandsmer)
Date: 2003-Oct-30 22:17:01

> If we suppose your equations for 5 and 7 are true (something that is
> quastionable), then it is possible to express 2003 using ONLY ONE 2.

It occurred to me after I made my previous post that my solution method
does indeed make it possible to express 2003 using *ONLY ONE 2*.  (Had the
problem been stated this way initially, I would have thought it truly
impossible...)

Author: migo (Mikhael Goikhman)
Date: 2003-Oct-31 03:34:01

The daily hint. If you assume that the following expression

6 = 2 + 2 + 2

uses only one different mathematical operation, then the intended solution
for this puzzle uses only 3 different operations.

To answer Tom's questions, if you want to use logarithms in your solution,
then you may only use standard ln and log (natural and decimal logarithms)
implicitly. If you need another base you should specify it explicitly.
Otherwise such solution would be ambiguous, I guess.

Author: tomc (Tom Carmichael)
Date: 2003-Oct-31 13:36:24

I wouldn't expect an arbitrary base logarithm, no.  But 'lg' is a standard
notation for log base 2.  You see it commonly used in discussing big O
notation analysis for algorithms, such as mergesort being N lg N, etc.
That's the reason I suggested it.

Of course, even accepting that as a possible answer, that doesn't really
help with the 2003 problem, only the 5 and 7 problem.

(Putting 'N lg N' into google gives several eexamples, such as:
http://www.cse.ucsc.edu/classes/cmps012b/Spring97/Lecture14/sld005.htm)

So the problem is to find an acceptedly common function (nothing custom)
which yields 2003 as an answer - but that means that 'acceptedly common' is
somewhat arbitrary, since we've seen 'ceil' and 'floor' both used
successfully.

Some operations to choose:

Clearly accepted:
+ - * /
^ !
sqrt
abs

Possibly accepted:
log ln lg
trig functions (and anti-functions)
hyperbolic functions (and anti-functions)
exp  (e^x)
modulus

Stretching:
floor ceil (unless it was the 'exp' that was the problem)
fibonocci(n) (nth number in the Fibonocci sequence)
triangle(n)  (nth triangle number, i.e., n(n+1)/2)

------------------------------------------------------------

As an interesting side note, testing nearly random things, I came across
this:

pi/2 - atan(2003)  ~= 1 / 2003

Author: bandsmer (Michael Bandsmer)
Date: 2003-Oct-31 18:08:15

Tom, you may want to consider the trigonometric functions as "clearly
accepted", as suggested by one of migo's earlier posts:

> You may also use any reasonable mathematical functions, like sin() or
> sqrt(), but you can't use such unreasonable functions like floor() or
> rand(). You are also not allowed to use factorial for simlicity.

Another hint I picked up from this earlier post of his is that the
factorial function isn't needed, at least not for the intended solution.

Also, to expand on migo's hint of the day that the intended solution uses 3
distinct operations, I'll add that there is also a solution which uses only
2 distinct operations.

Author: migo (Mikhael Goikhman)
Date: 2003-Nov-01 04:07:49

This is the last hint. Tomorrow I will post my solution.

The three mentioned operations are log2 (log base 2), sqrt and "-".

If you insist on using lg to mean log2, then the puzzle is to express
any number using only one "2", otherwise it is still three "2".

I think no more hints are possible, you _must_ know the answer now. :)
I didn't have a free minute today (just released new versions of two
free software projects) to think about the Mike's solution with only
two operations.

Author: jason (Jason Jordan)
Date: 2003-Nov-01 07:02:49

Michael wrote:

> Also, to expand on migo's hint of the day that the intended solution uses 3
> distinct operations, I'll add that there is also a solution which uses only
> 2 distinct operations.

then Mikhael wrote:

> The three mentioned operations are log2 (log base 2), sqrt and "-".
>
> If you insist on using lg to mean log2, then the puzzle is to express
> any number using only one "2", otherwise it is still three "2".

Ahh, nice... I think I just discovered Mikhael's solution, and I believe
it's probably the same as Michael's 2-distinct-operation solution, except
Mikhael is also counting the '-' as an operation.

It is similar to, but more elegant than, the first solution I found, which
uses sqrt(), and logarithms in two different bases.  I suspect this is the
same method used in Michael's 3-distinct-operation solution.

Author: bandsmer (Michael Bandsmer)
Date: 2003-Nov-01 21:13:07

Whoah, migo's solution is *really* different than mine---I'm not using
log2, sqrt, OR "-"!  Instead, I'm making use of 2 trig functions.  Maybe
I'll try doing it with the log/sqrt method if I have time before tomorrow.
-- Michael

Author: migo (Mikhael Goikhman)
Date: 2003-Nov-02 01:25:07

It's getting interesting. I think I'll wait a bit with posting my solution.

I doubted whether to disallow trigonometry functions from the start.
Because it is always ambiguos, we should know whether to work in radians or
grads or whatever. I thought, trigonometry functions can't help anyway, so
it is obvious they can't be used in the solution. :)

Michael, if you want others to find your solution, formulate it properly.
Is it to express any integer number using only one number 2 and only two
distinct trigonometry functions working in radians? I can't see how more
than one "2" may be used, since all trigonometry functions I know accept
only one argument. Does posting the function names reveal the solution? :)

Author: bandsmer (Michael Bandsmer)
Date: 2003-Nov-02 05:15:36

Okay, I've figured out a nifty solution using "-", sqrt, and log2.  I'll
let Mikhael post this solution when he's ready.

If anyone wants to try figuring out my solution, the problem is this:
Express any integer >= 2 using only one 2, and up to two distinct
operations.  (As I already hinted, I happened to use trigonometric
functions, but there may be non-trigonemetric approaches as well.  The
trigonometric functions I would consider valid are sin, cos, tan, csc, sec,
cot, and their inverses (asin, acos, atan, acsc, asec, and acot).  You can
work in whatever angle system you want (radians, degrees, or gradients).  I
know of 2 solutions.

Author: migo (Mikhael Goikhman)
Date: 2003-Nov-02 09:21:32

The original solution follows. Very elegant. The tall thing is sqrt().
To express 2003, use 2003 square roots.

_____
/_____
//_____
///_____
////_____
/////_____
//////_____
7 =  -  log   log   VVVVVVV  2
2     2

You may verify this by typing "perl" in your shell and pasting this code:

sub log2 { log(\$_) / log(2) }  # perl does not have log_2, only log_e
print -log2(log2(sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(sqrt(2)))))))));

Author: jason (Jason Jordan)
Date: 2003-Nov-02 19:23:05

Similar to Mikhael's original solution, given a natural number n, use n
iterations of sqrt():

n = log  log                          2
2    sqrt(sqrt(...sqrt(2)...))

Author: submoon (Little Neo)
Date: 2003-Nov-03 16:56:16

This problem was beautiful :) . Thanks.

Author: tomc (Tom Carmichael)
Date: 2003-Nov-03 20:51:10

I tried to post before, but I guess the system went down when I was trying.

The solution is quite elegant, I like it.  There's one remaining question
in my mind:  how do you solve the problem using the trig functions, as
mentioned before?  I'd like to see that solution as well.
```