Daedalus' Second Challenge

[Daedalus]

Part 1:

 

About the same time that I discovered how to modify a function as to only affect a single output, I also discovered a way to produce the following sequence using only elementary operators {+, -, *, / and ^}:

 

{1, 1, 2, 2, 3, 3, 4, 4, etc...}

 

I do realize that a solution could be found using the floor and ceiling operators, but that will not be accepted for the answer. As in my first challenge, you are only allowed to use addition, subtraction, multiplication, division and exponents. No other operators are allowed. Also the function is restricted to the set of integers.

 

Because the domain can be shifted to start with whatever input you choose, I will accept any solution that produces the above sequence that only uses the elementary operators stated previously.

 

Part 2:

 

I will also give a five star rating and reputation to the person who can give me a single solution for the following sequences where the values are repeated according to [math]2^x[/math]:

 

{1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, etc...}

{1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, etc...}

{1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, etc...}

 

The solution that I am looking for in this case uses the elementary operators as stated for part 1 in conjunction with the series operators, [math]\Sigma[/math] and [math]\Pi[/math]. I will also accept a solution using [math]\Sigma[/math], [math]\Gamma[/math], factorials, or Pochhammer.

 

I will give this challenge a few weeks before posting the solution unless someone solves it or requests more time : )

Edited September 29, 2011 by Daedalus

[uncool]

 

First one:

 

I'm going to assume the sequence starts at 0, and give the sequence {0,0,1,1,2,2,...}, or in other words, floor(x/2); it should be clear how that can generalize.

 

First, we get the function {0,1,0,1,...} as follows:

 

(1 - (-1)^(x))/2.

 

Then we get the function {0,0,2,2,4,4,...} as follows:

 

x - (1 - (-1)^(x))/2.

 

Then to get the final thing, we get

(x - (1 - (-1)^(x))/2)/2.

 

Alternatively:

 

x/2 - 1/4 + (-1)^x/4.

 

That's part 1.

 

 

=Uncool-

[Daedalus]

Very good uncool!!! Part 1 was easy. Now lets see if you can solve part 2 : ) I have confidence that you can do it.

[Daedalus]

It's time to give you all a hint for part 2. The solution can be found in the Sierpinski triangle : )

[Daedalus]

Since noone has solved the second part of my challenge, I will post the answer.

 

 

 

Uncool solved the first part using the following "odd / even" equation:

 

[math]\frac{1-(-1)^x}{2}[/math]

 

The above equation produces a zero if [math]x[/math] is an even integer, and one if [math]x[/math] is an odd integer. We can arrive at the solution uncool derived by solving the equation which predicts the summation of the above equation:

 

[math]\sum_{x=0}^n \frac{1-(-1)^x}{2}=\frac{ 2\, n - (-1)^n + 1}{4}[/math]

 

To obtain the equation which gives us the rest of the sequences we must first derive an equation which produces the Sierpinski triangle. This can be done if we apply the odd / even function to continued summations of [math]x[/math]. Basically, we sum the sequence produced by [math]f(x)=x[/math]. Then, we continue to sum the new sequence to produce the next sequence:

 

[math]F(S, n)=\sum_{j_{1}=1}^n \sum_{j_{2}=1}^{j_{1}} ... \sum_{x=1}^{j_{S}} (x)[/math]

 

The Sth summation of [math]x[/math] from 1 to [math]n[/math] can be generalized as follows:

 

[math]F(0, n)=\sum_{x=1}^n 1=n[/math]

 

[math]F(1, n)=\sum_{x=1}^n x=\frac{n\, (n+1)}{2}[/math]

 

[math]F(2, n)=\sum_{x=1}^n \frac{x\, (x+1)}{2}=\frac{n\, (n+1)\, (n+2)}{6}[/math]

 

[math]F(S, n)=\prod_{j=0}^S \frac{n+j}{j+1}=\frac{\Gamma(S + n + 1)}{\Gamma(n) \, \Gamma(S + 2)}=\frac{\left \langle n \right \rangle_{S+1}}{(S+1)!}[/math]

 

