호프스타터 수열

수학에서 호프스태터 수열은 비선형 반복 관계에 의해 정의된 관련 정수 시퀀스 계열의 구성원이다.

괴델, 에셔, 바흐: 영원한 황금 브레이드

최초의 호프스타터 시퀀스는 더글러스 리처드 호프스타터가 그의 저서 괴델, 에셔, 바흐에서 서술한 것이다.그림 및 배경(그림-그림 순서)에 대한 III장 및 재귀적 구조와 프로세스(잔류 순서)에 대한 V장의 프레젠테이션 순서에 따라, 이러한 시퀀스는 다음과 같다.

Hofstadter 그림-그림 순서

Hofstadter 그림-그림(R 및 S) 시퀀스는 다음과^[1][2] 같이 정의된 보완 정수 시퀀스의 한 쌍이다.

${\displaystyle {\begin}R(1)&=1~;\S(1)=2\R(n)&=R(n-1)+S(n-1),\quad n>1.\end{정렬}}}$

$R{\displaystyle }$${\displaystyle }$(${\displaystyle n}$) ${\displaystyle S(n)}$ 시퀀스를 R${\displaystyle }$(${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle R(n)}$에 없는 엄밀하게 증가하는 양의 정수 시리즈로$$ 정의한다$.$이 시퀀스의 처음 몇 개 항은

R: 1, 3, 7, 12, 18, 26, 35, 45, 56, 69, 83, 98, 114, 131, 150, 191, 213, 236, 260, ... (OEIS에서의 연속 A005228)

S: 2, 4, 5, 6, 8, 9, 10, 11, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, ... (OEIS의 경우 순서 A030124)

호프슈타터 G 시퀀스

Hofstadter G 시퀀스는 다음과^[3][4] 같이 정의된다.

${\displaystyle {\begin}G(0)&=0\\g(n)&=n-G(n-1)),\quad n>0.\end{정렬}}}$

이 시퀀스의 처음 몇 개 용어는

0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, ... (OEIS의 경우 순서 A005206)

호프슈타터 H 시퀀스

Hofstadter H 시퀀스는 다음과^[3][5] 같이 정의된다.

${\displaystyle {\begin}H(0)&=0\\H(n)&=n-H(H(n-1)),\quad n>0.\end{정렬}}}$

이 시퀀스의 처음 몇 개 용어는

0, 1, 2, 3, 4, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 13, 14, ... (OEIS에서 연속 A005374)

호프스태터 여성 및 남성 시퀀스

호프스타터 여성(F) 및 남성(M) 시퀀스는 다음과^[3][6] 같이 정의된다.

${\displaystyle {\begin}F(0)&=1~;\M(0)=0\\\F(n-1)=n-M(n-1)=\quad n>0\\\m(n)&=n-F(M(n-1)),\quad n>0.\end{정렬}}}$

이 시퀀스의 처음 몇 개 항은

F: 1, 1, 2, 3, 3, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, ... (OEIS에서 연속 A005378)

M: 0, 0, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, ... (OEIS에서 순서 A005379)

호프슈타터 Q 시퀀스

Hofstadter Q 시퀀스는 다음과^[3][7] 같이 정의된다.

${\displaystyle {\begin}Q(1)&=Q(2)=1,\Q(n)&=Q(n)&=Q(n)+Q(n-Q(n-2)),\quad n>2.\end{정렬}}}$

그 수열의 처음 몇 항은

1, 1, 2, 3, 3, 4, 5, 6, 6, 6, 8, 8, 8, 10, 9, 10, 11, 11, 12, ... (OEIS에서 연속 A005185)

호프스태터는 수열의 항을 "Q numbers"^[3]라고 명명했다. 따라서 Q number 6은 4이다.호프스태터의 책에서 Q순서의 발표는 사실 문학에서 메타 피보나치 수열의 첫 번째 알려진 언급이다.^[8]

피보나치 수열의 조건은 앞의 두 용어를 합쳐서 결정되지만, Q 번호의 앞의 두 항은 합계가 될 두 항을 찾기 위해 Q 수열에서 얼마나 거슬러 올라가야 하는지를 결정한다.따라서 종합 조건의 지수는 Q 시퀀스 자체에 따라 달라진다.

