FANDOM


Valid Sequence Counts

In my blog on Program Code Version 4 (using Sequence Generator code) there is a reference to the number of Valid Sequences that can be generated by the Sequence Generating code. This blog will estimate the number and the growth rate of these numbers.


Sequence Generating Code

Here is a summary of the sequence generating code taken from the Version 4 blog:

\(g(q) = (q(0:a,q(1:,m_0(q)),T,g_E(q),g_C(q),g_a(q)))\)

\(m(q) = (p,R,g_F(q),g_{[q]}(q),n_0(q))\)

\(n(q) = (Q(0:,g_{[Q]}(Q),S,n_1(Q)))\)


Valid Sequence Count for \(g(0) = (q,a) = (o,a)\)

This sequence is limited to the finite integers allowed for \(a\). Lets define the function:

\(C(n) =\) the count of valid sequences that only use integers from 0 to n, then:

\(C(0) = 1\) because \((0,0)\) is the only valid sequence.

We can then calculate an interim count for any sequences of the form \((o,a)\) as:

\(C(n)\) for \((0,a) = C(n,(0,a)) = n + 1 = f_0(n)\) are the only valid sequences.


Valid Sequence Count for \(g(1) = (1,T,g_E,g_C,g_a)\)

Some useful results that will be used are as follows:

\(C(n,(1,T)) = n + 1 + C(n,(0,a)) = 2.(n + 1) = 2.f_0(n)\)

\(C(n,(1,T,g_E)) = E_0^{f_0(n)}(f_0(n)) = E_0^n(f_0(n)) + E_0^e(f_0(n))\) where \(e=0\) if \(n<2\) else \(e=1\)

\(C(n,(1,T,g_E,g_C)) = C_0^{f_0(n)}(f_0(n)) = C_0^n(f_0(n)).(C_0(f_0(n)) + 1)\)

and with one special case: \(C_0(f_0(n)) = f_0(n).(f_0(n) + 1)\)

\(C(n,(1,T,g_E,g_C,g_a)) = a_0^{f_0(n)}(f_0(n)) = a_0^n(f_0(n)).(a_0^n(f_0(n)) + 1)^{a_0(f_0(n))}\)

and with one special case: \(a_0(f_0(n)) = f_0(n).(f_0(n) + 1)^{f_0(n)}\)

Therefore some calculations are:

\(C(1,(1,T,g_E,g_C,g_a)) = a_0^{f_0(1)}(f_0(1)) = a_0(2).(a_0(2) + 1)^{a_0(2)} = 18.(18 + 1)^{18}\) because

\(a_0(2) = 2.(2 + 1)^2 = 2.(3)^2 = 18\)

\(C(2,(1,T,g_E,g_C,g_a)) = a_0^{f_0(2)}(f_0(2)) = a_0^2(3).(a_0^2(3) + 1)^{a_0(3)} = X.(X + 1)^X\) when

\(X = a_0^2(3) = a_0(3).(a_0(3) + 1)^{a_0(3)} = 192.(192 + 1)^{192}\) when

\(a_0(3) = 3.(3 + 1)^3 = 3.4^3 = 3.64 = 192\)

Alternatively:

\(C(1,(1,T,g_E,g_C,g_a)) = a_0^{f_0(1)}(f_0(1)) = a_1(f_0(1))\)

\(C(2,(1,T,g_E,g_C,g_a)) = a_0^{f_0(2)}(f_0(2)) = a_1(f_0(2))\) and

\(C(n,(1,T,g_E,g_C,g_a)) = a_0^{f_0(n)}(f_0(n)) = a_1(f_0(n))\)

And using slightly simpler notation to represent all valid sequences which begin with \((1)\):

\(C(n,(1)) = C(n,(1,T,g_E,g_C,g_a)) = a_0^{f_0(n)}(f_0(n)) = a_1(f_0(n))\)


Valid Sequence Count for \(g(2) = (2,m_0,T,g_E,g_C,g_a)\)

Continuing for \(q = 2\), we can count the number of valid \(m\) and \(n\) sequences, beginning with:

\(m(2) = (p,R,g_F,g_{[2]},n_0(2))\)

\(C(2,(2,0,0,(0,0),(0,0),0,T)) = a_0^{f_0(2)}(a_1(f_0(2))) = a_0^3(a_1(3))\)

\(C(2,(2,0,0,(0,0),(0,1),0,T)) = a_0^{f_0(2).2}(a_1(f_0(2))) = a_0^6(a_1(3))\)

\(C(2,(2,0,0,(0,0),(1,T),0,T)) = a_0^{f_0(2).a_1(f_0(2))}(a_1(f_0(2))) = a_0^3(a_1^2(3))\)

or

