덧셈 체인

수학에서, 양의 정수 n을 계산하기 위한 추가 체인은 1로 시작하고 n으로 끝나는 자연수의 순서에 의해 주어질 수 있다. 이렇게 해서 순서의 각 숫자는 이전의 두 숫자의 합이다.덧셈 체인의 길이는 모든 숫자를 표현하는 데 필요한 합계의 수로서, 숫자 순서의 카디널리티보다 1이 적다.^[1]

예

예를 들어 (1,2,3,6,12,24,30,31)은 길이 7의 31에 대한 추가 체인이다.

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

덧셈 체인은 덧셈 체인 지수를 위해 사용될 수 있다.이 방법은 정수 지수를 사용한 지수를 지수에 대한 추가 체인 길이와 동일한 수의 곱을 사용하여 수행할 수 있도록 한다.예를 들어, 31에 대한 추가 체인은 반복 곱셈에서 얻을 수 있는 30 곱셈과 제곱에 의한 지수를 갖는 8 곱셈 대신에 7 곱셈만을 사용하여 임의 숫자의 n의 31번째 검정력을 계산하는 방법으로 이어진다.

n² = n × n

n³ = n² × n

n⁶ = n³ × n³

n¹² = n⁶ × n⁶

n²⁴ = n¹² × n¹²

n³⁰ = n²⁴ × n⁶

n³¹ = n³⁰ × n

추가 체인 계산 방법

최소 길이의 추가 사슬을 계산하는 것은 쉽지 않다; 각각의 일련의 값들을 동시에 형성하는 사슬을 찾아야 하는 문제의 일반화된 버전은 NP-완전하다.^[2]합리적인 타이밍이나 작은 메모리 사용량을 보장하면서 주어진 숫자에 대한 최소 추가 체인을 계산할 수 있는 알려진 알고리즘은 없다.그러나, 몇몇 기법들은 항상 최적의 것은 아닌 비교적 짧은 체인을 계산하는 것으로 알려져 있다.^[3]

