호프스타터 수열
Hofstadter sequence수학에서 호프스태터 수열은 비선형 반복 관계에 의해 정의된 관련 정수 시퀀스 계열의 구성원이다.
괴델, 에셔, 바흐: 영원한 황금 브레이드
최초의 호프스타터 시퀀스는 더글러스 리처드 호프스타터가 그의 저서 괴델, 에셔, 바흐에서 서술한 것이다.그림 및 배경(그림-그림 순서)에 대한 III장 및 재귀적 구조와 프로세스(잔류 순서)에 대한 V장의 프레젠테이션 순서에 따라, 이러한 시퀀스는 다음과 같다.
Hofstadter 그림-그림 순서
Hofstadter 그림-그림(R 및 S) 시퀀스는 다음과[1][2] 같이 정의된 보완 정수 시퀀스의 한 쌍이다.
() 시퀀스를 R( 에 없는 엄밀하게 증가하는 양의 정수 시리즈로 정의한다이 시퀀스의 처음 몇 개 항은
- 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] 같이 정의된다.
이 시퀀스의 처음 몇 개 용어는
호프슈타터 H 시퀀스
Hofstadter H 시퀀스는 다음과[3][5] 같이 정의된다.
이 시퀀스의 처음 몇 개 용어는
호프스태터 여성 및 남성 시퀀스
호프스타터 여성(F) 및 남성(M) 시퀀스는 다음과[3][6] 같이 정의된다.
이 시퀀스의 처음 몇 개 항은
- 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] 같이 정의된다.
그 수열의 처음 몇 항은
호프스태터는 수열의 항을 "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]
이것이 시퀀스 패밀리로 이어진다.
여기서 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 시퀀스의 처음 몇 개 용어는
W 시퀀스의 처음 몇 항은
다른 값(r,s)의 경우, 조만간 시퀀스 "die" 즉, n - Q(nr,s - r) < 1 때문에 Qr,s(n)가 정의되지 않은 n이 존재한다.[19]
핀 에프i,j(n) 가문
1998년 뮌스터 대학(독일)의 과학자 클라우스 핀은 호프스타터(Hofstadter)와 긴밀히 소통하면서 핀이 F 시퀀스라고 부른 호프스타터 Q 시퀀스의 또 다른 일반화를 제안했다.[21]
핀 F 시퀀스i,j 패밀리는 다음과 같이 정의된다.
따라서 핀은 개념적으로 합계 항의 지수를 왼쪽으로 이동시키는 추가 상수 i와 j를 도입했다(즉, 시퀀스의 시작에 가깝다).[21]
첫 번째 Q 시퀀스를 나타내는 (i,j) = (0,0), (0,1), (1,0), (1,1)의 F 시퀀스만 잘 정의되어 있는 것으로 보인다.[21]Q(1)와 달리 핀 Fi,j(n) 시퀀스의 첫 번째 요소는 추가 상수 중 하나가 1일 때 시퀀스의 이후 요소를 계산할 때 합한 용어다.
핀0,1 F 시퀀스의 처음 몇 개 용어는
호프스타터-콘웨이 1만 달러 수열
Hofstadter-Conway $10,000 시퀀스는 다음과[22] 같이 정의된다.
이 시퀀스의 처음 몇 개 용어는
( )/ 값은 1/2로 수렴되며, 이 순서는 존 호튼 콘웨이가 수렴 속도를 결정할 수 있는 사람에게 1만 달러의 상금을 제안했기 때문에 그 이름을 얻었다.그 이후 1,000달러로 줄어든 상금은 콜린 말로스가 주장했는데, 그는 그 사실을[23][24] 증명했다.
참조
- ^ 호프스태터(1980), 페이지 73
- ^ Weisstein, Eric W. "Hofstadter Figure-Figure Sequence". MathWorld.
- ^ a b c d e f 호프스타터(1980), 페이지 137
- ^ Weisstein, Eric W. "Hofstadter G-Sequence". MathWorld.
- ^ Weisstein, Eric W. "Hofstadter H-Sequence". MathWorld.
- ^ Weisstein, Eric W. "Hofstadter Male-Female Sequences". MathWorld.
- ^ Weisstein, Eric W. "Hofstadter's Q-Sequence". MathWorld.
- ^ 에머슨(2006), 페이지 1, 7
- ^ 핀(1999), 페이지 5-6
- ^ a b 핀(1999), 페이지 3
- ^ 핀(2000), 페이지 1
- ^ a b 에머슨(2006), 페이지 7
- ^ 핀(1999), 페이지 3-4
- ^ 발라모한, 쿠즈넷소프 & 타니(2007), 페이지 19
- ^ 핀(1999), 추상화, 페이지 8
- ^ 핀(1999), 페이지 4~5
- ^ a b 핀(1999), 페이지 2
- ^ 핀(2000), 페이지 3
- ^ a b c d e f g h i 발라모한, 쿠즈넷소프 & 타니(2007), 페이지 2
- ^ 발라모한, 쿠즈넷소프 & 타니(2007), 전문기사
- ^ a b c 핀(2000), 페이지 16
- ^ Weisstein, Eric W. "Hofstadter-Conway $10,000 Sequence". MathWorld.
- ^ Tempel, Michael. "Easy as 1 1 2 2 3" (PDF).
- ^ Mallows, Colin L. (1991). "Conway's challenge sequence". The American Mathematical Monthly. 98 (1): 5–20. doi:10.2307/2324028. JSTOR 2324028. MR 1083608.
원천
- 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.