bushindo 14 Posted January 27, 2013 Report Share Posted January 27, 2013 This is based on a previous Find a closed form expression for function f(N) such that f( N ) = 0 for 1 <= N <= 11 f( N ) = 1 for 12 <= N <= 22 f( N ) = 2 for 23 <= N <= 33 f( N ) = 3 for 34 <= N <= 44 f( N ) = 4 for 45 <= N <= 55 ... No modulus or rounding operators are allowed. Quote Link to post Share on other sites

0 Solution Prime 15 Posted January 29, 2013 Solution Report Share Posted January 29, 2013 But they don't need to be integers, those 11 periodic values. As long as we have 11 periodic values, we could plug them, say, into Lagrange Interpolating Polynomial to produce integer values of our choice like [0,1,2,3,4,5,6,7,8,9,10]. Tangent seems like a good choice for a periodic function. We could plug tan(N*pi/11 - 21pi/22) as "x" variable into our Lagrange Polynomial, [tan(-21pi/22), tan(-19pi/22),...,tan(21pi/22)] as x_{k} points and [0,1,...,10] as y_{k} points. Subtract that from N, divide by 11, and voila. I am not constructing the actual formula. The main thing I seem to remember about the Lagrange Interpolating Polynomial from the time when my daughter took all those AP math classes at high school, that it's big. Anyone, be my guest and work out the details for half of my "best answer" credit. Quote Link to post Share on other sites

0 bonanova 85 Posted January 27, 2013 Report Share Posted January 27, 2013 No, I won't try it myself. But could your from RG's puzzle be generalized, by replacing "3"s with "11"s? Quote Link to post Share on other sites

0 bushindo 14 Posted January 28, 2013 Author Report Share Posted January 28, 2013 No, I won't try it myself. But could your from RG's puzzle be generalized, by replacing "3"s with "11"s? Comments Indeed that trig expression could be generalized, although the particulars are a bit more involved than replacing '3's with '11's. The devil is in the details =) Quote Link to post Share on other sites

0 Prime 15 Posted January 28, 2013 Report Share Posted January 28, 2013 I am assuming N must be an integer. As for how to slice two pi into 11 pieces, which would yield the required progression, I am stumped. I just want to throw a different thought into this subject: We already have a two-step function g(N), which outputs 1,1,2,2,3,3,... Courtesy Bushindo, we have a 3-step function f(N), producing 1,1,1,2,2,2,... Now we can construct a 6-step function: f(g(N)), or any multiple of 2 and 3-step function like 4, 6, 8, 9, etc. We could shift output of a function left or right by adding to or subtracting from the argument, e.g., f(N+1). I don't see how to construct an m-step function, where m is relatively prime to 2 and 3 by using this concept. Quote Link to post Share on other sites

0 Rob_Gandy 2 Posted January 29, 2013 Report Share Posted January 29, 2013 My equation used a piece that repeated the pattern -1, 0. Bushindo's equation used a piece that repeated the pattern -1, 0, 1. (2/sqrt(3)*[sqrt(3)/2, 0, -sqrt(3)/2) So if we use the same idea we need a pattern that repeats -5,-4,-3,-2,-1,0,1,2,3,4,5. The question now is how? (n-6-[-5,-4,-3,-2,-1,0,1,2,3,4,5])/11 Quote Link to post Share on other sites

0 bonanova 85 Posted January 29, 2013 Report Share Posted January 29, 2013 Wouldn't a polynomial be continuous? Quote Link to post Share on other sites

0 Prime 15 Posted January 29, 2013 Report Share Posted January 29, 2013 (edited) Oops, messed up a little... But they don't need to be integers, those 11 periodic values. As long as we have 11 periodic values, we could plug them, say, into Lagrange Interpolating Polynomial to produce integer values of our choice like [0,1,2,3,4,5,6,7,8,9,10]. Tangent seems like a good choice for a periodic function. We could plug tan(N*pi/11 - 21pi/22) as "x" variable into our Lagrange Polynomial, [tan(-21pi/22), tan(-19pi/22),...,tan(21pi/22)] as x_{k} points and [0,1,...,10] as y_{k} points. Subtract that from N, divide by 11, and voila. I am not constructing the actual formula. The main thing I seem to remember about the Lagrange Interpolating Polynomial from the time when my daughter took all those AP math classes at high school, that it's big. Anyone, be my guest and work out the details for half of my "best answer" credit. The variable in the Lagrange Polynomial should be tan(N*pi/11 - 10*pi/22). Starting just to the right of -pi/2 mark. And the x_{k} points must be tan(-10pi/22, -8pi/22, ... ,10pi/22]. Since we start with N=0 and want our output to start with 1, we must add another 11. Or using L for Lagrange Polynomial function: (N + 11 - L{(-10pi/22,0), (-8pi/22,1), ... ,(10pi/22,10)})/11 Edited January 29, 2013 by Prime Quote Link to post Share on other sites

0 Prime 15 Posted January 29, 2013 Report Share Posted January 29, 2013 (edited) Wouldn't a polynomial be continuous? No. We have exactly 11 pairs of points (x_{k},y_{k}). Where x_{k} is one of the tan(...) values and y_{k} is one of the integer values 0 through 10. It should be big and messy, but a regular polynomial of 10th degree. And another correction to start output with zeros instead of ones, just subtract another 1 from that whole thing. Edited January 29, 2013 by Prime Quote Link to post Share on other sites

