완전순서

수학에서 모든 양의 정수를 최대 한 번에 각 값을 사용하여 순서에 있는 값의 합으로 표현할 수 있다면 자연수의 순서는 완전한 순서라고 한다.

예를 들어 2진수 시스템의 기초인 2진수(1, 2, 4, 8, ...)의 검정력 순서는 완전한 순서다. 자연수가 있으면 2진수에서 1비트에 해당하는 값을 선택하여 합하여 그 숫자를 얻을 수 있다(예: 37 = 100101₂ = 1 + 4 + 32).이 순서는 어떤 값도 자연수를 나타내기 불가능하게 만들지 않고서는 제거할 수 없기 때문에 미미하다.짝수를 더하면 짝수만 생성되므로, 완전하지 않은 시퀀스의 간단한 예에는 짝수 수가 포함된다. 홀수 수는 형성할 수 없다.

완전성을 위한 조건

일반성을 상실하지 않고, a의_n 순서가 비감소 순서라고 가정하고, a의_n 부분 합을 다음과 같이 정의한다.

${\displaystyle s_{}}$ =${\displaystyle {}_{}\underset{m}{\overset{}{}}}$= ${\displaystyle \underset{}{\overset{}{\mathrm{0n}}}}$ ${\displaystyle \underset{}{\overset{}{}}}$ ${\displaystyle m_{}}$ ${\$

그러면 조건들이.

${\displaystyle a_{0}=1\,}$

${\displaystyle s_{k-1}\geq a_{k}-1{\text{{{}모든 }에 대해 {\displaystyle s_{k-1}{k}-1\text{}$

a가_n 완전한 시퀀스가 되려면 필요하기도 하고 충분하기도 하다.^[1][2]

위와 같은 유의사항은 다음과 같다.

${\displaystyle a_{0}=1\,}$

${\displaystyle 2a_{k}\geq a_{k+1}{\text{{{}모든 }k\geq 1}$

전체_n 시퀀스가 되기에 충분하다.^[1]

그러나 예를 들어(OEIS의 순서 A203074), 숫자 1과 2의 각 동력 뒤의 첫 번째 프라임으로 구성되는 등, 이 골수를 만족시키지 못하는 완전한 시퀀스가 있다.

기타 전체 시퀀스

전체 시퀀스에는 다음이 포함된다.

• 숫자 1의 순서 다음에 소수점(S. S. S. 필라이^[3] 등이 연구함); 이것은 베르트랑의 추론에서 따온 것이다.^[1]
• 1을 첫 번째 항으로 하고 2의 다른 모든 힘을 하위 집합으로 포함하는 실제 숫자의 순서.^[4](OEIS에서 A005153 시퀀스)
• 피보나치 숫자 및 한 개의 숫자가 제거된 피보나치 숫자.^[1]이는 첫 번째 n 피보나치 숫자의 합이 (n + 2)nd 피보나치 숫자 마이너스 1이라는 정체성에서 따온 것이다(피보나치_numbers#Second_identity 참조).

적용들

두 개의 힘이 이진수 체계로 인해 완전한 시퀀스를 형성하는 것처럼, 사실 어떤 완전한 시퀀스도 정수를 비트 문자열로 인코딩하는 데 사용될 수 있다.가장 오른쪽 비트 위치는 시퀀스의 첫 번째, 가장 작은 멤버에 할당되고, 다음으로 가장 오른쪽이 다음 멤버에 할당된다.1로 설정된 비트는 합계에 포함된다.이러한 표현은 독특하지 않을 수 있다.

피보나치 부호화

예를 들어 피보나치 산술 체계에서는 피보나치 수열을 바탕으로 숫자 17을 다음과 같은 6가지 방법으로 인코딩할 수 있다.

110111(F₆ + F₅ + F₃ + F₂ + F₁ + F = 8 + 5 + 2 + 1 = 17, 최대 형식)

111001(F₆ + F₅ + F₄ + F₁ + F = 8 + 5 + 3 + 1 = 17)

111010(F₆ + F₅ + F₄ + F₂ + F = 8 + 5 + 3 + 1 = 17)

1000111 (F₇ + F₃ + F₂ + F₁ = 13 + 2 + 1 = 17)

1001001(F₇ + F₄ + F₁ = 13 + 3 + 1 = 17)

1001010(F₇ + F₄ + F₂ = 13 + 3 + 1 = 17, 최소 형태, 피보나치 부호화에 사용됨)

위의 최대 형태는 항상 F를₁ 사용하고 후행 형태는 항상 F를 사용할 것이다.후행 코딩이 없는 전체 코딩은 (OEIS의 순서 A104326)에서 확인할 수 있다.후행 1을 떨어뜨림으로써 위의 17에 대한 코딩은 A104326의 16번째 항으로 발생한다.최소 형태는 절대 F를₁ 사용하지 않으며 항상 후행 0을 가질 것이다.후행 0이 없는 전체 코딩은 (OEIS의 순서 A014417)에서 확인할 수 있다.이 코딩은 Zeckendorf의 표현으로 알려져 있다.

이 숫자 체계에서, 모든 하위 문자열 "100"은 "011"로 대체될 수 있고, 그 반대는 피보나치 숫자의 정의로 인해 "011"로 대체될 수 있다.^[5]이러한 규칙의 지속적인 적용은 최대한의 형태를 최소로 변환할 것이며, 그 반대의 경우도 마찬가지일 것이다.임의의 숫자(1보다 큰 숫자)를 단자 0으로 나타낼 수 있다는 것은 언제나 1을 추가할 수 있다는 것을 의미하며, 1과 2를 피보나치 부호화에서 나타낼 수 있다는 것을 감안할 때 완전성은 유도에 의해 뒤따른다.

참고 항목

• 오스트로우스키 숫자

참조

외부 링크

• Weisstein, Eric W. "Complete Sequence". MathWorld.