« previous next »
Pages: [1]   Go Down

Author Topic: Non-linear sequence  (Read 7433 times)

0 Members and 1 Guest are viewing this topic.

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Non-linear sequence
« on: April 27, 2011, 01:48:00 am »
Given a function f(x) that operates on the set of whole numbers, for every xn, there is a corresponding yn in the set of integers that is equal to the function applied to the integer xn.

x|y
---
1|1
---
2|3
---
3|7
---
4|13
---
5|31
---
6|49
---
7|115
---
8|215
---
9|509
...

What is the function f(x)? More generally, what is the value of y for any integer xn?

Hints (since this is likely to be difficult):
  • The function is only defined for positive integers. However, it is defined for *all* positive integers.
  • The function does in fact follow the general upwardly trend that you can see. It's not a pathological function that will go insane the second you extend the values. However, there are two arguments to the function, one of which I have kept constant simply because the equation is too chaotic if it's allowed to change.
  • This isn't a standard type of function, so any answer that correctly predicts the subsequent terms of the sequence will be accepted
  • It doesn't involve Nethams. I'm serious.
« Last Edit: April 27, 2011, 01:48:59 am by Qwerty.55 »
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline phenomist

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 132
  • Rating: +46/-3
    • View Profile
Re: Non-linear sequence
« Reply #1 on: April 27, 2011, 02:19:09 am »
Looks like it's very close to powers of two. Let's express it in binary.

x|y
---
1|1
---
2|3
---
3|7
---
4|13
---
5|31
---
6|49
---
7|115
---
8|215
---
9|509
1
11
111
1101
11111
110001
1110011
11010111
111111101
At first I thought I saw a Sierpinski triangle, but it appears not.
Perhaps it's still a cellular automaton though. (1-D hopefully)

Left-align doesn't appear too productive - note that 110 maps to 1 in 4~5, but maps to 0 in 7~8
So try right align?

000000001
000000011
000000111
000001101
000011111
000110001
001110011
011010111
111111101
000 => 0
001 => 1
010 => 1
011 => 1
100 => 0
101 => 1
110 => 1
111 => 0

so Rule 110 CA. IIRC, it's one of those CAs that is Turing complete or something.
Logged
+2/-0 karm for this message
Level Designer for Graviter

[Disclaimer: I can't program for my life.]

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Non-linear sequence
« Reply #2 on: April 27, 2011, 02:21:16 am »
Yeah, that's the function. Nice work. I'm still curious what the nth term is though... :P
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Non-linear sequence
« Reply #3 on: April 27, 2011, 02:22:50 am »
Psh, would you like an equation to model the values? I have one that I am about to test! I literally just used two pages of paper to draw out everything XD
Logged

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Non-linear sequence
« Reply #4 on: April 27, 2011, 02:23:43 am »
An equation would be nice.
* Qwerty.55 is surprised it only took two pages...
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Non-linear sequence
« Reply #5 on: April 27, 2011, 02:32:47 am »
Blegh, I made a mistake somewhere :/ I was trying to make one that had a third variable that could be any number and would still work. I know I can (I just added f(10)=m). I have a final project, though, so when I am finished with that, I'll get back to this :)
Logged

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Non-linear sequence
« Reply #6 on: April 28, 2011, 09:33:13 am »
Okay, sorry to be so late x.x I literally only went to class and then immediately slept when I got back. I remembered this in the last half hour of psychology and it was the only way I could stay awake x.x:

1+2034X-15334X(X+1)/2+50686X(X+1)(X+2)/6-95994X(X+1)(X+2)(X+3)/24+113930X(X+1)(X+2)(X+3)(X+4)/120-86756X(X+1)(X+2)(X+3)(X+4)(X+5)/720+41386X(X+1)(X+2)(X+3)(X+4)(X+5)(X+6)/7!-11306X(X+1)(X+2)(X+3)(X+4)(X+5)(X+6)(X+7)/8!+1354X(X+1)(X+2)(X+3)(X+4)(X+5)(X+6)(X+7)(X+8)/9!

Maybe later today I will come up with a more general version that has "m" in the equation, too.

EDIT: This version only took 1 page :P
EDIT2: Screenshot of equation:
Xmin=0
Xmax=10
xscl=1
Ymin=-10
Ymax=509
Yscl=0
Xres=1
« Last Edit: April 28, 2011, 09:46:18 am by Xeda112358 »
Logged
+1/-0 karm for this message

Offline ZippyDee

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 729
  • Rating: +83/-8
  • Why not zoidberg?
    • View Profile
Re: Non-linear sequence
« Reply #7 on: April 28, 2011, 10:14:18 am »
I don't completely understand phenomist's explanation...In fact, I don't understand it at all. Can someone explain that explanation? xD
Logged
There's something about Tuesday...


Pushpins 'n' stuff...

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Non-linear sequence
« Reply #8 on: April 28, 2011, 10:56:09 am »
I don't understand this part:
Quote from: phenomist on April 27, 2011, 02:19:09 am
000 => 0
001 => 1
010 => 1
011 => 1
100 => 0
101 => 1
110 => 1
111 => 0

so Rule 110 CA. IIRC, it's one of those CAs that is Turing complete or something.
Everything else is just converting to binary and looking at the pretty patterns :)
At least I think... I just liked looking at the diagonals :)
Logged

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Non-linear sequence
« Reply #9 on: April 28, 2011, 11:00:27 am »
Elementary cellular automata are defined by a function of the 3 pixels in the row above. So, to determine a pixel, you look at those three pixels above and whether the pixel is on or off is the same as whether that pattern is 1 or 0.
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline phenomist

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 132
  • Rating: +46/-3
    • View Profile