비교적 짧은 덧셈 체인을 계산하는 잘 알려진 기법 중 하나는 제곱에 의한 지수와 유사한 이항법이다.In this method, an addition chain for the number ${\displaystyle n}$ is obtained recursively, from an addition chain for ${\displaystyle n'=\lfloor n/2\rfloor }$. If ${\displaystyle n}$ is even, it can be obtained in a single additional sum, as ${\displaystyle n=n'+n'}$. If ${\displaystyle n}$${\$$displaystyle$ $n$$}$은(는) 이상이며, 이 ${\displaystyle {}^{}}$은 $n{\displaystyle }$- ${\displaystyle 1}$= n ${\displaystyle {\prime }^{}}$+ $′$을 계산한 다음 하나를$$ $추가$하여 두 개의 합을 사용하여 얻는다.^[3]

추가 체인을 찾기 위한 인자 방법은 표시할$$ 숫자 $n{\displaystyle }$ ${\displaystyle n}$의 주요 인자화에 기초한다.$n{\displaystyle }$ ${\displaystyle n$$}$이(가) 주요 $요인{\displaystyle }$중 $하나$로 p {\$displaystyle$ p}을$$(를) 가지고$$ 있는 $경우{\displaystyle }$ n${\displaystyle /p}${\$displaystyle$n/$p}$을(를) 위한 체인으로 시작한 다음$,$ 각 숫자를 곱하여 수정된$$$p{\displaystyle }$ ${\displaystystyle p}$을(를) 위한 체인으로 $연결$하면$$n {\$displaystyp)$에 대한 추가 체인을 얻을 수 있다$$.$bers{\displaystyle by}$n / p {\$displaystyle$ n/p$\}.$ 인자 방법과 이진법의 아이디어는 임의의 $숫자{\displaystyle }$ m ${\displaystyle m}$을(를) 선택하여 Brauer의 m-ary 방법으로 결합할 수 있다($$$n{\displaystyle }$ ${\displaystyle$ n$}$을(를) $$$\lfloor {\displaystyle }$ ${\displaystyle n}$/ $m ⌋$에 대한 체인을 재귀적으로 구성한다$($$nm\displayplayplayplayplayplaystate$).$m{\displaystyle }$ ${\displaystyle m}($위의 것과 동일한 방식으로 표시됨)에 체인을 적용하여 $m{\displaystyle }$ ${\displaystyle \lfloor n}$/ ${\displaystyle m}$ ${\displaystyle \rfloor }$ ${\displaystyle m\lllloor n/m\$m\$loor }$을$($를) 얻은 후 나머지를 추가하십시오.$$이러한 사상의 추가적인 개선은 슬라이딩 윈도우 방식이라 불리는 방법의 가족으로 이어진다.^[3]

체인 길이

$l{\displaystyle }$(${\displaystyle n}$) ${\displaystyle l(n)}$이(가) $가장{\displaystyle }$ 작은 $s{\displaystyle }$ ${\displaystyle s}$을(를) 나타내도록$$$$ 하여 n ${\displaystyle n}$을(를) 계산하는$$ $길이{\displaystyle }$ s ${\displaystyle s}$의 추가 체인이 존재하도록 한다$.$

${\displaystyle \log _{2}(n)+\log _{2}(\nu (n))-2.13\leq l(n)\leq \log _{2}(n)+\log _{2}(n)(1+o(1))/\log _{2}(\log _{2}(n))}$,

여기서 $\nu {\displaystyle (n}$ ${\displaystyle )}$ ${\displaystyle \nu(n)}$은(는) $n{\displaystyle }$ ${\displaystyle n}$의 이진 확장에 대한 해밍 가중치(하나의 수)이다$.$^[4]

One can obtain an addition chain for ${\displaystyle 2n}$ from an addition chain for ${\displaystyle n}$ by including one additional sum ${\displaystyle 2n=n+n}$, from which follows the inequality ${\displaystyle l(2n)\leq l(n)+1}$ on the lengths of the chains for ${\displayst$$yle n}$과 ${\displaystyle \mathrm{2n}}$ ${\displaystyle 2n$ 그러나 경우에 따라 ${\displaystyle \mathrm{2n}}$ ${\displaystyle 2n}$이(가) 이러한 방식으로 얻은 체인보다 짧은 체인을 가질 수 있기$$ 때문에 이것이 항상 동일하지는 않다.예를 들어, Knuth가 관찰한 $l{\displaystyle }$(${\displaystyle 382}$)${\displaystyle }$= l${\displaystyle }$(${\displaystyle 191}$)${\displaystyle }$= ${\displaystyle 11}$ ${\displaystyle l(382)=l(191)=11$^[5]2n{2n\displaystyle}n{n\displaystyle}보다 더 짧은 사슬이 있기 때문에 내가(2n)그것은 심지어,<>l(n){\displaystyle l(2n)<, l(n)};이 일어난 가장 작은 n{n\displaystyle}=는 602641031가 뒤따릅니다 375494703{\displaystyle n=375494703},[6]{\display n가능성이 있다.스타일 60$2641031$ ${\displaystyle 619418303}$ ${\displaystyle 619418303}$등(OEIS의 시퀀스 A230528).

브라워 체인

브라우어 체인 또는 별첨사슬은 각각의 숫자를 계산하는 데 사용된 합계가 바로 이전의 숫자를 사용하는 덧셈사슬이다.브루어 번호는 브루어 체인이 최적인 숫자다.^[5]

브라워는 그것을 증명했다.

l^*(2ⁿ−1) ≤ n − 1 + l^*(n)

$여기$서 l$∗{\$는 최단 항성 체인의 길이다.n의 많은 값과 특히 n < 12509의 경우, ^[7]l(n) = l(n^*)의 값이 같다.그러나^* 한센은 n = 2 + 2⁶¹⁰⁶ + 2^30482032 + 2 + 1과²⁰¹⁶ 같이 l^*(n) = 6110, l(n) ) 6109가 있는 n의 값이 있음을 보여주었다.가장 작은 n은 12509이다.

숄츠 추측

아놀드 숄츠와 알프레드 T.브라워의 이름을 딴 숄츠-브라워 또는 브라우어-숄츠 추측으로 불리기도 한다) 숄츠 추측은 1937년부터 다음과 같이 진술한 추측이다.

${\displaystyle l(2^{n}-1)\leq n-1+l(n)}$

이 불평등은 브루어 숫자의 일반화인 모든 한센 숫자를 지탱하는 것으로 알려져 있다; 니일 클리프트는 컴퓨터로 n${\displaystyle }n{\displaystyle }$ $[\displaystyle n\leq 5784688}$이 모두 한센( 반면에$$ 5784689는 그렇지 않다)^[6]이라는 것을 확인했다.Clift는 실제로 $l{\displaystyle }$ (${\displaystyle \mathrm{2n}{}^{}}$- 1${\displaystyle }$)${\displaystyle }$= ${\displaystyle n}$- ${\displaystyle 1}$+ l${\displaystyle }$(${\displaystyle n}$) ${\displaystyle$ l $(2^{n}-1)=n-1+l(n)}$ $모든{\displaystyle }$ n${\displaystyle 64}$ 64$${\$displaystyle n\leq$64$\}$^[5]에 대해 추가로 검증했다.

참고 항목

• 덧셈-굴절 체인
• 벡터 덧셈 체인
• 루카스 체인

참조

• Brauer, Alfred (1939). "On addition chains". Bulletin of the American Mathematical Society. 45 (10): 736–739. doi:10.1090/S0002-9904-1939-07068-7. ISSN 0002-9904. MR 0000245.
• Richard K. Guy (2004). Unsolved Problems in Number Theory. Springer-Verlag. ISBN 978-0-387-20860-2. OCLC 54611248. Zbl 1058.11001. C6절.

외부 링크

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• OEIS 시퀀스 A003313(n의 경우 최단 추가 체인 길이).초기 "1"은 계산되지 않는다는 점에 유의하십시오(따라서 시퀀스의 #1 요소는 0임).
• F. 버거론, J. 버스텔S. Brlek "추가 체인의 효율적인 계산"