Suite de Conway

Générer la suite de Conway avec des langages de programmation

La fonction conway() représentant la suite de Conway

Avec le PHP

 <?php
 $a1 = array('1', '2', '3');
 $a2 = array('a', 'b', 'c');
 $b1 = array('bbb', 'aaa', 'cc', 'bb', 'aa', 'c', 'b', 'a');
 $b2 = array('32', '31', '23', '22', '21', '13', '12', '11');
 
 function conway($n, $str = '1', $i = 0) {
     // $n : la ligne de la suite de conway à afficher
     // $i est passé en paramètre lors de la récursivité (appel à la fonction même)
     // On rend globales les variables $a1, $a2, $b1 et $b2, pour ne pas avoir à les définir à chaque fois.
     global $a1, $a2, $b1, $b2;
     if($i < $n) {
         return conway($n, str_replace($b1, $b2, str_replace($a1, $a2, $str)), ++$i);
     }
     else {
         return $str;
     }
 }
 echo conway(3, $str = '1', $i = 0); 
 // Execution : cela affichera 3 lignes de la suite 
?>

En C

Voici un programme écrit en C qui affiche les n premiers termes de la suite de Conway, n étant passé en ligne de commande :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main(int argc, char **argv)
{
        const int nb_terms = argc > 1 ? atoi(argv[1]) : 10;
        int max_length = 1024;
        char *s1 = malloc(max_length), *s2 = malloc(max_length);
        strcpy(s1, "1");
        for (int i = 0; i < nb_terms; ++i) {
                puts(s1);
                if (strlen(s1) > max_length / 2) {
                        max_length *= 2;
                        s1 = realloc(s1, max_length);
                        free(s2); s2 = malloc(max_length);
                }
                s2[0] = 0;
                char *start = s1;
                do {
                        char *stop = start + 1;
                        while (*stop == *start) ++stop;
                        sprintf(s2, "%s%td%c", s2, stop - start, *start);
                        start = stop;
                } while (*start);
                strcpy(s1, s2);
        }
        free(s1); free(s2);
        return 0;
}

En Haskell

  import Data.List
 
  conway = iterate step [1] where
    step l = [f x | x <- group l, f <- [length,head] ]
 
  main = print . take 10 $ conway

En Perl5

    for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }

ou depuis le shell:

    perl -E 'for ( $_=1;; ) { say; s/((.)\2*)/length($1).$2/xeg; }'

En Python

import itertools
 
def conway():
    x = '1'
    while True:
        yield x
        nx = ''
        for item, grouper in itertools.groupby(x):
            nx += '%d%s' % (len(list(grouper)), item)
        x = nx
 
suite = conway()
for i in range(10):
    print suite.next()

En Prolog

  conway(0,[1]).
  conway(N,R):- N>0, M is N-1, conway(M,L), conwayLigneSuivante(L,R).
 
  conwayLigneSuivante([],[]).
  conwayLigneSuivante([E],[1,E]).
  conwayLigneSuivante([E,E|L],[M,E|R]) :- conwayLigneSuivante([E|L],[N,E|R]), M is N+1.
  conwayLigneSuivante([E,F|L],[1,E|R]) :- dif(E,F), conwayLigneSuivante([F|L],R).

En Ocaml

let rec suivant c l e = match l with
    | [] -> [c; e]
    | t::q when t = e -> suivant (c + 1) q t
    | t::q -> c::e::(suivant 1 q t)
 
let conway n =
    let rec aux n l =
        print_newline (List.iter print_int l);
        if n > 1 then aux (n - 1) (suivant 1 (List.tl l) (List.hd l)) in
    aux n [1]
 
let () = conway 10

En Java

La classe ConwayTerm représente un terme donné de la suite. Sa méthode nextTerm calcule le terme suivant. Dans l'exemple ci-dessous, le premier terme est 1. Si l'on veut commencer avec 22, il faut un tableau de 2 bytes contenant chacun 2 et non un byte contenant 22 (new byte[] { 2,2 })

package fr.math.suite;
 
import java.util.Arrays;
 
public class ConwayTerm {
        private byte[] digits;
 
        /**
         * @param args
         */
        public static void main(String[] args) {
                ConwayTerm term = new ConwayTerm(new byte[] { 1 }); // Premier terme de la suite:1
                //Affiche les 25 premiers termes
                for (int i = 0; i < 25; i++) {
                        System.out.println("u(" + i + ")=" + term);
                        term = term.nextTerm();
                }
        }
 
        public ConwayTerm(byte[] digits) {
                this.digits = digits;
        }
 
        /**
         * calcule le terme suivant de la suite.
         */
        public ConwayTerm nextTerm() {
                if (digits.length != 0) {
                        byte count = 1;
                        while ((count < digits.length && digits[0] == digits[count])) count++;
                        return concat(count, digits[0], new ConwayTerm(Arrays.copyOfRange(
                                        digits, count, digits.length)).nextTerm());
                } else {
                        return this;
                }
        }
        /**
         * Affiche les chiffres du terme de la suite
         */
        public String toString() {
                StringBuffer buffer = new StringBuffer();
                for (byte b : digits) buffer.append(b);
                return buffer.toString();
        }
        private ConwayTerm concat(byte count, byte digit, ConwayTerm other) {
                byte[] result = new byte[2 + other.digits.length];
                result[0] = count;
                result[1] = digit;
                for (int i = 0; i < other.digits.length; i++) result[i + 2] = other.digits[i];
                return new ConwayTerm(result);
        }
 
}

Références

Liens externes

• (en) Suite A005150 sur l'Encyclopédie en ligne des suites de nombres entiers
• (en) Eric W. Weisstein, « Look and Says Sequence », sur MathWorld
• (en) Henry Bottomley, « Evolution of Conway's 92 Look and Say audioactive elements » : une compilation des 92 éléments « audioactifs » de la suite