[SeqFan]: Repeated iterations of INVERT starting from A019590 ?

[Joshua Zucker]

Hi all,
here are the answers to Antti's questions.  See source code below.
--Joshua Zucker



> I.e. INVERT(A019590) produces Fibonacci numbers beginning from A000045(2),
> and when we apply INVERT(RIGHT(...)) to them, i.e.
> INVERT([1,1,2,3,5,8,13,21,34,55,89,...])
> we get Pell numbers, A000129
> 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741,

OK, I verify this conclusion.

> and again, prepending one, and taking INVERT:
> INVERT([1, 1, 2, 5, 12, 29, 70, 169, 408, 985, 2378, 5741, ...]
> produces what?

I get 1 2 5 14 40 115 331 953 2744 7901 22750

> Could somebody compute that, and continue few iterations more?
OK, here goes:
1 2 5 14 42 130 408 1288 4076 12912 40920 ...
1 2 5 14 42 132 427 1405 4668 15593 52242 ...
1 2 5 14 42 132 429 1428 4833 16542 57042 ...
1 2 5 14 42 132 429 1430 4860 16763 58464 ...
1 2 5 14 42 132 429 1430 4862 16794 58749 ...
1 2 5 14 42 132 429 1430 4862 16796 58784 ...
1 2 5 14 42 132 429 1430 4862 16796 58786 ...

Looks like there are some other interesting patterns: just before
becoming the catalans, 2 is added on the last step.  On the step
before that, what's added looks like
11, 15, 19, 23, 27, 31, 35, ...
so there may be an interesting formula as a sum of easy things that
add up to Catalans in there?  I didn't look too closely at the step
before that 4n+3 step.

As for the conjecture, that "almost any" sequence converges to
Catalan, it sure looks plausible to me from my experiments!  In fact I
think I see an easy proof, that the prepending of the 1 always
guarantees that after n iterations, the first n terms will be the
Catalans.  Effectively you are "pushing" the old sequence farther and
farther down.  Either that, or I'm making some mistake about the
offset, and there is supposed to be some compensating deletion of
initial terms at some point in this process?

--Joshua Zucker


PS: Hi Antti,
here's some code that runs in PLT Dr. Scheme "Pretty Big" language
level.  I'm happy to explain what the code's supposed to do if you're
curious.

To run it:
Download the PLT Scheme engine from http://www.drscheme.org/
Install, and start it up
choose the "Pretty Big" language level
Copy the stuff below into the top window
click run
Then, for example, type
(invert #(1 1) 25)
at the > prompt at the bottom, and you get
(vector 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181
6765 10946 17711 28657 46368 75025 121393)
(the #(1 1) is the sequence, with all terms not given being assumed 0,
and the 25 is the number of terms you want it to compute).

At the end there's some code that automatically prepends 1 and inverts.
To generate the answers above, I ran it like this:
(define s #(1))
(define s (prepend-1-and-invert s 25) s
where the extra s on the end of the line displays the answer.
Then I repeatedly ran that last line to keep iterating the
prepend-and-invert process.

--Joshua Zucker


(define (invert seq nterms)
  (local ((define len (vector-length seq))
          (define (my-vector-ref v n)
            (cond
              [(or (<= n 0) (> n len)) 0]
              [else (vector-ref v (sub1 n))]))

          (define ht (make-hash-table 'equal))
          (define (invert-help n)
            (hash-table-get ht n (lambda () (let ((answer (invert-calc n)))
                                              (begin (hash-table-put!
ht n answer)
                                                     answer)))))
          (define (invert-calc n)
            (cond
              [(< n 0) 0]
              [(= n 0) 1]
              [else (apply + (build-list n (lambda (k) (*
(my-vector-ref seq (add1 k)) (invert-help (- n (add1 k)))))))]))
            )
    (list->vector (build-list nterms (lambda (nminus1) (let ((n (add1 nminus1)))
                                           (invert-help n)))))))


(define (prepend-1-and-invert seq nterms)
  (invert (build-vector (add1 (vector-length seq))
                        (lambda (k) (cond [(= k 0) 1]
                                          [else (vector-ref seq (sub1 k))])))
          nterms))