Closed form expression on steroids

[bushindo]

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.

[Prime]

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.

[bonanova]

No, I won't try it myself.

But could your from RG's puzzle be generalized, by replacing "3"s with "11"s?

[bushindo]

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 =)

[Prime]

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.

[Rob_Gandy]

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

[bonanova]

Wouldn't a polynomial be continuous?

[Prime]

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

[Prime]

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

[bushindo]

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.

[Prime]

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₂,...,y₁₁].
Lets designate the result of our tan() function as x and its 11 possible values as set R [r₁,r₂,r₃,...,r₁₁]. The product (x - r₁)* (x - r₂)* (x - r₃)*...* (x - r₁₁) will always be zero since x is equal to one of the R values. Now, if we remove (x - r₁) from the above expression, the product yields zero, except when x = r₁. When x = r₁, the expression is equal to (r₁ - r₂)*(r₁ - r₃)* ... *(r₁ - r₁₁).Therefore dividing (x - r₁)* (x - r₂)* (x - r₃)*...* (x - r₁₁) by (r₁ - r₂)*(r₁ - r₃)* ... *(r₁ - r₁₁), yields zero, except when x = r₁, then we get 1. Now we can multiply that expression by corresponding number from our integer set Y (y₁ for r₁) and thus obtain the expression that yields y₁ when x=r₁ and zero otherwise. Constructing the expressions for r₂ through r₁₁ 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