Sequência de Kolakoski

Notas sobre a sequência de Kolakoski

A sucessão de Kolakoski¹ é definida por:

Um algoritmo simples é o seguinte (em ² 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))

> (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/Octave

Criado/Created: NaN

Última actualização/Last updated: 10-10-2022 [14:26]

Voltar à página inicial.