Conjecture 1. 761 is the largest integer which is not a pseudo-Fibonacci.

Conjecture 2. The largest integer not contained in the right tree is 922.

Conjecture 3. The product of any two derivable numbers is derivable.

Guess: It is quicker to multiply using pseudo-Fibonacci encodings.

Rationale:

I think algorithms exist multiplying two k digit numbers in O(k^. logk^. log(log k)) steps. (Grade-school algorithm is O(k²).)

derivation of number N is of length logqN where 1.4656=q=1.618 and

by Corollary 3.4, any two numbers in the right tree n=pF(0001a) and m=pF(0001b) can be multiplied by string reversal, followed by string concatenation:

n=pF(0001a)=pF(000aR1) and

nm=pF(000aR10001b).

Reversing a string of length k takes O(k) steps; concatenation is also O(k).

by conjecture 2 all but a few numbers are so expressable, hence to multiply two numbers (given their expressions) takes O(k) steps.

So if we can find the expression quickly, then we can multiply quickly.

To find an expression of N involves (in the worst case) exploring all branches of the tree. N is at depth k=logqN in the tree (for 1.465<q<1.618). There are 2^k-3 leaves at that depth, each requiring k steps to articulate.

It follows then that "blind-exploration" takes O(N1.8logN) steps to find a pseudo-Fibonacci expression of N.

prime-factorization

By conjecture 2, most nonprimes, N, will have 2 factors p=pF(000a1) and q=pF(0001b) in the right-tree. If they do, then N=pF(000a10001b). Once we know that the expression of N contains the string 10001, then we may de-concatenate to factor N. If were possible to find this expression in O(k) time, then we would easily check each to see if it contains the string 10001. Thence, prime factorizing numbers could be done in O(logN)=O(k) time.

exponentiation of integers:

Once an integer has been found in the right tree, we may exponentiate its socks off:

N = pF(0001a)=pF(000a^R1)

N² = pF(000a^R1000a^R1)

N³= pF(000a^R1000a^R1000a^R1)

Various numbering schemes for natural numbers

Examples Base 10

B10 (Arabic, Base 10) - 162 = 1 x 100 + 6 x 10 + 2 =162

S={0,1,2,3,4,5,6,7,8,9} , L={strings in S* not beginning with 0}

R (Roman) - MCMXCIX = Meg + (Meg-Cent) + (Cent-Dec) +(Dec-Uno) = 1999

S={I,V,X,L,C,D,M, _} , L is difficult to describe in one line.

U (Unary) - I I I I I I I I I I I I I I I I I I I I I I I = 23

S={I} , L=S*

P (Prime Decomposition) - assign each prime (p) its ordinal rank (written base 10), 2=p1, 3=p2, 5=p3, 7=p4, 11=p5, ... , 109=p29, etc. ;

encode each integer by its prime factorization, listing primes which occur by increment in ordinal rank and associated exponent.

S={0,1,2,3,4,5,6,7,8,9,.,;} , L= { i,j;} for i,j in Z+

Nice properties:

Extendable: no largest natural number. For all N in Z+ there should be an encoding (unlike Roman )

Space conserving (Base 10)

Method for counting arbitrarily high - Base k

Extendable - integers, rationals, reals, etc. - Base k

Cognitive, calculational, computational ease and speed ... [XIX times XXI = 400-1]

Successor - Unary

Ordinal comparison

Addition

Multiplication

Exponentiation

Prime Factorization