[seqfan] Elementary Binary Combinatory Sequences

[Brad Klee]

Hi Seqfans,

Here are a few easy sequences obtained by recursive combination of free
function F[].

We start with the natural numbers including zero, N, and define Bin[n] w/ n
in N, as the ordered list of binary digits of n. For each b in Bin[N],
define a composition of F by reading the digits, d in b, starting with the
most significant:

Axiom : F[]

if d = 0
  G[ x ] ---> G'[ x' ]=G[ x, F[] ]
elseif d = 1
  G[ x ] ---> G'[ x' ]=F[ G[ x ] ]
iterate through d

Or we can make the other choice "If d= 1...". This defines two functions
Comb[Bin[n]] . The first few terms are:

n: 0, 1, 2, 3, 4, 5, 6 ,7...
Comb[Bin[N],0] := F[], F[F[]], F[F[], F[]], F[F[F[]]], F[F[], F[], F[]],
F[F[F[], F[]]], F[F[F[]], F[]], F[F[F[F[]]]] . . .
Comb[Bin[N],1] := F[], F[F[]], F[F[F[]]], F[F[], F[]], F[F[F[F[]]]],
F[F[F[]], F[]], F[F[F[], F[]]], F[F[], F[], F[]] . . .

Notice that every block of 2^n is a permutation between sequences. This is
easy to prove following the fact that when G[x] = F[], G'[x'] = F[F[]]
regardless of d or the bit choice, then every b has a unique
parity-reflected image.  For example 1uvw <---> 1xyz, where u !=x, v !=y, w
!=z. This is a nice property for relating any sequences we can find in the
OEIS.

Now, for the fun part. You are free to assume whatever unique, arithmetical
definition for F, based on the number of arguments (to make function
evaluation non-ambiguous). For example, the most simple addition function:

0 arg: F[] = 1
1 arg: F[x] = x
>1 arg: F[x,y,...] = x+y+....

Yields the following sequences:

1, 1, 2, 1, 3, 2, 2, 1, 4, 3, 3, 2, 3, 2, 2, 1 . . .
1, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 . . .

If term matching is reliable beyond n=50, then as a corollary to the
theorem above: A008687 and A106487 are related by a permutation of values.

Other Functions.

1. Increment & Add.
0 arg: F[] = 0
1 arg: F[x] = x+1
>1 arg: F[x,y,...] = x+y+....

0, 1, 0, 2, 0, 1, 1, 3, 0, 1, 0, 2, 1, 2, 2, 4, 0, 1, 0, 2, 0, 1, 1, 3, 1,
2, 1, 3, 2, 3, 3, 5 . . .
0, 1, 2, 0, 3, 1, 1, 0, 4, 2, 2, 1, 2, 0, 1, 0, 5, 3, 3, 2, 3, 1, 2, 1, 3,
1, 1, 0, 2, 0, 1, 0 . . .

2. Subtract & Add
0 arg: F[] = 1
1 arg: F[x] = x
2 arg: F[x,y] = x-y
>2 arg: F[x,y,z,...] = x+y+z+....

1, 1, 0, 1, 3, 0, 0, 1, 4, 3, -1, 0, 3, 0, 0, 1, 5, 4, 2, 3, 2, -1, -1, 0,
4, 3, -1, 0, 3, 0, 0, 1 . . .
1, 1, 1, 0, 1, 0, 0, 3, 1, 0, 0, 3, 0, -1, 3, 4, 1, 0, 0, 3, 0, -1, 3, 4,
0, -1, -1, 2, 3, 2, 4, 5 . . .

3. Divide & Add
0 arg: F[] = 1
1 arg: F[x] = x
2 arg: F[x,y] = x / y
>2 arg: F[x,y,z,...] = x+y+z+....

1, 1, 1, 1, 3, 1, 1, 1, 4, 3, 1, 1, 3, 1, 1, 1, 5, 4, 3, 3, 3, 1, 1, 1, 4,
3, 1, 1, 3, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 1, 1, 3, 4, 1, 1, 1, 3, 1, 1, 3, 4, 1,
1, 1, 3, 3, 3, 4, 5

I don't think any of these other six sequences are in the OEIS.

Maybe the domain function could be improved by doing prepend and append,
but this introduces ambiguity because we will then encounter situations
such as F[F[]]  where append and prepend both give F[ F[] , F[] ].

Mma Code: http://ptpb.pw/Irmy .

Happy Holidays,

Brad