시퀀스의 첫 번째 요소인 Q(1)는 이후 요소를 생성하기 위해 추가되는 두 가지 용어 중 하나가 아니며, Q(3)의 계산에서 지수 내에서만 관련된다.^[9]

Q 시퀀스의 용어는 많은 메타-피보나치 시퀀스와 같이 차오티컬하게 흐르지만,^{[3][10][11][12]} 그것의 용어는 연속 세대를 이루는 블록으로 분류될 수 있다.^[13][14]Q 시퀀스의 경우 k-th 세대는 2명의^k 멤버가 있다.^[15]더욱이 g가 Q 번호가 속하는 세대인 상황에서, 그 부모라고 불리는 Q 숫자를 계산하기 위해 요약해야 할 두 용어는 g - 1세대에 훨씬 많이 존재하고 g - 2세대에 몇 개만 존재하지만, 심지어 더 나이든 세대에는 결코 존재하지 않는다.^[16]

이러한 발견의 대부분은 경험적 관찰이다. 왜냐하면 사실상 어떤 것도 지금까지 Q 순서에 대해 엄격하게 증명된 것이 없기 때문이다.^[17][18][19]모든 n에 대해 시퀀스가 잘 정의되어 있는지 특히 알 수 없다. 즉, 그 세대 규칙이 개념적으로 첫 번째 용어 Q(1)의 왼쪽에 위치할 용어를 참조하려고 하기 때문에 시퀀스 "dies"가 어느 시점에 "dies"로 정의되어 있는지 알 수 없다.^[12][17][19]

Q 시퀀스의 일반화

호프스타터-휴버_r,s Q(n) 패밀리

호프스태터가 Q 시퀀스를 처음 설명한 지 20년 후, 그와 그렉 휴버는 등장인물 Q를 사용해 시퀀스 계열을 향해 Q 시퀀스의 일반화의 이름을 붙였고, 책의 원래 Q 시퀀스를 U 시퀀스로 개칭했다.^[19]

원래의 Q 시퀀스는 각각 (n - 1)과 (n - 2)를 (n - r)과 (n - s)로 대체함으로써 일반화된다.^[19]

이것이 시퀀스 패밀리로 이어진다.

${\displaystyle Q_{r,s}={\begin{case}1,\quad 1\leq n\leq s,\\Q_{r,s}(n-Q_{r,s})+Q_{r,s}(n-Q_{r,s})(n-s),\quad n>s,\end{case}}}$

여기서 s ≥ 2와 r < s.

(r,s) = (1,2)를 사용하는 경우, 원래의 Q 시퀀스는 이 계열의 구성원이다.지금까지 알려진 것은 패밀리 Q의_r,s U 시퀀스(r,s) = (1,2)(원래 Q 시퀀스),^[19] (r,s) = (1,4),^[20] (r,s) = (2,4)가 있는 V 시퀀스뿐이다.^[19]다른 것들과 같이 비현실적으로 행동하지 않는 V 시퀀스만이 "죽지"^[19] 않는 것으로 증명된다.원래의 Q 순서와 유사하게, 사실상 현재까지 W 순서에 대해 엄격하게 입증된 것은 없다.^[19]

V 시퀀스의 처음 몇 개 용어는

1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 8, 9, 9, 10, 11, 11, 11, ... (OEIS에서 연속 A063882)

W 시퀀스의 처음 몇 항은

1, 1, 1, 2, 4, 6, 7, 7, 5, 3, 8, 9, 11, 12, 9, 13, 11, 11, 9, 9, 9, ... (OEIS에서 연속 A087777)

다른 값(r,s)의 경우, 조만간 시퀀스 "die" 즉, n - Q(n_r,s - r) < 1 때문에 Q_r,s(n)가 정의되지 않은 n이 존재한다.^[19]

핀 에프_i,j(n) 가문

