10,818 Pages

## 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)$$