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.
Subscribe to:
Post Comments (Atom)
16 comments:
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
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.
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)
Yep, there are "lots" of solutions. Do you recognise f(x)?
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)
I hadn't thought of pythagorean triples at all but f(x) and tan are related. Cast your mind back 19 years!
Right so, with tan as a big clue,
tan(x)= 2 * tan ( x / 2)
/ ( 1 - tan(x/2) * tan(x/2))
Indeed, so what does that tell you about the solutions?
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.
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!).
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)
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).
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.
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 )
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?
Post a Comment