0 bushindo 14 Posted January 29, 2013 Author Report Share Posted January 29, 2013 But they don't need to be integers, those 11 periodic values. As long as we have 11 periodic values, we could plug them, say, into Lagrange Interpolating Polynomial to produce integer values of our choice like [0,1,2,3,4,5,6,7,8,9,10]. Tangent seems like a good choice for a periodic function. We could plug tan(N*pi/11 - 21pi/22) as "x" variable into our Lagrange Polynomial, [tan(-21pi/22), tan(-19pi/22),...,tan(21pi/22)] as x_{k} points and [0,1,...,10] as y_{k} points. Subtract that from N, divide by 11, and voila. I am not constructing the actual formula. The main thing I seem to remember about the Lagrange Interpolating Polynomial from the time when my daughter took all those AP math classes at high school, that it's big. Anyone, be my guest and work out the details for half of my "best answer" credit. Excellent answer The key of the puzzle is indeed to construct 11 linearly independent terms, taking advantage of the cyclical nature of trig functions. It is then easy to construct a linear combination of the 11 terms so that they combine to be within the set [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5]. It is then straight forward to construct a closed form solution using linear algebra. Quote Link to post Share on other sites

0 Prime 15 Posted January 29, 2013 Report Share Posted January 29, 2013 (edited) Funny. I felt uncomfortable about using such complex math as Lagrange Interpolating Polynomial while not remembering how it actually worked. I set out to invent a simpler switching function, which would select one value out of 11 based on an integer variable N and then convert that value into an integer of my choice. And I have invented such formula! Thereafter, I consulted a respectable mathematical reference website and discovered that my simple and beautiful switching function was the Lagrange Interpolating Polynomial! Now I understand how it works! It appears 18th century mathematicians (Waring and Euler) invented it just for this puzzle. I shall give a better explanation the puzzle solution and Lagrange Polynomial. It could be useful to some math students and, perhaps, parents of high school students who are about to get bogged down in those dreaded AP math classes. To solve the puzzle, first we need a periodical (repeating) set of 11 values. Easy. Just take a periodic function like tan() and split its period interval into 11 parts. E.g. for tan() whose period is Pi, our step should be Pi/11. We must avoid Pi/2 + N*Pi points where tan() is not defined. The Pi/11 step avoids hitting Pi/2 naturally. However, if we wanted our 11 periodic values sorted in ascending order, we could subtract 5Pi/11, starting our sequence just to the right of -Pi/2. Thus the function tan(N*Pi/11 - 5Pi/11) shall produce a repeating set of 11 distinct numbers ranging from tan(-5Pi/11) to tan(5Pi/11). But those are real numbers not forming any linear progression, and what we need is a set of integers like [1,2,3...,11]. We shall call this set Y and its members [y_{1,}y_{2},...,y_{11}]. Lets designate the result of our tan() function as x and its 11 possible values as set R [r_{1},r_{2},r_{3},...,r_{11}]. The product (x - r_{1})* (x - r_{2})* (x - r_{3})*...* (x - r_{11}) will always be zero since x is equal to one of the R values. Now, if we remove (x - r_{1}) from the above expression, the product yields zero, except when x = r_{1}. When x = r_{1}, the expression is equal to (r_{1} - r_{2})*(r_{1} - r_{3})* ... *(r_{1} - r_{11}).Therefore dividing (x - r_{1})* (x - r_{2})* (x - r_{3})*...* (x - r_{11}) by (r_{1} - r_{2})*(r_{1} - r_{3})* ... *(r_{1} - r_{11}), yields zero, except when x = r_{1}, then we get 1. Now we can multiply that expression by corresponding number from our integer set Y (y_{1} for r_{1}) and thus obtain the expression that yields y_{1} when x=r_{1} and zero otherwise. Constructing the expressions for r_{2} through r_{11} in like manner, then adding all the expressions together we get our sequence Y [1,2,...,11]. The formula works like a selector switch. For each of the 11 values of x it turns all but one term to zero. The one non-zero term is 1 multiplied by a corresponding number from the set Y. That is the Lagrange Interpolating Polynomial. If we designate the Lagrange Polynomial as L(), the Tangent function as t(f(N)), the set of integers [1,2,3,...,11] as Y, and the set of the 11 values for tan(f(N)) as R, then the answer to the puzzle could be stated as: (N - L(t(f(N),R,Y) ) / 11. Lagrange Polynomial: http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html Edited January 29, 2013 by Prime Quote Link to post Share on other sites

## Question

## bushindo 14

This is based on a previous

Find a closed form expression for function f(N) such that

f( N ) = 0 for 1 <= N <= 11

f( N ) = 1 for 12 <= N <= 22

f( N ) = 2 for 23 <= N <= 33

f( N ) = 3 for 34 <= N <= 44

f( N ) = 4 for 45 <= N <= 55

...

No modulus or rounding operators are allowed.

## Link to post

## Share on other sites

## 10 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.