이집트 분수에 대한 탐욕 알고리즘

수학에서 이집트 분수에 대한 탐욕스러운 알고리즘은 피보나찌가 처음으로 설명한 합리적 숫자를 이집트 분수로 변형시키기 위한 탐욕스러운 알고리즘이다. 기약 분수의.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output.sfrac.tion,.mw-parser-output.sfrac .tion{디스플레이:inline-block, vertical-align:-0.5em, font-size:85%;text-align:센터}.mw-parser-output.sfrac .num,.mw-parser-output.sfrac .d 같은 뚜렷한 단위 분수의 합으로 한 이집트 소수 부분은 표현입니다.En{디스플레이:블록, line-height:1em, 마진:00.1em}.mw-parser-output.sfrac .den{border-top:1px 고체}.mw-parser-output .sr-only{국경:0;클립:rect(0,0,0,0), 높이:1px, 마진:-1px, 오버 플로: 숨어 있었다. 패딩:0;위치:절대, 너비:1px}5/6)1/2+1/3. 이름에서 알 수 있듯이, 이러한 표현은 고대 이집트만큼이나 오래 전에 사용되었지만, 그러한 확장을 건설하기 위한 최초의 체계적인 방법은 피사의 레오나르도(피보나치)의 리베르 아바시(1202)에 기술되어 있다. 알고리즘은 각 단계에서 나머지 분수의 어떤 표현에도 사용될 수 있는 가능한 가장 큰 단위 분율을 탐욕스럽게 선택하기 때문에 탐욕스러운 알고리즘이라고 불린다.

피보나찌는 실제로 이집트 분수표현을 위한 몇 가지 다른 방법들을 열거한다(Sigler 2002, 챕터 II.7). 그는 몇 가지 간단한 방법들이 실패하는 상황에 대한 마지막 수단으로 탐욕스러운 방법을 포함시킨다. 이러한 방법들에 대한 더 자세한 목록은 이집트 분수를 참조하라. 살저(1948)의 세부사항처럼, 비합리적인 숫자의 근사치에 대한 탐욕스러운 방법 및 그 연장법은 현대 수학자들에 의해 여러 번 재발견되었는데, 가장 초창기에 그리고 가장 두드러지게 J. J. 실베스터(1880)에 의해 발견되었다. 예를 들어 카헨(1891), 스피어스(1907)를 참조하라. 합계의 일부 단위 분수를 음수 값으로 허용함으로써 각 단계에서 더 가까운 근사를 생성하는 밀접하게 연관된 팽창 방법은 램버트(1770)로 거슬러 올라간다.

숫자 x에 대해 이 방법에 의해 생성된 확장을 욕심 많은 이집트 팽창, 실베스터 팽창 또는 x의 피보나치-실베스터 팽창이라고 한다.그러나 피보나치 팽창이라는 용어는 보통 이 방법이 아니라 정수를 피보나치 숫자의 합으로 표현하는 것을 말한다.

알고리즘 및 예제

피보나치의 알고리즘은 교체를 반복적으로 수행함으로써 나타낼 분율 x/y를 확장한다.

${\displaystyle {\frac {x}{x}}={\frac {1}{\좌측\lceil {\frac {1}{x}\우측\rceil }}}+{\frac{-y}}{\좌측\lceil {x}{x\lceil}}}}}}}}}}}$

(필요에 따라 이 교체의 두 번째 임기). 예를 들어,

${\displaystyle {\frac {7}{15}}={\frac {1}{1}{3}}+{\frac {1}{15}={\frac {1}{3}+{8}}{\frac {1}{120}}}}.}$

이 팽창에서 1단위의 분모 3은 15/7을 다음으로 큰 정수로 반올림한 결과이며, 나머지 2/15는 -15 mod 7/15 × 3 = 6/45를 단순화한 결과물이다. 두 번째 단위 분율 8의 분모는 15/2를 다음 큰 정수로 반올림한 결과이며, 나머지 1/120은 1/3과 1/8을 모두 뺀 후 7/15에서 남은 것이다.

각각의 팽창 단계가 팽창할 나머지 분수의 분자를 감소시키므로, 이 방법은 항상 유한한 팽창으로 끝나지만, 고대 이집트의 팽창이나 보다 현대적인 방법에 비해 이 방법은 분모가 큰 상당히 긴 확장을 만들어 낼 수 있다. 예를 들어, 이 방법은 확장된다.

${\displaystyle {\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763\,309}}+{\frac {1}{873\,960\,180\,913}}+{\frac {1}{1\,527\,612\,795\,642\,093\,418\,846\,225}},}$

