콜라코스키 수열

Kolakoski sequence
Kolakoski 수열의 3번째에서 50번째 항을 나선형으로 시각화. 용어는 나선형의 중간에 있는 점에서 시작된다. 다음 혁명에서는 항이 1이면 각 호를 반복하고, 2이면 2등분한다. 처음 두 용어는 자기주장적이기 때문에 보일 수 없다. SVG 이미지에서 호 또는 레이블 위로 마우스를 가져가서 강조 표시하고 통계를 표시하십시오.

수학에서 콜라코스키 시퀀스는 때로 올덴버거-콜라코스키 시퀀스로도 알려져 있으며 [1]자체 런 길이 인코딩에서 런 길이의 시퀀스인 {1,2} 기호의 무한 시퀀스다.[2] 1965년 이를 기술한 레크리에이션 수학자 윌리엄 콜라코스키(1944~97년)의 이름을 딴 것이지만,[3] 앞서 1939년 루푸스 올덴버거가 논의한 바 있다.[1][4]

정의

콜라코스키 시퀀스는 자체 주행 길이를 설명한다.

콜라코스키 수열의 초기 조건은 다음과 같다.

1,2,2,1,1,2,2,2,2,2,2,2,1,2,1,2,1,2,2,1,2,1,2,1,2,1,2,1,2,1,1,2,1,2,1,...(OEIS의 A000002 시퀀스 A000002)

각 기호는 1개 또는 2개의 연속된 항의 "런"(동일한 요소의 시퀀스)에서 발생하며, 이러한 런의 길이를 적는 것은 정확히 동일한 시퀀스를 제공한다.

1,2,2,1,1,2,1,2,2,1,2,2,1,1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,2,1,2,2,1,2,2,1,1,2,1,2,2,...
1, 2 , 2 ,1,1, 2 ,1, 2 , 2 ,1, 2 , 2 ,1,1, 2 ,1,1, 2 , 2 ,1, 2 ,1,1, 2 ,1, 2 , 2 ,1,1, 2 ,...

그러므로 콜라코스키 수열의 설명은 되돌릴 수 있다. K가 "Kolakoski sequence"를 의미하는 경우, 설명 #1은 논리적으로 설명 #2(그리고 그 반대)를 내포한다.

1. K의 조건은 K의 런(즉, 런 길이)에 의해 생성된다.
2. K의 런은 K의 조건에 의해 생성된다.

따라서, 콜라코스키 시퀀스의 각 용어는 한두 개의 미래 용어의 런을 발생시킨다고 말할 수 있다. 시퀀스의 첫 번째 1은 "1" 즉, 그 자체로 실행되며, 첫 번째 2는 자신을 포함하는 "22"의 실행이 생성되며, 두 번째 2는 "11"의 실행이 생성된다. 시퀀스의 각 숫자는 생성될 다음 실행의 길이이며, 생성될 요소는 1과 2 사이에 번갈아 나타난다.

1,2(시퀀스 l = 2; 항의 합계 s = 3)
1,2,2 (l = 3, s = 5)
1,2,2,1,1 (l = 5, s = 7)
1,2,2,1,1,2,1 (l = 7, s = 10)
1,2,2,1,1,2,1,2,2,1 (l = 10,s = 15)
1,2,2,1,1,2,2,2,2,2,2,2,2,2,1,1,2 (l = 15,s = 23)

보시다시피 각 단계에서 시퀀스의 길이는 이전 단계의 용어 합계와 동일하다. 이 애니메이션은 다음과 같은 과정을 보여준다.

An animated gif illustrating how later terms of the Kolakoski sequence are generated by earlier terms.

이러한 자기 생성 속성은 초기 1을 제외하고 시퀀스를 작성하면 남는 것으로서, 콜라코스키 시퀀스를 프랙탈, 또는 다른 척도로 그 자신의 표현을 암호화하는 수학적 개체로 설명할 수 있다는 것을 의미한다.[1] 베르트란 스틴스키가 수열의[5] i번째 용어를 위해 재귀 공식을 만들었지만, 수열이 aperiodic,[6] 즉 그 용어들이 일반적인 반복 패턴을 가지고 있지 않다고 추측된다(cf. π, √2와 같은 불합리한 숫자).

리서치

밀도

콜라코스키{1,2}시퀀스의 1s 밀도가 1/2인 것은 그럴듯해 보이지만, 이러한 추측은 여전히 입증되지 않고 있다.[6] 바클라프 차바탈은 1초의 상위 밀도가 0.50084보다 낮다는 것을 증명했다.[7] Nilsson은 바운드 0.500080을 얻기 위해 계산력이 훨씬 더 큰 동일한 방법을 사용해 왔다.[8]