1998년 뮌스터 대학(독일)의 과학자 클라우스 핀은 호프스타터(Hofstadter)와 긴밀히 소통하면서 핀이 F 시퀀스라고 부른 호프스타터 Q 시퀀스의 또 다른 일반화를 제안했다.^[21]

핀 F 시퀀스_i,j 패밀리는 다음과 같이 정의된다.

${\displaystyle F_{i,j}(n)={\begin{case}1,\quad n=1,2,\F_{i,j}(n-i_{i,j-1)+F_{i,j}(n-j-F_{i,j}(n-2)),\quad n>2.\end{case}}}$

따라서 핀은 개념적으로 합계 항의 지수를 왼쪽으로 이동시키는 추가 상수 i와 j를 도입했다(즉, 시퀀스의 시작에 가깝다).^[21]

첫 번째 Q 시퀀스를 나타내는 (i,j) = (0,0), (0,1), (1,0), (1,1)의 F 시퀀스만 잘 정의되어 있는 것으로 보인다.^[21]Q(1)와 달리 핀 F_i,j(n) 시퀀스의 첫 번째 요소는 추가 상수 중 하나가 1일 때 시퀀스의 이후 요소를 계산할 때 합한 용어다.

핀_0,1 F 시퀀스의 처음 몇 개 용어는

1, 1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 8, 8, 9, 10, 10, 11, ... (OEIS에서 연속 A046699)

호프스타터-콘웨이 1만 달러 수열

Hofstadter-Conway $10,000 시퀀스는 다음과^[22] 같이 정의된다.

이 시퀀스의 처음 몇 개 용어는

1, 1, 2, 3, 4, 4, 4, 4, 5, 6, 7, 8, 8, 8, 9, 10, 11, 12, ... (OEIS에서 연속 A004001)

$a{\displaystyle }$ (${\displaystyle n}$ )${\displaystyle }$/${\displaystyle n}$ ${\displaystyle a(n)/n}$ 값은 1/2로 수렴되며$$, 이 순서는 존 호튼 콘웨이가 수렴 속도를 결정할 수 있는 사람에게 1만 달러의 상금을 제안했기 때문에 그 이름을 얻었다.그 이후 1,000달러로 줄어든 상금은 콜린 말로스가 주장했는데, 그는 그 사실을^[23][24] 증명했다.

이후 클라우스 핀과의 사적인 대화에서 호프슈타터는 콘웨이가 도전을 제기하기 약 10~15년 전에 이 수열과 그 구조를 발견했다고 주장했다.^[10]

참조

원천

• Balamohan, B.; Kuznetsov, A.; Tanny, Stephan M. (2007-06-27), "On the Behaviour of a Variant of Hofstadter's Q-Sequence" (PDF), Journal of Integer Sequences, Waterloo, Ontario (Canada): University of Waterloo, 10 (7): 71, Bibcode:2007JIntS..10...71B, ISSN 1530-7638.
• Emerson, Nathaniel D. (2006-03-17), "A Family of Meta-Fibonacci Sequences Defined by Variable-Order Recursions" (PDF), Journal of Integer Sequences, Waterloo, Ontario (Canada): University of Waterloo, 9 (1), ISSN 1530-7638.
• Hofstadter, Douglas (1980), Gödel, Escher, Bach: an Eternal Golden Braid, Penguin Books, ISBN 0-14-005579-7.
• Pinn, Klaus (1999), "Order and Chaos in Hofstadter's Q(n) Sequence", Complexity, 4 (3): 41–46, arXiv:chao-dyn/9803012v2, Bibcode:1999Cmplx...4c..41P, doi:10.1002/(SICI)1099-0526(199901/02)4:3<41::AID-CPLX8>3.0.CO;2-3.
• Pinn, Klaus (2000), "A Chaotic Cousin of Conway's Recursive Sequence", Experimental Mathematics, 9 (1): 55–66, arXiv:cond-mat/9808031, Bibcode:1998cond.mat..8031P, doi:10.1080/10586458.2000.10504635, S2CID 13519614.
• Ullah, AMM Sharif (2017), "Surface Roughness Modeling Using Q-Sequence", Mathematical and Computational Applications, 22 (2): 33, doi:10.3390/mca22020033.