\(C(2,(2,0,0,(0,0)) = C(2,(2,0,0,(0,0),(1,T),0,T)\)

\(= a_0^{f_0(2).a_1(f_0(2))}(a_1(f_0(2))) = a_0^{C(2,(0)).C(2,(1))}(C(2,(1))\)

and

\(C(n,(2,0,0,(0,0)) = a_0^{C(n,(0)).C(n,(1))}(C(n,(1)) = a_0^{(n + 1).C(n,(1))}(C(n,(1)) = a_0^{n.C(n,(1))}(a_1(C(n,(1)))\)

\(>> a_1(C(n,(1))\)

then

\(C(2,(2,0,0,(0,1),(0,0),0,T)) = a_0^{f_0(2)}(a_0^3(a_1^2(3))) = a_0^6(a_1^2(3))\) and using

\(n(2) = (Q(0:,g_{[Q]},S,n_1(Q)))\)

\(C(2,(2,0,0,(0,1),(0,0),(1,(0,0),0,0),T)) = a_0^{f_0(2).2}(a_0^3(a_1^2(3))) = a_0^9(a_1^2(3))\)

\(C(2,(2,0,0,(0,1),(0,0),(1,(0,0),1,0),T)) = a_0^{f_0(2).3}(a_0^3(a_1^2(3))) = a_0^{12}(a_1^2(3))\)

\(C(2,(2,0,0,(0,1),(0,0),(1,(0,0),2,0),T)) = a_0^{f_0(2).4}(a_0^3(a_1^2(3))) = a_0^{15}(a_1^2(3))\)

Without proof, the general rule for counting sequences of \(n_0\) is \(C(n,(n_0)) = 4^{C(n,(g_1))}\) i.e. the count of \(g_1\) from the \(m_0\) sequence.

so

\(C(2,(2,0,0,(0,1),(0,0))) = a_0^{3.4^1 + 3}(a_1^2(3))\)

or

\(C(2,(2,0,0,(0,1),(0,0))) >> a_0^{C(2,(0)).4^1}(a_1(C(2,(1)))\)

and

\(C(2,(2,0,0,(0,1),(0,1))) >> a_0^{C(2,(0)).4^1.2}(a_1(C(2,(1)))\)

then

\(C(2,(2,0,0,(0,1))) >> a_0^{C(2,(0)).4^1.C(2,(1))}(a_1(C(2,(1))) >> a_1^2(C(2,(1)))\)

then

\(C(2,(2,0,0,(0,2))) >> a_1^3(C(2,(1)))\)

\(C(2,(2,0,0)) >> a_1^{C(2,(1)) + 1}(C(2,(1)))) >> a_2(C(2,(1)))\)

then

\(C(2,(2,0,1)) >> a_1^{C(2,(2,0,0)) + 1}(C(2,(2,0,0)))) >> a_2^2(C(2,(1)))\)

\(C(2,(2,0,2)) >> a_1^{C(2,(2,0,1)) + 1}(C(2,(2,0,1)))) >> a_2^{C(2,(0))}(C(2,(1)))\)

\(C(2,(2,1,0)) >> a_1^{C(2,(2,0,2)) + 1}(C(2,(2,0,2)))) >> a_2^{C(2,(0)) + 1}(C(2,(1)))\)

\(C(2,(2,1,1)) >> a_1^{C(2,(2,1,0)) + 1}(C(2,(2,1,0)))) >> a_2^{C(2,(0)) + 2}(C(2,(1)))\)

\(C(2,(2)) = C(2,(2,1,2)) >> a_1^{C(2,(2,1,1)) + 1}(C(2,(2,1,1)))) >> a_2^{C(2,(0)).2}(C(2,(1)))\)

or

\(C(n,(2)) >> a_2^{C(n,(0)).2}(C(n,(1)))\)


Valid Sequence Count for \(g(3) = (3,m_0,T,g_E,g_C,g_a)\)

Using similar calculations as above and starting with:

\(C(3,(2)) >> a_2^{C(3,(0).2}(C(3,(1)))\)

\(C(3,(3,0,0,(0,0),(0,0),(0,0))) >> a_0^{f_0(3)}(a_2^{C(3,(0).2}(C(3,(1))))\)

\(C(3,(3,0,0,(0,0),(0,0),(0,1))) >> a_0^{f_0(3).2}(a_2^{C(3,(0).2}(C(3,(1))))\)

\(C(3,(3,0,0,(0,0),(0,0))) >> a_0^{f_0(3).a_2^{C(n,(0)).2}(C(n,(1)))}(a_2^{C(3,(0).2}(C(3,(1))))\)

or

\(C(3,(3,0,0,(0,0),(0,0))) >> a_1(a_2^{C(3,(0).2}(C(3,(1))))\)

and

\(C(n,(3,0,0,(0,0),(0,0))) >> a_1(a_2^{C(n,(0).2}(C(n,(1))))\)

then

\(C(3,(3,0,0,(0,0),(0,1))) >> a_1^2(a_2^{C(3,(0).2}(C(3,(1))))\)

and

\(C(3,(3,0,0,(0,0))) >> a_1^{C(3,(2)) + 1}(a_2^{C(3,(0).2}(C(3,(1)))) >> a_2^{C(3,(0).2 + 1}(C(3,(1)))\)

\(C(3,(3,0,0,(0,1))) >> a_1^{C(3,(2,0,0,(0,0))) + 1}(C(3,(2,0,0,(0,0))))) >> a_2^{C(3,(0).2 + 2}(C(3,(1)))\)

then

\(C(3,(3,0,0)) >> a_2^{C(3,(0).2 + C(3,(1))}(C(3,(1))) >> a_3(C(3,(1)))\)

\(C(3,(3,0,1)) >> a_2^{C(3,(3,0,0)) + 1}(C(3,(3,0,0)))) >> a_3^2(C(3,(1)))\)

\(C(3,(3,2,2)) >> a_3^(C(3,(0) + 3)(C(3,(1)))\)

\(C(3,(3)) >> a_3^(C(3,(0).2)(C(3,(1)))\)

or

\(C(n,(3)) >> a_3^(C(3,(0).2)(C(3,(1)))\)


Growth Rate of Sequence Counts for \(g(n) = (n,m_0,T,g_E,g_C,g_a)\)

Without proof the general formula is proposed as follows:

\(C(n,(p)) >> a_p^{C(p,(0).2}(C(p,(1)))\)

so

\(C(n) = C(n,(n)) >> a_n^{C(n,(0).2}(C(n,(1))) >> a_{\omega}^{C(n,(0).2}(C(n,(1)))\)

and without proof the growth rate of these sequences are estimates to be:

\(f_{\omega}(n) << C(n) << f_{\omega + 1}(n)\)

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.