비록 수열의 처음 3×108 값들의 계산은 그 밀도가 1/2과 약간 다른 값으로 수렴되는 것으로 나타났지만,[5] 그 수열을 처음 1013 값으로 확장한 이후의 계산은, 제한 밀도가 실제로 1/2일 경우 예상할 수 있듯이 1/2의 밀도가 더 작아지는 것을 보여준다.[9]

태그 시스템 연결

콜라코스키 시퀀스는 단순한 순환 태그 시스템의 결과라고도 설명할 수 있다. 그러나 이 시스템은 1태그 시스템보다는 2태그 시스템(즉, 한 번에 하나의 기호로 동작하는 것이 아니라 다른 기호의 시퀀스로 기호의 쌍을 대체하는 시스템)이기 때문에 태그 시스템이 튜링 완료되어 있는 파라미터 영역에 놓여 있어 시퀀스에 대해 이 표현을 이용하기 어렵다.[10]

알고리즘

콜라코스키 시퀀스는 i-th 반복에서 이미 출력된 값 x를i 시퀀스의 i-th 값으로 읽는 알고리즘(또는 아직 출력되지 않은 경우 x = i를 설정)에i 의해 생성될 수 있다. 그런 다음 내가 홀수일 경우 숫자 1의 x 사본을i 출력하고 짝수일 경우 숫자 2의 x 복사본을i 출력한다. 따라서 알고리즘의 처음 몇 단계는 다음과 같다.

  1. 첫 번째 값이 아직 출력되지 않았으므로 x1 = 1을 설정하고 숫자 1의 출력 1 복사본을 설정하십시오.
  2. 두 번째 값은 아직 출력되지 않았으므로 x2 = 2를 설정하고 숫자 2의 출력 복사본을 2로 설정하십시오.
  3. 세 번째 값 x는3 두 번째 단계에서 2로 출력되었으므로 숫자 1의 복사본 2개를 출력한다.
  4. 네 번째 값 x는4 세 번째 단계에서 1로 출력되었으므로, 숫자 2의 복사본 1개를 출력한다. 등

이 알고리즘은 선형 시간이 걸리지만, 시퀀스에서 이전 위치를 다시 참조할 필요가 있기 때문에 전체 시퀀스를 저장하여 선형 공간을 확보해야 한다. 각 단계에서 수행할 작업을 결정하기 위해 이전 복사본의 출력을 사용하여 서로 다른 속도로 시퀀스의 여러 복사본을 생성하는 대체 알고리즘을 사용하여 선형 시간 및 로그 공간에서만 시퀀스를 생성할 수 있다.[9]

참고 항목

메모들

  1. ^ a b c Sloane, N. J. A. (ed.). "Sequence A000002 (Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
  2. ^ Pytheas Fogg, N. (2002). Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. (eds.). Substitutions in dynamics, arithmetics and combinatorics. Lecture Notes in Mathematics. 1794. Berlin: Springer-Verlag. p. 93. ISBN 3-540-44141-7. Zbl 1014.11015.
  3. ^ Kolakoski, William (1965). "Problem 5304". American Mathematical Monthly. 72: 674. doi:10.2307/2313883. 부분적인 해결책은 다음을 참조하십시오.
  4. ^ Oldenburger, Rufus (1939). "Exponent trajectories in symbolic dynamics". Transactions of the American Mathematical Society. 46: 453–466. doi:10.2307/1989933. MR 0000352.
  5. ^ a b Steinsky, Bertran (2006). "A recursive formula for the Kolakoski sequence A000002" (PDF). Journal of Integer Sequences. 9 (3). Article 06.3.7. MR 2240857. Zbl 1104.11012.
  6. ^ a b Kimberling, Clark. "Integer Sequences and Arrays". University of Evansville. Retrieved 2016-10-13.
  7. ^ Chvátal, Vašek (December 1993). Notes on the Kolakoski Sequence. Technical Report 93-84. DIMACS.
  8. ^ Nilsson, J. "Letter Frequencies in the Kolakoski Sequence" (PDF). Acta Physics Polonica A. Retrieved 2014-04-24.
  9. ^ a b Nilsson, Johan (2012). "A space-efficient algorithm for calculating the digit distribution in the Kolakoski sequence" (PDF). Journal of Integer Sequences. 15 (6): Article 12.6.7, 13. MR 2954662.
  10. ^ van der Poorten, A. J. (1981). "Substitution automata, functional equations and "functions algebraic over a finite field"". Papers in algebra, analysis and statistics (Hobart, 1981). Contemporary Mathematics. 9. Providence, Rhode Island: American Mathematical Society. pp. 307–312. MR 0655988. 특히 페이지 308을 참조하라.

추가 읽기

외부 링크