mirror of https://github.com/tLDP/LDP
60 lines
1.6 KiB
Bash
60 lines
1.6 KiB
Bash
#!/bin/bash
|
|
|
|
# Douglas Hofstadter's notorious "Q-series":
|
|
|
|
# Q(1) = Q(2) = 1
|
|
# Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), for n>2
|
|
|
|
# This is a "chaotic" integer series with strange
|
|
#+ and unpredictable behavior.
|
|
# The first 20 terms of the series are:
|
|
# 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12
|
|
|
|
# See Hofstadter's book, _Goedel, Escher, Bach: An Eternal Golden Braid_,
|
|
#+ p. 137, ff.
|
|
|
|
|
|
LIMIT=100 # Number of terms to calculate.
|
|
LINEWIDTH=20 # Number of terms printed per line.
|
|
|
|
Q[1]=1 # First two terms of series are 1.
|
|
Q[2]=1
|
|
|
|
echo
|
|
echo "Q-series [$LIMIT terms]:"
|
|
echo -n "${Q[1]} " # Output first two terms.
|
|
echo -n "${Q[2]} "
|
|
|
|
for ((n=3; n <= $LIMIT; n++)) # C-like loop expression.
|
|
do # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]] for n>2
|
|
# Need to break the expression into intermediate terms,
|
|
#+ since Bash doesn't handle complex array arithmetic very well.
|
|
|
|
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 % $LINEWIDTH` -eq 0 ] # Format output.
|
|
then # ^ modulo
|
|
echo # Break lines into neat chunks.
|
|
fi
|
|
|
|
done
|
|
|
|
echo
|
|
|
|
exit 0
|
|
|
|
# This is an iterative implementation of the Q-series.
|
|
# The more intuitive recursive implementation is left as an exercise.
|
|
# Warning: calculating this series recursively takes a VERY long time
|
|
#+ via a script. C/C++ would be orders of magnitude faster.
|