Introducing myself.

[Antti Karttunen]

Chers Messieurs/Dear Sirs:
 
 
Maybe it's now time to introduce myself:
 
I'm about thirty years old, a father of one year
old son, and a first-year student of the Mathematics
at the University of Helsinki, having before this,
without better knowledge, wasted my youth mainly
with the programming, which is still my civil profession.

Of all the sequences of which I have submitted to Neil's
Encyclopedia, it's the first two ones that actually count anything,
which must be the reason they are about only ones which
have merited the keyword "nice" from Neil.
They are:
 
A033538 1,1,5,17,57,189,625,2065,6821,22529,74409,245757,811681,...
which counts the recursion steps of the Lisp function:
(defun reverse* (lista)
   (cond ((null (cdr lista)) lista)
          (t (cons (car (reverse* (cdr lista)))
                (reverse* (cons (car lista)
                             (reverse* (cdr (reverse* (cdr lista))))))))))
with a list of length n, and
A033539 1,1,1,4,10,25,61,148,358,865,2089,5044,12178,29401,70981,171364,413710
which counts the recursion steps for the Forth word defined in
equally tortuitous manner. The recursive formulas for these,
a(0)=1, a(1)=1, a(n)=3*a(n-1)+a(n-2)+1
and a(0)=1, a(1)=1, a(2)=1, a(n)=2*a(n-1)+a(n-2)+1 follow trivially
from the corresponding Lisp and Forth functions.
 
Most of my other sequences are based on binary expansion of N,
which must be because of too long exposure to Assembly and
C-programing, as well as being inspired by HAKMEM,
MIT's Artificial Intelligence Laboratory's Memo No. 239,
from February 29, 1972, which can be seen at:
http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html
 
For example A036213 and A036214 which originate from
HAKMEM, ITEM 167 (Schroeppel) and Thue-Morse sequence
related A048707/8 straight from HAKMEM, ITEM 122 (Schroeppel, Gosper).
 
Many of the sequences and arrays I have submitted are based on
interpreting the binary expansion of n as a polynomial in 
the ring of GF(2)[X], (i.e. decimal 11 = 1011 in binary stands for
the polynomial x^3+x^2+1), and adding and multiplying these
according to the rules of GF(2)[X], i.e. simply using
the assembly-language operation XOR instead of ADD in a standard
binary "blackboard multiplication" algorithm.
 
This gives us a lots of "X-sequences" like
 
A048631 1,1,2,6,24,120,272,1904,15232,124800,848640,7507200,39738368,433441792,...
which is "Xfactorials - like factorials but use carryless GF(2)[X] polynomial
multiplication" in a formula  a(0) = 1, a(n) = n X a(n-1),
 
as well as A048720, a multiplication table (0..i) X (0..j) of
such polynomials, and all the related tables and sequences,
such as its row/column 3 = A048724 ("nX2 + n") which incidentally,
is the bisection of Gray Code (A003188), Gray Code expansion
of binary encoding "n" being conceptually just n+floor(n/2) computed
in GF(2)[X], i.e. (n XOR (n SHR 1)).
 
The method also gives the corresponding "X-power" table A048723,
and its rows A001317 (Pascal's triangle mod 2 converted to decimal),
A038183 (a history of one-dimensional cellular automata "rule 90"
starting from the seed pattern 1), and similarly, A038184, 1-D CA,
"rule 150". The two former sequences, which thus correspond to
taking nth power of of polynomials x^1+x^0 (binary 11 = 3),
and x^2+x^0 (binary 101 = 5 = "3^2") have also an interesting
expansion as products of distinct Fermat Numbers.
 
Furthermore, pondering about such sequences leads one naturally to
Zeckendorf-expansions like "fibbinary" numbers:
A003714 0,1,2,4,5,8,9,10,16,17,18,20,21,32,33,34,36,37,40,41,42,64,...
which means a Zeckendorf-expansion of n (an unique way of
expressing n as a sum of distinct fibonacci numbers) interpreted
as a binary number; and to other such sequences, but using recurrences
like f(n) = f(n-1) + f(n-3) or f(n) = f(n-1) + f(n-4) instead
of the fibonacci recurrence, to produce A048715 and A048718.
Thus the binary expansions of these three sequences has the property
that the 1-bits are separated from each other at least by one,
two or three 0-bits respectively, and it's trivial to see that
these sequences give all the solutions to particular
"pattern equations" like "All n for which 3*n = 3Xn", i.e.
when there are no carries produced <=> no 1-bits in common
locations of the subsummands.
Just a little bit harder is to see that
A048717 0,3,6,7,12,14,15,24,28,30,31,48,51,56,60,62,63,96,99,102,...
(where binary expansion matches ((0)*00(1*)11)*(0*))
gives all the solutions to the equation "7Xn = 3*n".
 
 
Lately I have been collecting permutations of integers, i.e.
sequences where all n from 0 or 1 upward occur, but only once.
Of the existing sequences Gray Code A003188 itself is a good
example (and why not apply the transformation (n XOR [n/2])
twice or thrice to get Gray² Code and Gray³ Code respectively?
and Gray^-1 Code would then be good name for the inverse mapping).
 
For example, from the sequence
A045965 2,3,5,9,7,15,11,27,25,21,13,45,17,33,35,81,19,75,23,63,55,...
produced by replacing all the primes in the factorization of n
with the next prime. (A nice sequence entered by njas and
Marc Le Brun, but what was the original puzzle proposed?)
one gets a permutation of N by adding one and dividing by 2:
A048673 1,2,3,5,4,8,6,14,13,11,7,23,9,17,18,41,10,38,12,32,28,...
whose "invariant sequence" is then
A048674 1,2,3,25,26,33,93,1034,970225
(Those A048673 for which A048673[n] = n.)
 
And lastly, back to Zeckendorf-expansions, because by compressing
the fibbinary numbers mentioned above (A003714) with a simple
rewrite rule 0->0, 01->1, we get "compressed fibbinary numbers"
A048679 0,1,2,4,3,8,5,6,16,9,10,12,7,32,17,18,20,11,24,13,14,64,33,...
which is yet another permutation of non-negative integers,
like its inverse mapping
A048680 0,1,2,4,3,6,7,12,5,9,10,17,11,19,20,33,8,14,15,25,16,27,28,...
which is produced by a reverse process.
One could similarly compress A048715 and A048718 with rewrite
rules (0->0, 001->1 and 0->0, 0001->1 respectively) to get further
permutations.
 
I have been collecting cross-references to such permutations
to "See also" fields of A001477 (The non-negative integers)
and A000027 (The natural numbers).
 
 
 
Yours,
 
Antti Karttunen
E-mail: Antti.Karttunen at iki.fi (permanent, forwarded to karttu at megabaud.fi)
 
PS. Je peut aussi lirer la Francaise, pas de problem, mais la ecriture,
c'est plus dificile...