Monday, February 21, 2011

Bit of a maths puzzle.


Ugh! This comes out nicely on my blog but looks like crap in Google reader, presumably because the javascript can't run.
Define a function:
\[ f(x) = \frac{2x}{1 - x^2} \] In case that maths layout thing isn't working, that's f(x) = 2x/(1-x^2)
Now, \[ f(0) = 0 \] so that repeats. Also \[ f(\sqrt 3) = -\sqrt 3 \] and \[ f(\sqrt -3) = \sqrt 3 \] so that repeats too.
The question is, what values repeat if you keep applying f to the result? I thought I knew the answer but now I think maybe it's more tricky.

16 comments:

Nelnik said...

also f(i) = i
where i is the sqrt of -1


suppose x = f(f(f(x)))
then (assuming I haven't messed up the algebra) we get the lovely sixth order polynomial:
(1-x)*(1-6*x^2+x^4)=2*x^2*(1-x^2)^2

Fergal said...

That's interesting.

I came up this puzzle "in reverse". That is, there is another way of viewing f(x) that turns this into a fairly straight forward number theory question and knowing that, it allowed me to phrase it in a much more puzzling way - with a fairly elementary function but with complex behaviour.

Anyway, in the other way, complex numbers are not at all natural to consider.

Nelnik said...
This comment has been removed by the author.
Nelnik said...

I used a google sheet to plot f(x) against x:

https://spreadsheets.google.com/ccc?key=0Ainukd--c2MldEkwdm1VajN1RDF6UGQ1c3BXT1gtdWc&hl=en&authkey=CJTIl-EO

for smallish x: abs(x) < 1
ignoring x=0
we find
abs(f(x)) > abs(x)
so when we apply f(x) the magnitude of the result is bigger than abs(x)

Also for larger abs(x),
i.e. abs(x) > sqrt(3)
we find that
abs(f(x)) < abs(x)
so when we apply f(.) the magnitude of the result is smaller than abs(x)


Thus we have stability rather than run away solutions.
i.e. dealing with absolute values, when we apply f(x):
small x's get bigger
and big x's get smaller

This suggests to me that there may be many solutions...

In contrast for say g(x) = x^2
we can see that applying g(.) to itself for x>1 the results will get bigger and bigger and so there is no hope of ever getting back to where you started.

(I posted an version of this comment a moment ago with a typo, hence I deleted it)

Fergal said...

Yep, there are "lots" of solutions. Do you recognise f(x)?

Nelnik said...

If I follow the hint you gave about it being in number theory:
It looks related to a method of generating pythagorean triples:
For x an odd integer:
A right angle triangle with sides
x and (x^2 - 1)/2
has hypotenues: (x^2 + 1)/2

Now the tan of one of the angles is:
2 * x / ( x^2 - 1)

Fergal said...

I hadn't thought of pythagorean triples at all but f(x) and tan are related. Cast your mind back 19 years!

Nelnik said...

Right so, with tan as a big clue,

tan(x)= 2 * tan ( x / 2)
/ ( 1 - tan(x/2) * tan(x/2))

Fergal said...

Indeed, so what does that tell you about the solutions?

Nelnik said...

let x = tan(z) so:
f(tan(z))= tan( 2 * z)

For notation I'll use:
g(n,x) = f(f(...f(x)))))) , (n f's)
ie. g(2,x)=f(f(x))

so g(n, tan(z))= tan(2^n * z)
seek n and z such that:
g(n, tan(z))= tan(z)
i.e.
tan(2^n * z) = tan(z)

that can happen when:
2^n * z = z + m * pi
where m is an integer
=> z = m * pi / ( 2^n -1)

and so we have solutions:
x = tan( m * pi / ( 2^n -1))

if n = 2 and m = 1
then z = pi / 3
and so x = tan(pi/3) = sqrt(3)

mmm, interesting question with rather non obvious solution.

Fergal said...

Actually I think it's more involved than that.

tan(x) = tan(y)

iff

x = y + n*pi

for some int n.

So for any x there is a t with

tan(t * pi) = x and

f^n(x) = tan(2^n * t * pi)

so f^n(x) = x

iff

tan(2^n * t * pi) = tan(t * pi)

iff

2^n * t * pi = t * pi + K * pi

divide by pi

2^n * t = t + K

for that to work, t must be rational, say a/b

so 2^n *a = a + b*K

so now we're looking for a and b such that 2^n * a = a (mod b) for some n.

I think you can achieve that for any a iff b is odd but I can't prove it yet (I suspect it's well known and I bet I knew if 15 years ago!).

Nelnik said...

So you have the formula:
2^n * t = t + K
i.e. t = K/ ( 2^n -1 )
K and n are integers
so t is rational.

and we could have
a = K
and b = 2^n -1
Thus b is indeed odd.

Anyway, I think you're making it a little more complicated than it needs to be. No need to introduce a and b.

Using my notation
z = t * pi
and from my comment:
z = K * pi / ( 2^n -1)
which is just the same as you had but pi left in.
Again when K and n are given,
we can find z and or t on the way to getting
x = tan(z) = tan ( pi * t)

Fergal said...

If I understand you correctly you're saying the set of solutions is

{tan(K*pi/(2^n-1)), for K in Int and N in Nat}

I'm saying all solutions look like

{tan(a*pi/b), for a, b in Int and b odd}.

I actually think they are the same sets but that requires a proof (although I think it's not hard).

Fergal said...

BTW a*2^n=a (mod b) with gcd(a, b) = 1 is solvable iff b is odd and yes this is something I would have known 15 years ago.

If b odd then 2^phi(b) = 1 (mod b), that's Euler's theorem. So

n = phi(b)

works for all a.

If b is even then since a has no common factors, a must be odd but 2^n*a must be even. So the LHS is even, the RHS is odd and the modulo is even so they cannot be equal.

Nelnik said...

Here's my understanding of your argument:

With a/b = k/(2^n-1)
if we're given integers k and n
with n>=1,
we can easily find a relatively prime pair of integers, a,b such that
a/b= k/(2^n-1)

Conversely given integers a,b
with b odd, we can set
n=phi(b) ( Euler Totient function)
and then using Euler's theorem, we find that
2^n-1 is divisible by b
and so
k = (2^n-1)*a/b is an integer.



Right, so here's a question:
given the 'Countdown numbers Game' rules, use input numbers 1,2,3,4,5,6
to obtain 233

Standard Countdown Rules:
Don't have to use all the input numbers.
Can't use an input number more than once.
Can use the operators +,-,*,/
and brackets.

( solution: http://sateek.com/?pg=countdown )

Fergal said...

Yes, so k/(2^n-1) can generate all of a/b with odd b.

(4*6-1)*2*5+3

Took plenty more than 30s (and I used a calculator).

Is sateek your place? I couldn't get the solution finder to work. There's only 1 box "Target value". Does that mean the Java is not displaying properly?