호프스타터 수열

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] 같이 정의된다.

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

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] 같이 정의된다.

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

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

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

호프스타터 여성(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] 같이 정의된다.

그 수열의 처음 몇 항은

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]

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

여기서 s ≥ 2와 r < s.

(r,s) = (1,2)를 사용하는 경우, 원래의 Q 시퀀스는 이 계열의 구성원이다.지금까지 알려진 것은 패밀리 Qr,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(nr,s - r) < 1 때문에 Qr,s(n)가 정의되지 않은 n이 존재한다.[19]

에프i,j(n) 가문

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

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

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

번째 Q 시퀀스를 나타내는 (i,j) = (0,0), (0,1), (1,0), (1,1)의 F 시퀀스만 잘 정의되어 있는 것으로 보인다.[21]Q(1)와 달리 핀 Fi,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)

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

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

참조

  1. ^ 호프스태터(1980), 페이지 73
  2. ^ Weisstein, Eric W. "Hofstadter Figure-Figure Sequence". MathWorld.
  3. ^ a b c d e f 호프스타터(1980), 페이지 137
  4. ^ Weisstein, Eric W. "Hofstadter G-Sequence". MathWorld.
  5. ^ Weisstein, Eric W. "Hofstadter H-Sequence". MathWorld.
  6. ^ Weisstein, Eric W. "Hofstadter Male-Female Sequences". MathWorld.
  7. ^ Weisstein, Eric W. "Hofstadter's Q-Sequence". MathWorld.
  8. ^ 에머슨(2006), 페이지 1, 7
  9. ^ 핀(1999), 페이지 5-6
  10. ^ a b 핀(1999), 페이지 3
  11. ^ 핀(2000), 페이지 1
  12. ^ a b 에머슨(2006), 페이지 7
  13. ^ 핀(1999), 페이지 3-4
  14. ^ 발라모한, 쿠즈넷소프 & 타니(2007), 페이지 19
  15. ^ 핀(1999), 추상화, 페이지 8
  16. ^ 핀(1999), 페이지 4~5
  17. ^ a b 핀(1999), 페이지 2
  18. ^ 핀(2000), 페이지 3
  19. ^ a b c d e f g h i 발라모한, 쿠즈넷소프 & 타니(2007), 페이지 2
  20. ^ 발라모한, 쿠즈넷소프 & 타니(2007), 전문기사
  21. ^ a b c 핀(2000), 페이지 16
  22. ^ Weisstein, Eric W. "Hofstadter-Conway $10,000 Sequence". MathWorld.
  23. ^ Tempel, Michael. "Easy as 1 1 2 2 3" (PDF).
  24. ^ Mallows, Colin L. (1991). "Conway's challenge sequence". The American Mathematical Monthly. 98 (1): 5–20. doi:10.2307/2324028. JSTOR 2324028. MR 1083608.

원천