Re: Non-linear sequence
« Reply #10 on: April 29, 2011, 04:20:44 pm »
@Xeda: Any polynomial interpolation will be bound to lose accuracy pretty quickly, considering that f(x)>2^(x-1) which is exponential.

Progress on creating an explicit formula, I believe, can be done the following way:
1) Create a recursive CA110 step function. For example CAstep110(1) = 3, CAstep110(3)=7, etc.
2) Find an explicit formula for this, using characteristic polynomials.
3) Recursively apply the explicit formula to 1, to generate this.

So far, for step 1, I have the following:
CAstep110(2n) = 2CAstep110(n)
CAstep110(4n+1) = CAstep110(4n)+3 = 4CAstep110(n)+3
CAstep110(8n+3) = CAstep110(8n+2)+1 = 2CAstep110(4n+1)+1 = 8CAstep110(n)+7
CAstep110(8n+7) = CAstep110(8n+6)-1 = 2CAstep110(4n+3)-1

The fourth equation is the problematic one.
Logged
Level Designer for Graviter

[Disclaimer: I can't program for my life.]

Offline AngelFish

  • Is this my custom title?
  • Administrator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 3242
  • Rating: +270/-27
  • I'm a Fishbot
    • View Profile
Re: Non-linear sequence
« Reply #11 on: April 29, 2011, 05:48:02 pm »
Phenomist, the rules of a CA are difficult to operate on like that. For example, 2CA110(n)=/=CA110(2*1) for n=1. However, 3CA110(n)=CA110(2) for n=1, although it fails for n=2 and above. So, right from the start, your derivation is flawed. To fix it also presupposes the very question that I was asking ;)
Logged
∂²Ψ    -(2m(V(x)-E)Ψ
---  = -------------
∂x²        ℏ²Ψ

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Non-linear sequence
« Reply #12 on: April 29, 2011, 10:58:24 pm »
Quote from: phenomist on April 29, 2011, 04:20:44 pm
@Xeda: Any polynomial interpolation will be bound to lose accuracy pretty quickly, considering that f(x)>2^(x-1) which is exponential.
I know, but he only asked for an equation for that data XD I would have to study more to figure it out to match that sequence :D
Logged

Offline phenomist

  • LV4 Regular (Next: 200)
  • ****
  • Posts: 132
  • Rating: +46/-3
    • View Profile
Re: Non-linear sequence
« Reply #13 on: April 29, 2011, 11:40:26 pm »
Quote from: Qwerty.55 on April 29, 2011, 05:48:02 pm
Phenomist, the rules of a CA are difficult to operate on like that. For example, 2CA110(n)=/=CA110(2*1) for n=1. However, 3CA110(n)=CA110(2) for n=1, although it fails for n=2 and above. So, right from the start, your derivation is flawed. To fix it also presupposes the very question that I was asking ;)

I was describing a different function, namely the CA110step(n).

CA110(n) can be expressed as CA110step(CA110step(...(1)...)) where CA110step( is applied n-1 times.

For example, 2^8 can be seen as 1 with the x=>2x function applied 8 times.

It would be easier to talk about CA110step(x) because we know what each step of CA 110 does. However in the end, the situation of CA110step( (and hence CA110( ) may be the same as Ackermann( and other recursive functions that can't be explicitly defined.
« Last Edit: April 29, 2011, 11:45:18 pm by phenomist »
Logged
Level Designer for Graviter

[Disclaimer: I can't program for my life.]
Pages: [1]   Go Up
« previous next »