#!/bin/bash

# Douglas Hofstadter ÀÇ À¯¸íÇÑ "Q-±Þ¼ö"(Q-series):

# Q(1) = Q(2) = 1
# Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), for n>2

# "¹«Áú¼­ÇÑ" Q-±Þ¼ö´Â ÀÌ»óÇÏ°í ¿¹ÃøÇÒ ¼ö ¾ø´Â ÇൿÀ» º¸ÀÔ´Ï´Ù.
# ÀÌ ±Þ¼öÀÇ Ã³À½ 20°³ Ç×Àº ´ÙÀ½°ú °°½À´Ï´Ù:
# 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 

# Hofstadter ˂ ̴, "Goedel, Escher, Bach: An Eternal Golden Braid",
# p. 137, ff. ¸¦ Âü°íÇϼ¼¿ä.


LIMIT=100     # °è»êÇÒ Ç× ¼ö
LINEWIDTH=20  # ÇÑ ÁÙ¿¡ Ãâ·ÂÇÒ Ç× ¼ö

Q[1]=1        # óÀ½ µÎ Ç×Àº 1.
Q[2]=1

echo
echo "Q-±Þ¼ö [$LIMIT Ç×]:"
echo -n "${Q[1]} "             # óÀ½ µÎ Ç×À» Ãâ·Â
echo -n "${Q[2]} "

for ((n=3; n <= $LIMIT; n++))  # C ÇüÅÂÀÇ ·çÇÁ Á¶°Ç.
do   # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]]  for n&gt;2
# Bash ´Â º¹ÀâÇÑ ¹è¿­ ¿¬»êÀ» Àß Ã³¸®ÇÒ ¼ö ¾ø±â ¶§¹®¿¡
# À§ÀÇ ½ÄÀ» Çѹø¿¡ °è»êÇÏÁö ¾Ê°í Áß°£¿¡ ´Ù¸¥ Ç×À» µÎ¾î °è»êÇÒ ÇÊ¿ä°¡ ÀÖ½À´Ï´Ù.

  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 - ![n-2]]
echo -n "${Q[n]} "

if [ `expr $n % $LINEWIDTH` -eq 0 ]    # ¿¹»Û Ãâ·Â
then   #    ³ª¸ÓÁö
  echo # °¢ ÁÙÀÌ ±¸ºÐµÇµµ·Ï ÇØ ÁÜ.
fi

done

echo

exit 0

# ¿©±â¼­´Â Q-±Þ¼ö¸¦ ¹Ýº¹ÀûÀ¸·Î ±¸ÇöÇß½À´Ï´Ù.
# Á» ´õ Á÷°üÀûÀÎ Àç±ÍÀû ±¸ÇöÀº µ¶ÀÚµéÀ» À§ÇØ ³²°Ü ³õ°Ú½À´Ï´Ù.
# °æ°í: ÀÌ ±Þ¼ö¸¦ Àç±ÍÀûÀ¸·Î °è»êÇϸé "¾ÆÁÖ" ±ä ½Ã°£ÀÌ °É¸³´Ï´Ù.