다른 방법들이 훨씬 더 나은 확장으로 이어지는 동안

${\displaystyle {\frac {5}{5}}={\frac {1}{1}{33}+{\frac {1}{1}{363}}.}$

왜건(1991년)은 31/311이라는 훨씬 더 나쁜 행동의 예를 제시한다. 탐욕스러운 방법은 10개의 항으로 확장되는데, 그 중 마지막 항은 분모에 500자리 이상이지만 31/311은 1/12 + 1/63 + 1/2799 + 1/8708로 훨씬 짧은 비자유 표현을 가지고 있다.

실베스터의 수열과 가장 가까운 근사치

실베스터의 순서 2, 3, 7, 43, 1807, ...(OEIS: A000058)는 숫자 1에 대해 이러한 유형의 무한한 탐욕적인 확장에 의해 생성된 것으로 볼 수 있으며, 여기서 각 단계에서 분모인 y y/x ⌉ 대신 ⌊ y/x + + 1을 선택한다. 이 시퀀스를 k 용어로 자르고 해당하는 이집트 분수를 형성함(예: (k = 4)

${\displaystyle {\frac {1}{1}:{1}:{1}{1}:{3}+{\frac {1}{1}{7}}}{\frac {1}}={\frac {1805}{1806}}}}}}$

k-ter 이집트 분수에 의해 가능한 가장 가까운 1을 과소평가한다(Curtiss 1922; Soundarajan 2005). 즉, 예를 들어 개방 간격(1805/1806, 1)의 숫자에 대한 이집트 분수는 최소 5개의 항을 필요로 한다. 커티스(1922년)는 이러한 가장 근접한 결과의 적용에 대해 완벽한 수의 구분자 수를 낮게 제한하는 것을 기술하고, 스퉁(1983)은 집단 이론으로 응용을 기술한다.

최대 길이 확장 및 결합 조건

x/y 분수는 탐욕스러운 팽창에서 최대 x항까지 필요로 한다. Mays(1987년)와 Freitag & Phillips(1999년)는 탐욕스러운 방법이 x/y의 확장을 생성하는 조건을 정확히 x 항으로 조사한다. 이러한 조건은 y의 합치조건으로 설명할 수 있다.

• 모든 1/y 분수는 탐욕스러운 팽창에서 하나의 용어를 필요로 한다; 가장 단순한 분수는 1/1이다.
• 모든 분수 2/y는 y ≡ 1 (mod 2)인 경우에만 탐욕스러운 팽창에서 두 개의 용어를 요구한다. 가장 간단한 분수는 2/3이다.
• 분수 3/y는 y 1 1 (mod 6)에 대해 -y mod x = 2와 y(y + 2)/3이 홀수인 경우에만 탐욕스러운 확장에 3개의 항이 필요하다. 따라서 한 번의 탐욕스러운 확장 후에 남은 분수는

${\displaystyle {\frac(-y){\bmod {x}{y}}{x}\right\rceil }}}={\frac {2},{\frac {y(y+2)}{3}}}\,}}}$

가장 간단한 용어로. 3개월 확장 시 가장 간단한 분율 3/y는 3/7이다.

• 분수 4/y는 y ≡ 1 또는 17 (mod 24)인 경우에만 탐욕스러운 팽창에서 4개의 항이 필요하다. 그 경우 나머지 분수의 분자 -y mod x는 3이고 분모는 1 (mod 6)이다. 4개월 확장의 가장 간단한 분수 4/y는 4/17이다. Erdős-Straus 추측에 따르면 모든 분수는 3개 이하의 항으로 팽창하지만 y ≡ 1 또는 17 (mod 24)이 있을 때 그러한 팽창은 17 (mod 24) 사례가 일치 관계 2 (mod 3)에 의해 다루어지는 탐욕스러운 알고리즘 이외의 방법으로 발견되어야 한다.

일반적으로 x-항 탐욕 팽창이 있고 각 x에 대해 가능한 가장 작은 분모 y를 갖는 분율 x/y의 순서는 다음과 같다.

${\displaystyle 1,{\frac {2}{3}},{\frac {3}{7}},{\frac {4}{17}},{\frac {5}{31}},{\frac {6}{109}},{\frac {7}{253}},{\frac {8}{97}},{\frac {9}{271}},\dots }$ (sequence A048860 in the OEIS).

다항근의 근사치

