#!/bin/bash

# Les célèbres "Q-series" de Douglas Hofstadter :

# Q(1) = Q(2) = 1
# Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), pour n&gt;2

#  C'est une série chaotique d'entiers avec un comportement étrange et non
#+ prévisible.
# Les 20 premiers termes de la série étaient :
# 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 

#  Voir le livre d'Hofstadter, _Goedel, Escher, Bach: An Eternal Golden Braid_,
#+ p. 137, ff.


LIMITE=100        # Nombre de termes à calculer.
LONGUEURLIGNE=20  # Nombre de termes à afficher par ligne.

Q[1]=1            # Les deux premiers termes d'une série sont 1.
Q[2]=1

echo
echo "Q-series [$LIMITE termes] :"
echo -n "${Q[1]} "             # Affiche les deux premiers termes.
echo -n "${Q[2]} "

for ((n=3; n &lt;= $LIMITE; n++))  # Expressions de boucle style C.
do   # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]]  for n&gt;2
#  Nécessaire de casser l'expression en des termes intermédiaires
#+ car Bash ne gère pas très bien l'arithmétique des tableaux complexes.

  let "n1 = $n - 1"        # n-1
  let "n2 = $n - 2"        # n-2
  
  t0=`expr $n - ${Q[n1]}`  # n - Q[n-1]
  t1=`expr $n - ${Q[n2]}`  # n - Q[n-2]
  
  T0=${Q[t0]}              # Q[n - Q[n-1]]
  T1=${Q[t1]}              # Q[n - Q[n-2]]

Q[n]=`expr $T0 + $T1`      # Q[n - Q[n-1]] + Q[n - Q[n-2]]
echo -n "${Q[n]} "

if [ `expr $n % $LONGUEURLIGNE` -eq 0 ]    # Formate la sortie.
then   #      ^ Opérateur modulo
  echo # Retour chariot pour des ensembles plus jolis.
fi

done

echo

exit 0

# C'est une implémentation itérative de la Q-series.
# L'implémentation récursive plus intuitive est laissée comme exercice.
#  Attention : calculer cette série récursivement prend BEAUCOUP de temps
#+ via un script. C/C++ aurait mieux convenu.