20120528
	random pair generation
	pvr(n, b, c) recurrence relation computation
		claim: pvr(n, b, c) satisfies a recurrence relation S_{b,c}(n)
		S_{b, c} can be described by a matrix X
		d = floor(log_b(c)) + 1
		d is the depth of the recursion, X has b^d rows
		w = c(b^d - 1)/(b-1)
		f = floor(m/b^d) = max integer such that fb^d < w
		f is the look back, or borrow, index, X has f+1 columns
		((S_{b,c}(m b^d + i))_{i \in (b-1)b^d} = X (S_{b,c}(m-i))_{i \in f}

20120503
What do I know about S_b(n)?
Generating function


What do I know about S_3(n)?
a_n = (3^n-1)/2+1
b_n = (3^{n+1} - 1)/2
c_n = 3^n - 1
the layers (a_n to b_n) are concatenations of two palindromes,
the first is a concatenation of previous layers and the other is a new one

20120306

    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .
    2   10   11
   12   20   21   22  100  101  102  110  111
  112  120  121  122  200  201  202  210  211  212  220  221  222 1000 1001 1002 1010 1011 1012 1020 1021 1022 1100 1101 1102 1110 1111
 1112 1120 1121 1122 1200 1201 1202 1210 1211 1212 1220 1221 1222 2000 2001 2002 2010 2011 2012 2020 2021 2022 2100 2101 2102 2110 2111 2120 2121 2122 2200 2201 2202 2210 2211 2212 2220 2221 2222xxxx


s(1012) = s(101) = s(10) = s(0) + s(1)

s('81')	= s(10000)
	= s(1000) + s(222)
	= s(100) + s(22) + s(222)
	= s(10) + s(2) + s(22) + s(222)
	= s(1) + s(0) + s(2) + s(2) + s(222)
	= s(1) + s(0) + s(2) + s(2) + s(22)
	= s(1) + s(0) + s(2) + s(2) + s(2)
	= 1 + 1 + 1 + 1 + 1
	= 5

s('759')= s(1001010)
	= s(100101) + s(100100)
	= s(10010) + s(100100)
	= s(1001) + s(1000) + s(100100)
	= s(100) + s(1000) + s(100100)
	= s(10) + s(22) + s(1000) + s(100100)
	= s(1) + s(0) + s(22) + s(1000) + s(100100)
	= s(1) + s(0) + s(2) + s(1000) + s(100100)
	= s(1) + s(0) + s(2) + s(100) + s(22) + s(100100)
	= s(1) + s(0) + s(2) + s(10) + s(2) + s(22) + s(100100)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(22) + s(100100)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(100100)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(10010) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1001) + s(1000) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(100) + s(1000) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(10) + s(2) + s(1000) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1000) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(100) + s(22) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(10) + s(2) + s(22) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(22) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(10002)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1000)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(100) + s(22)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(10) + s(2) + s(22)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(22)
	= s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(1) + s(0) + s(2) + s(2) + s(1) + s(0) + s(2) + s(2)



\begin{comment}
\begin{lem*}
$\pvr(b^k-1, b, b+1) = 1$
\end{lem*}
\begin{proof}
Let $n = b^k - 1$.
Then the $b$-ary representation of $n$ is $s = (b-1)_{i \in k}$.
Since $s$ is the lexicographically greatest representation of $n$
any other representation $s'$ must have a $b-2$ at some index $i_0$.
Thus some other representation, say $s_{n'}$ of $n' = b^{i_0}$
must be added below this index.
In particular $s_{n'}$ must be shorter than $i_0$.
Further if $s'$ is to be in $\pvp(n, b, b+1)$
then $s_{n'}$ must be in $\pvp(n', b, b)$,
that is, it must be a $b$-ary representation of $n'$
because each index lower than $i_0$ already has a value of at least $1$.
But $b^{i_0}$ has a unique $b$-ary representation,
which has length $i_0$,
and there is no shorter $b$-ary representation of $n'$.
Thus $n$ has exactly one representation in $\pvp(n, b, b+1)$.
Consequently for $n = b^k - 1$ it is the case that
\[
S_b(n) = \pvr(n, b, b+1) = |\pvp(n, b, b+1)| = 1.
\]
\end{proof}
\end{comment}