10 replies to this topic

[bushindo]

This is based on a previous puzzle.

 

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.

[bonanova]

Spoiler for How about

No, I won't try it myself.
But could your trig expression from RG's puzzle be generalized, by replacing "3"s with "11"s?

[bushindo]

Spoiler for How about

No, I won't try it myself.
But could your trig expression from RG's puzzle be generalized, by replacing "3"s with "11"s?

 

Comments

Spoiler for

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:

Spoiler for multiples

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]

Spoiler for My 2 cents.

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 

[Prime]

But they don't need to be integers, those 11 periodic values.

Spoiler for one messy solution

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]

Wouldn't a polynomial be continuous?

[Prime]

Oops, messed up a little...

But they don't need to be integers, those 11 periodic values.

Spoiler for one messy solution

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.
 

Spoiler for CORRECTION

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 by Prime, 29 January 2013 - 07:37 AM.

[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 by Prime, 29 January 2013 - 07:50 AM.

[bushindo]

But they don't need to be integers, those 11 periodic values.

Spoiler for one messy solution

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

Spoiler for

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.