스트레이트마이어(1930)와 살저(1947)는 탐욕스러운 방법을 바탕으로 다항식의 뿌리에 대한 정확한 근사치를 찾는 방법을 설명한다. 그들의 알고리즘은 한 뿌리의 탐욕스러운 확장을 계산한다. 이 팽창의 각 단계에서 그것은 확장될 남은 분수를 그것의 뿌리로 가지고 있는 보조 다항식을 유지한다. 다항식 P₀(x) = x - x² - 1 = 0의 두 해법 중 하나인 황금 비율의 탐욕스러운 확장을 찾기 위해 이 방법을 적용하는 예를 들어보자. Stratemeyer와 Salzer의 알고리즘은 다음과 같은 단계의 순서를 수행한다.

1. p₀(x) < x = 1은 0, 모든 x x 2는 P₀(x) > 0이므로 1과 2 사이에는₀ P(x)의 루트가 있어야 한다. 즉, 황금비율의 탐욕스러운 확대의 첫 번째 임기는 1/1이다. x가₁ 탐욕스러운 팽창의 첫 번째 단계 이후의 잔여분이라면 P₀(x₁ + 1) = 0이라는 방정식을 만족시켜 P₁(x₁) = x²
   ₁ + 1₁ = 0으로 확장할 수 있다.
2. P₁(x) < x = 1/2이면 0, 모든 x > 1이면 P₁(x) > 0이기 때문에 P의₁ 뿌리는 1/2과 1/1 사이에 있고, 탐욕스러운 팽창의 첫 번째 용어(황금 비율 탐욕스러운 팽창의 두 번째 용어)는 1/2이다. x가₂ 욕심쟁이 팽창의 이 단계 뒤에 남은 분수라면₁ P(x₂ + 1/2) = 0이라는 방정식을 만족시켜₂ P(x₂) = 4x²
   ₂ + 8x₂ - 1 = 0으로 확장할 수 있다.
3. p₂(x) < x = 1/9이면 0이고, p(x) > 1/8이면 모두₂ 0이므로 탐욕스러운 팽창의 다음 기간은 1/9이다. x가₃ 욕심쟁이 팽창의 이 단계 이후의 잔여분수라면₂ P(x₃ + 1/9) = 0 등식을 만족시켜 다시 정수계수 P₃(x₃) = 324x²
   ₃ + 720x₃ - 5 = 0을 갖는 다항식으로서 확장될 수 있다.

이 근사 과정을 계속하면 결국 황금 비율에 대한 탐욕스러운 확장이 발생한다.

${\displaystyle \varphi ={\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots }$ (sequence A117116 in the OEIS).

기타 정수 시퀀스

작은 분자와 분모가 있는 모든 분수에 대한 탐욕스러운 팽창의 길이, 최소 분모, 최대 분모는 각각 OEIS: A050205, OEIS: A050206, OEIS: A050210 순서에 따른 정수 시퀀스 온라인 백과사전에서 찾을 수 있다. 게다가, 어떤 비합리적인 숫자의 탐욕스러운 확장은 무한히 증가하는 정수의 순서를 초래하며, OEIS는 잘 알려진 상수 몇 개의 확장을 포함한다. OEIS의 일부 추가 항목은 탐욕스러운 알고리즘에 의해 생산된 것으로 라벨이 지정되지는 않았지만 동일한 유형으로 나타난다.

관련 확장

일반적으로 분모가 어떤 식으로든 제약을 받는 이집트 분수 확장을 원한다면 각 단계에서 확장을 선택하는 탐욕스러운 알고리즘을 정의할 수 있다.

${\displaystyle {\frac {x}{y}}={\frac {1}{d}+{\frac {xd-y}{yd}},}$

여기서 d는 제약조건을 만족하는 모든 가능한 값 중에서 xd > y 및 d가 이전에 선택한 모든 분모와 구별되는 가능한 한 작은 값으로 선택된다. 예를 들어, 엥겔 팽창은 각각의 연속 분모가 이전 분모의 배수가 되어야 하는 이 유형의 알고리즘으로 볼 수 있다. 그러나 이러한 유형의 알고리즘이 항상 유한 확장을 찾는 데 성공할 수 있는지 여부를 판단하기는 어려울 수 있다. 특히 분수 x/y의 이상 탐욕스러운 팽창은 모든 분모가 홀수일 수밖에 없는 이런 유형의 탐욕스러운 알고리즘에 의해 형성된다. y가 홀수일 때마다 모든 분모가 홀수일 때 유한한 이집트 분수 확장이 존재한다고 알려져 있지만, 홀수 욕심의 확장이 항상 피니인지는 알 수 없다.te.

참조