Sequência de Kolakoski
A sucessão de Kolakoski1 é definida por:
Um algoritmo simples é o seguinte (em 2 está a versão em GNU/Octave):
a=[1 2 2] i=3:n j=1:a(i) a=[a 1+mod(i-1,2)]
o que dá
1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 - --- --- - - --- - --- --- - (...) 1 2 2 1 1 2 1 2 2 1
O algoritmo anterior está definido de uma forma imperativa e tem uma tradução para LISP com forma
(defun kolakoski. (n) "Kolakoski sequence." (let ((a '(1 2 2))) (do ((i 2 (+ i 1))) ((= i n)) (do ((j 1 (+ j 1))) ((= j (+ 1 (car (nthcdr i a))))) (setq a (concatenate 'list a (list (+ 1 (mod i 2))))))) a))
Vejamos então como construir uma forma funcional para gerar a sequência. A ideia
é obter o valor de m
(ver figura acima) definido como o mínimo, fixado um n
, de
todas as somas maiores ou iguais a n
o valor do n-ésimo termo da sucessão é
então dado por
((lambda (x) (/ (+ 3 (expt -1 x)) 2)) 'm)
. Antes de construirmos essa função precisamos de algumas funções auxiliares
(defun sum (x) "Sum of elements of X." (cond (x (+ (car x) (sum (cdr x)))) (t 0))) (defun lin-seq (n) "Retuns (1 2 3 ... n)." (cond ((= n 1) (list 1)) (t (append (lin-seq (- n 1)) (list n))))) (defun nest (op xo n) "Applies OP to XO N times." (cond ((= n 1) xo) (t (nest op (funcall op xo) (- n 1))))) (defun partial-sum (lst) "Partial sums of LST." (reverse (maplist #'sum (reverse lst))))
Vejamos então como funciona a função find-m
definida por
(defun find-m (lst n) (+ 1 (length (mapcan #'(lambda (y) (and y (list y))) (mapcar #'(lambda (x) (<= x n)) (partial-sum lst))))))É composta de duas partes: dada uma lista
lst
, a primeira, verifica se a
condição <=n x
é t
ou nil
, por exemplo, dada uma lista (1 2 3 4)
com
somas parciais (1 3 6 10)
a aplicação da condição (<
x 3)=, onde x
é o
valor de cada entrada da lista, dá
> (mapcar #'(lambda (x) (<= x 3)) (partial-sum '(1 2 3 4)))
(t t nil nil)
A segunda parte da função remove as entradas nil
através de
> (mapcan #'(lambda (y) (and y (list y))) '(t t nil nil))
(t t)
e, logo, o valor de m
é o comprimento desta última lista mais um.
De seguida verifica-se se está tudo bem calculando o valor dos sucessivos m
> (mapcar #'(lambda (x) (find-m (kolakoski. 20) x))
'(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))
(1 2 2 3 3 4 5 6 6 7 8 8 9 9 10 11 11 12 12 13 14)
e desfaz-se a transformação de modo a obter a sequência original
> (kolakoski. 20) (1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1 1 2 1 2 2 1 1 2)através de
> (mapcar #'(lambda (x) (/ (+ 3 (expt -1 x)) 2)) (mapcar #'(lambda (x) (find-m (kolakoski. 20) x)) '(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))) (1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2)
A construção da sequência de Kolakoski vem então definida por
(defun kolakoski (seq) (append seq (list (/ (+ 3 (expt -1 (find-m seq (length seq) ))) 2))))Exemplificando
(kolakoski '(1 2 2))e
> (nest 'kolakoski '(1 2 2) 20) (1 2 2 1 1 2 1 2 2 1 2 2 1 1 2 1 1 2 2 1 2 1)
1. The American Mathematical Monthly, Vol. 72, No. 6 (Jun. - Jul., 1965), pp. 673-67
function retval = kolakoski (n) retval=[1 2 2]; for i=3:n for j=1:retval(i) retval=[retval 1+mod((i-1),2)]; endfor; endfor; endfunction;
3. O número de termos não está correcto, a sequência final tem 22 termos e não 20, isto resolve-se com a indexação correcta de cada termo (índice que indexa as entradas de cada lista começa em 0).
Palavras chave/keywords: Kolakoski, Lisp, matemática, self-generating, GNU/OctaveCriado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:26]
(c) Tiago Charters de Azevedo