A challenge
I got bored during some lessons today, and tried to solve the following problem I made up. I thought others here might enjoy it.
Using a standard calculator, you can reference the previous answer with the Ans key. By pressing equals repeatedly, you can move along iterative series.
E.g. U1=1 Un+1=2*Un becomes in calculator keys "1 [equals] 2 * Ans" and then pressing equals to iterate.
A series that eventually returns to its original value is an oscilating series. The number of terms it has cycles through is the order of the oscillation.
An order one expression would be "Ans"
An order two expression would be "1/Ans"
Using only standard calculator buttons, come up with a sequence that has order 4, and then (harder) order 3. What if you were only confined to addition, multiplication, raising to an integer power and the inverses?
All of the above are possible. They took me a while to do though, so you might want to save it till you are bored at the end of a Maths exam :-).
The open question is "is it possible to construct an expression with order n ?".
[edited by - sadwanmage on February 26, 2004 10:51:16 AM]
quote:Original post by sadwanmage
The open question is "is it possible to construct an expression with order n ?".
What do you mean open ? That nobody knows, or that the book didn''t provide an answer? I found a way to do it. My solution involves trigonometry. Is that allowed?
Order 1 : 1 * ans
Order 2 : -1 * ans
Order 3 : j * ans
Order 4 : i * ans
Order n : w * ans (where w = exp( i * 2 * pi / n ))
This all comes from the solutions w of the equation w^n = 1 in complex space.
EDIT : WHAT calculator?
[edited by - ToohrVyk on February 26, 2004 11:30:14 AM]
Order 2 : -1 * ans
Order 3 : j * ans
Order 4 : i * ans
Order n : w * ans (where w = exp( i * 2 * pi / n ))
This all comes from the solutions w of the equation w^n = 1 in complex space.
EDIT : WHAT calculator?
Victor Nicollet, INT13 game programmer
[edited by - ToohrVyk on February 26, 2004 11:30:14 AM]
On a completely different topic, a series that comes back to its initial value is not always oscillating, although in your specific case (series defined by a first-order relation) it''s true.
The simplest example of this is the series u(n) = n * (1+(-1)^n)
The simplest example of this is the series u(n) = n * (1+(-1)^n)
In general, a sequence of order n can be made using a polynom of order n-1. For instance, setting a(n+1) = -3/2*a(n)^2 + 5/2*a(n) + 1, a(0) = 0, gives the series: 0, 1, 2, 0, 1, 2, 0, 1, 2, ...
Sorry, I realize now order is the wrong term. I mean period I think. Thats why I explained it rather than assume everyone knew what I meant.
ToohrVyk, you are quite correct (except for your order 3 example as i=j), but my calculator does not deal with complex numbers. Its more of a challenge that way. I confess this solution had not occured to me, so well done. Now try it with a worse calculator. I''m leaving the precise calculator ambiguous as is more interesting to see different solutions, but if you must know I was using a Casio fx-85WA.
Alvaro, yes, well done there is a way to do it trigonometrically. But as I said, there is the further challenge of being limited to addition, multiplaction, raising to integer powers and their inverses. I suppose now I have done it another way, I''ll have a go at finding yours.
AP: That is an excellent solution, and one which I had not even considered (I like it as it doesn''t involve anything beyond addition and multiplication). The question still stands about arbitrary length. I''ll add the condition that the length of the formula must be O(log(n)) or less if n is the period. I.e. you cannot add an extra term for each increase of 1 in n ( as that would be O(n) ), but a formula that had the period required written in it would still work.
By open, I meant I could not see how to do it. There is no book I am getting it from, it''s just a puzzle I made up and enjoyed doing, and thought there would be some people on gamedev who would also enjoy the challenge. Anyway, since my last post I figured out how to do it for an arbitrary periodicity. For that I only required brackets, addition, subtraction, squaring and square rooting. It only required 20 button presses to enter it (though it was originally in a form requiring ~70).
I found getting that a tough challenge. I must have spent an hour and a half working on it.
Don''t waste any time on this if you don''t want to. Its purely for your own amusement.
Seeing everyone has given such a wide range of answers, I am beginning to see that it is not such a good question to use as a puzzle. That said, it is still interesting to see different solutions.
ToohrVyk, you are quite correct (except for your order 3 example as i=j), but my calculator does not deal with complex numbers. Its more of a challenge that way. I confess this solution had not occured to me, so well done. Now try it with a worse calculator. I''m leaving the precise calculator ambiguous as is more interesting to see different solutions, but if you must know I was using a Casio fx-85WA.
Alvaro, yes, well done there is a way to do it trigonometrically. But as I said, there is the further challenge of being limited to addition, multiplaction, raising to integer powers and their inverses. I suppose now I have done it another way, I''ll have a go at finding yours.
AP: That is an excellent solution, and one which I had not even considered (I like it as it doesn''t involve anything beyond addition and multiplication). The question still stands about arbitrary length. I''ll add the condition that the length of the formula must be O(log(n)) or less if n is the period. I.e. you cannot add an extra term for each increase of 1 in n ( as that would be O(n) ), but a formula that had the period required written in it would still work.
By open, I meant I could not see how to do it. There is no book I am getting it from, it''s just a puzzle I made up and enjoyed doing, and thought there would be some people on gamedev who would also enjoy the challenge. Anyway, since my last post I figured out how to do it for an arbitrary periodicity. For that I only required brackets, addition, subtraction, squaring and square rooting. It only required 20 button presses to enter it (though it was originally in a form requiring ~70).
I found getting that a tough challenge. I must have spent an hour and a half working on it.
Don''t waste any time on this if you don''t want to. Its purely for your own amusement.
Seeing everyone has given such a wide range of answers, I am beginning to see that it is not such a good question to use as a puzzle. That said, it is still interesting to see different solutions.
Sorry for that j part... I wrongly assumed that was the standard notation. Here, we use j = -1/2 + sqrt(3)/2 i.
My general solution using trigonometry is computing tan(atan(Ans)+360/n). This happens to be a projectivity of the real projective line into itself, so it has the form x |-> (a*x+b)/(c*x+d), for appropriate values of a, b, c and d. I am not sure if you can find those constants with only the operations that you are allowing (for n=3 and n=4 of course you can).
I also thought of AP''s solution (setting up a polynomial with whatever values you want), but it has the problem that it only works for a few initial values.
I also thought of AP''s solution (setting up a polynomial with whatever values you want), but it has the problem that it only works for a few initial values.
quote:Original post by alvaro
I also thought of AP''s solution (setting up a polynomial with whatever values you want), but it has the problem that it only works for a few initial values.
On the other hand, you can get any sequence you like that way.
Seeing as everyone else has disclosed their method, my method was:
Un+1=(1-Un+sqrt((1-Un)^2))*q+Un-2
or in calculator terms
(1-Ans+sqrt(1-Ans)^2)*q+Ans-2
where q is the period you want. Start at 0. With a few simple modifications, you can make it to repeat any subsequence within an arithmetic progression, which is why I liked it so much.
(The trick in it is emulating abs by taking the square root of a square. From then on it is manipulation).
Again, with a enough patience you can extend this method to arbitrary sequences, as the expression:
(Ans-n-1+sqrt(Ans-n-1)^2+Ans-n+1+sqrt(Ans-n+1)^2)/2-(Ans-1+sqrt(Ans-n)^2)
returns 1 when Ans=n and 0 otherwise (given Ans & n are integers), so you can just sum a whole series of expressions each of which states roughly: "if Ans=Un then return Un+1 else return 0" for some n.
I had figured there was a trigonometric one, but got bored after a couple of failed attempts with sin and cos. Its much neater.
Here is France for you is it, ToohrVyk?
I dunno about the rest of the world, but here in England convention has recently changed so that j instead of i is the sqrt(-1), so both are used and everyone is confused. I had no idea other countries had a different convention.
Un+1=(1-Un+sqrt((1-Un)^2))*q+Un-2
or in calculator terms
(1-Ans+sqrt(1-Ans)^2)*q+Ans-2
where q is the period you want. Start at 0. With a few simple modifications, you can make it to repeat any subsequence within an arithmetic progression, which is why I liked it so much.
(The trick in it is emulating abs by taking the square root of a square. From then on it is manipulation).
Again, with a enough patience you can extend this method to arbitrary sequences, as the expression:
(Ans-n-1+sqrt(Ans-n-1)^2+Ans-n+1+sqrt(Ans-n+1)^2)/2-(Ans-1+sqrt(Ans-n)^2)
returns 1 when Ans=n and 0 otherwise (given Ans & n are integers), so you can just sum a whole series of expressions each of which states roughly: "if Ans=Un then return Un+1 else return 0" for some n.
I had figured there was a trigonometric one, but got bored after a couple of failed attempts with sin and cos. Its much neater.
Here is France for you is it, ToohrVyk?
I dunno about the rest of the world, but here in England convention has recently changed so that j instead of i is the sqrt(-1), so both are used and everyone is confused. I had no idea other countries had a different convention.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement