콜라코스키 수열

섬네일
유희 수학에서, 콜라코스키 수열(Kolakoski sequence, Oldenburger-Kolakoski sequence)은 스스로의 런 렝스 부호화와 일치하며, 1부터 시작하는, 1과 2로 구성된 수열이다. 1965년 이 수열을 기술한 유희 수학자 윌리엄 콜라코스키(1944~97)의 이름을 딴 수열이지만, For a partial solution, see  그 이전인 1939년 루푸스 올덴버거(Rufus Oldenburger)가 이에 관해 논한 적이 있다.

 정의 
콜라코스키 수열은 1부터 시작하며, 같은 수가 연속되는 부분의 길이들의 수열이 스스로와 일치하는, 유일한  값의 수열이다. 즉, 다음과 같다.
 첫 항만큼 1을 항으로 추가한다. 첫 항은 1이므로, 1을 하나 추가하며, 이는 수열의 첫 항이다.
 둘째 항만큼 2를 항으로 추가한다. 둘째 항은 2이므로, 2를 둘 추가한다.
 셋째 항만큼 1을 항으로 추가한다. 셋째 항은 2이므로, 1을 둘 추가한다.
 넷째 항만큼 2를 항으로 추가한다. 넷째 항은 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, ... 

 성질 
 비주기성 
콜라코스키 수열은 세제곱 인수가 없는 수열()이다 (즉, 1과 2의 문자열로 여겼을 때, 빈 문자열이 아닌 유한 문자열 에 대하여  꼴의 부분 문자열을 갖지 않는다). 특히, 콜라코스키 수열은 최종적으로 주기 수열이 아니다.

 1의 밀도 
콜라코스키 수열 속 1의 점근 밀도가 존재하는지, 만약 존재한다면 1/2인지 여부는 알려지지 않았다. 하지만 다음과 같은 (점차 개선되는) 부분적인 결과가 존재한다.
 1의 상 점근 밀도 및 2의 상 점근 밀도 < 0.50084
 1의 상 점근 밀도 및 2의 상 점근 밀도 ≤ 0.500080

 점화식 
콜라코스키 수열은 다음과 같은 점화식을 갖는다.

 같이 보기 
 읽고 말하기 수열

 참고 문헌 

 외부 링크 

 Kolakoski Constant to 25000 digits as computed by Olivier Gerard in April 1998


분류:정수열
분류:프랙탈
분류:홀짝성