[math]\left \langle x \right \rangle_{n}[/math] seen used in the above equation is the rising factorial or Pochhammer symbol. I prefer this notation instead of the other variations so that it is not confused with powers / exponents.

 

[math]F(S, n)[/math] produces the following sequences:

 

[math]F(0, \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\})=\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}[/math]

[math]F(1, \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\})=\{0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55\}[/math]

[math]F(2, \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10\})=\{0, 1, 4, 10, 20, 35, 56, 84, 120, 165, 220\}[/math]

 

Plugging this result into the "odd / even" function produces a series of ones and zeroes which gives us the Sierpinski triangle:

 

[math]\frac{1-(-1)^{F(S, n)}}{2}[/math]

 

which produce the following sequences (we start with [math]S=-1[/math] and [math]n=1[/math] so that we can see the triangle):

 

[math]F(-1, \{...\})=\{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...\}[/math]

[math]F(\ \ \, 0, \{...\})=\{1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,...\}[/math]

[math]F(\ \ \, 1, \{...\})=\{1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,...\}[/math]

[math]F(\ \ \, 2, \{...\})=\{1,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,1,...\}[/math]

[math]F(\ \ \, 3, \{...\})=\{1,1,1,1,0,0,0,0,1,1,1,1,0,0,0,0,1,...\}[/math]

[math]F(\ \ \, 4, \{...\})=\{1,0,1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,...\}[/math]

[math]F(\ \ \, 5, \{...\})=\{1,1,0,0,0,0,0,0,1,1,0,0,0,0,0,0,1,...\}[/math]

[math]F(\ \ \, 6, \{...\})=\{1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1,...\}[/math]

 

Now if you want the actual triangle pattern you will need to shift [math]n[/math] by [math]-(S+1)[/math]:

 

[math]\frac{1-(-1)^{F(S, \,n-(S+1))}}{2}[/math]

 

But, we can see from the above sequences that [math]F(0, n)[/math] produces the double counting sequence from the first part of my challenge. We can also see that [math]F(2, n)[/math] produces the second sequence because it generates a one followed by three zeroes and repeats. [math]F(6, n)[/math] produces the third sequence because it generates a one followed by seven zeroes and repeats. etc...

 

We can see from the Sierpinski triangle that the sequences we want occurr at the following values of [math]S[/math]:

 

[math]\{0, 2, 6, 14, 30, 62, ...\}[/math]

 

The equation which predicts these sequences is [math]2^{m+1}-2[/math] starting with [math]m=0[/math]. Substituting this equation for [math]S[/math] and summing the result gives us the solution for part two:

 

[math]G(m, n)=\sum_{j=0}^n \frac{1-(-1)^{F(2^{m+1}-2,\,j)}}{2}=\sum_{j=0}^n \frac{1-(-1)^{\frac{\Gamma(2^{m+1}+j-1)}{\Gamma(j)\, \Gamma(2^{m+1})}}}{2}[/math]

 

Interestingly enough, continued summations of [math]x^p[/math] produce the same result. I solved this equation when I was in the 11th grade in high school. The following is a generalized equation which produces the polynomials that predict the Sth summation of [math]x^p[/math] from 1 to [math]n[/math], where [math]p[/math] is any natural number not including zero:

 

[math]F(S,\, n,\, p)=\sum_{j_{1}=1}^n \sum_{j_{2}=1}^{j_{1}} ... \sum_{x=1}^{j_{S}} (x^p)=\sum_{j=0}^p \left((-1)^{j+p} \left(\sum_{k=0}^j \frac{k^p \, \left \langle -j \right \rangle_{j-k}}{(j-k)!}\right)\left(\frac{\left \langle n \right \rangle_{j+s}}{(j+s)!} \right)\right)[/math]

 

Mathematica implements the rising factorial, [math]\left \langle x \right \rangle_{n}[/math] , using:

 

[math]\text{Pochhammer}[x, n][/math]

 

 

 

Edited October 13, 2011 by Daedalus