재 방문 $(W^2 + X^2 + Y^2 + Z^2) = (A^2 + B^2)$
이 쿼리는 다음 쿼리에 대한 응답 중 일부에 의해 분류 된 좁은 질문을 제공합니다. Can a sum of$n$ 제곱은 다음의 합으로 표현됩니다. $n/2$ 사각형?
내가 구체적으로 묻는 질문이 위의 참조 된 쿼리의 OP에 의해 의도 된 것인지 확실하지 않습니다. 어쨌든...
두 개의 고정 된 양의 정수가 주어지면$A$ 과 $B$,
모든 양의 정수 솔루션 찾기
$(W^2 + X^2 + Y^2 + Z^2) = (A^2 + B^2)$
내가 찾고있는 것은 분석 + 특정한 경우와는 반대로 일반적인 경우에 적용 할 우아한 알고리즘입니다 [예 : $(A^2 + B^2)$특정 숫자 미만입니다]. 아래는 제가 생각 해낼 수있는 유일한 (추악한) 알고리즘입니다. 이 알고리즘에는 컴퓨터 지원이 필요한 것 같습니다.
이 알고리즘을 개선 할 수 있습니까? 특히 적절한 분석을 통해 컴퓨터 지원 없이도 일반적인 문제 를 해결할 수 있습니다 .
또는 우아한 알고리즘이 없다고 가정합니다. 이 경우
(1) 솔루션이 존재하기 위해 필요한 조건을 식별 할 수 있습니다. (2) 솔루션이 존재
하기에 충분한 조건을 식별 할 수 있습니다.
(3) (1)과 (2) 둘 다
$\underline{\textbf{my ugly algorithm}}$
허락하다 $C = (A^2 + B^2)$.
허락하다$S = \{(i,j) : i,j \in \mathbb{Z^+}, i \leq j, (i + j) = C\}.$
의 각 요소를 살펴보십시오. $S$ 개별적으로 모든 솔루션 식별 $(W,X,Y,Z)$각 요소에 대해. (A)에 의해 솔루션 , 나는 다음 세 가지 중 하나를하려는 :
(ㅏ) $W^2 = i$ 과 $(X^2 + Y^2 + Z^2) = j.$
(비) $W^2 = j$ 과 $(X^2 + Y^2 + Z^2) = i.$
(씨) $(W^2 + X^2) = i$ 과 $(Y^2 + Z^2) = j.$
개별 요소를 검사 할 때 $S$, 아래 "개별 요소 검사"섹션의 알고리즘을 따릅니다. 이 쿼리는 "Pythagorean Triplets 주변 분석"섹션으로 종료됩니다. 제안 할 수있는 최선 의 방법은이 쿼리의 닫는 섹션과 유사한 특수 사례를 더 추가하는 것 입니다.
개별 요소 검사
둘 다 $i$ ...도 아니다 $j$완전 제곱이되면 (a) 및 (b) 유형의 해가 즉시 제거됩니다. 다음 중 하나가$i$ 과 $j$완벽한 정사각형입니다. 나는 (예를 들어) Diophantine이$(X^2 + Y^2 + Z^2) = j$ (와 $j$고정 된 숫자)는 풀 수 있으며, 그렇다면 가능한 모든 솔루션을 식별하는 방법. 그런 분석이 없다고 가정하면 디오 판틴을 공격 할 방법이 없다고 생각합니다$(X^2 + Y^2 + Z^2) = j$ 컴퓨터 검색 외에.
이 섹션의 나머지 부분에서는 $i$ 또는 $j$완전한 제곱이고, 유형 (c)의 해를 찾을 것입니다. 가능한 모든 피타고라스 세 쌍둥이 생성에 대한 (초등 수 이론) 분석을 보았지만이 분석이 (예를 들어) 디오 판틴에 대해 어떻게 사용될 수 있는지는 불분명합니다.
$(W^2 + X^2) = i$,
어디서$i$ 완전 제곱 일 수도 있고 아닐 수도있는 고정 된 양의 정수입니다.
유형 (a)와 (b)의 해법을 찾는 것과 같이, 유형 (c)에 관련된 디오 판틴에 대한 분석을 가져올 수 없다면 (다시) 컴퓨터 검색이 불가피하다고 생각합니다.
피타고라스 삼중 항에 대한 분석
예를 들어 다음과 같은 특정 요소를 고려할 때 $S$, 그 $i$ 완벽한 제곱입니다 (예 : $i = k^2$).
그런 다음 피타고라스 세 쌍둥이 생성에 대한 분석이 호출 될 수 있습니다. 즉,이 경우이 특정 요소를 포함하는 (c) 유형의 솔루션은$S$ 피타고라스 삼중 항을 포함해야합니다.
$W^2 + X^2 = k^2.$
즉, 그러한 피타고라스 삼중 항이 불가능하다는 것을 입증 할 수 있다면 $k^2$, 그러면 S의이 특정 요소에 대해 유형 (c) 솔루션이 불가능하다는 것을 확인했습니다. 또한 가능한 모든 솔루션을 열거 할 수 있다면
$W^2 + X^2 = k^2$,
이 특정 요소에 대한 모든 유형 (c) 솔루션$S$ 이러한 피타고라스 삼중 항 용액 중 하나를 포함해야합니다.
그러나 여기에서도 $j$ 당신은 여전히 풀어야 할 완벽한 사각형이 아닙니다. $Y^2 + Z^2 = j.$
추가
John Omielan의 답변에서 "Lagrange의 4 제곱 정리"링크를 탐색하는 동안 저는 두 제곱 의 합 정리를 기반으로 알고리즘 을 적당히 개선 하는 방법을 발견했습니다 . 또는 아마도 정리를 잘못 읽은 것 같습니다.
특정 요소에 대해 $(i,j) \in S,$ 둘 다 $i$ ...도 아니다 $j$완벽한 정사각형입니다. 그러면이 요소를 활용할 수있는 유일한 솔루션은 (c) 유형입니다. 둘 중 하나라면$i$ 또는 $j$ "두 제곱합"정리의 기준에 실패하면 S의이 특정 요소를 사용하여 해를 생성 할 수 없습니다.
또는 $i$ 과 $j$ 둘 다 "두 제곱합"정리의 기준을 통과하면이 특정 요소를 사용하여 하나 이상의 유형 (c) 솔루션 (및 아마도 둘 이상)이 가능할 것입니다. $S$.
부록 -2
부록에 링크 된 "두 제곱 정리의 합"은 "피타고라스 삼중 체 분석"섹션의 토론에도 (간접적으로) 영향을 미칩니다. 특정 요소에 대해$(i,j) \in S,$ 그 $i$ 완벽한 제곱입니다 (예 : $i = k^2$).
또한 (현재로서는)이 요소에 대한 (가능한) 유형 (c) 솔루션만을 탐색하고 있다고 가정합니다 (유형 (a) 솔루션과 반대로).
또한 "피타고라스 삼중 항 분석"을 사용하여 적어도 하나의 솔루션이 있는지 확인했다고 가정합니다. $W^2 + X^2 = k^2.$
"피타고라스 삼중 체 주변 분석"섹션에 표시된 것처럼 여전히 $Y^2 + Z^2 = j$ 해결해야 할 디오 판틴.
만약 $j$ 또한 완벽한 정사각형 (예 : $j = l^2$), "피타고라스 삼중 항 분석"을 사용하여 $Y^2 + Z^2 = l^2$ 디오 판틴.
또는 $j$ 완전한 제곱이 아니라면 "두 제곱의 합 정리"를 사용하여 $Y^2 + Z^2 = j$ 디오 판틴.
부록 -3
부록 및 부록 -2 섹션의 대수학이 유효 해 보이지만 John Omielan의 답변에 따라 Steven Stadnicki가 게시 한 의견을 고려할 때이 두 섹션의 유용성에 의문을 제기합니다. 주어진 고정 정수$A$ 과 $B$둘 다 크고 부록 또는 부록 -2 섹션의 어떤 것도 특정 값과 관련된 특정 문제를 허용하지 않습니다.$A$ 과 $B$ 컴퓨터 지원없이 포괄적 인 공격을받을 수 있습니다.
결과적으로, 부록 및 / 또는 부록-2 섹션의 유용성을 평가하기 위해, 하나는 첫 번째 (내가 않는 스티븐 Stadnicki에 의해 참조 알고리즘 (들)의 컴퓨터의 효율성을 검토해야 하지 이해).
그런 다음 각 요소를 식별하는 비용을 고려해야합니다. $(i,j) \in S,$그리고 (아마도) "두 제곱의 합"정리를이 요소에 적용합니다. 이것은 각 요소에 대해$(i,j)$ (보통) 둘 다의 소인수 분해를 계산해야합니다. $i$ 과 $j$. 다른 고려 사항 중에서 이것은 소수 테이블이 필요하다는 것을 의미합니다.$\{1, 2, 3, 4, \cdots, [A^2 + B^2]\}.$
한 번에 하나 이상의 문제를 해결하는 경우 소수 테이블의 구성 비용이 어느 정도 "상각"될 수 있습니다. 어쨌든, 내 ( 맹인 ) 본능은 내 부록 및 부록 -2 분석이 아무것도 달성하지 못했을 수도 있다는 것입니다.
Addendum 및 Addendum-2 섹션에서 추가 한 분석의 유용성에 의문을 제기하고 있지만 John Omielan의 답변이 제공 한 분석의 유용성에 대해 유사하게 질문 하지 않습니다 . 이것은 그의 분석 (예 : 숫자의 잔류 물 mod 16 결정)이 컴퓨터 에 집중적이지 않은 것처럼 보이기 때문 입니다.
마지막으로이 (부록 -3) 섹션은 메타 치팅에 의해 동기가 부여되었음을 고백해야합니다 . Steven Stadnicki의 의견은 "토끼"가있을 가능성이 낮다는 것을 암시합니다. 학부 수준의 수 이론 (나)을 이해하고있는 사람이 방금 "두 제곱의 합"정리에서 일어난 일이 갑자기 바퀴를 재발 명 했다고 믿어야 합니까?
부록 -4 Arnold의 답변에서 사례 A에 대한 답변.
이 답변의 사례 A는 몇 가지 질문을 던지는 것 같습니다.
(1)
주어진 고정 된 양의 정수$(p,q)$ 와 $p^2 + q^2 = r,$
수 0이 아닌 정수 값$(a,b,c,d)$
그렇게 발견 되다$a^2 + b^2 + c^2 + d^2 = r$어디 동시에 A 경우의 패턴은 않습니다 하지 적용됩니다.
사례 A의 패턴이 적용되지 않는 상황은 다음 중 하나입니다.
(1a)
요소$\{a,b,c,d\}$페어링 할 수 없으므로 (예)
$(|a|+|b|) = p$ 과 $(|c|+|d|) = q.$
(1b)
요소$\{a,b,c,d\}$페어링 할 수 없으므로 (예)
$(ab + cd) = 0.$
(2)
바로 위의 (1) 주변의 어려움을 무시하고 사례 A의 분석을 큰 값에 적용 할 수 있습니까?$(p,q)$ 수동 (즉, 컴퓨터 지원이 사용되지 않는 곳)?
이것은 (예를 들어) ( 논란의 여지가 있지만 )$p$ 또는 $q$ 양의 정수를 모듈로 사용하면 소인수 분해를 계산할 수 없습니다. $p$ 또는 $q.~~$ 틀림없이 , 당신은 (또한) 소수 목록에 액세스 할 수 없습니다.
즉, $(p,q)$ fixed , 모든 만족스러운 세트 를 분석적으로 식별 해야 합니다.$[a,b,c,d]$ 0이 아닌 정수의 $(|a|+|b|) = p, ~ (|c|+|d|) = q, ~ \text{and} ~ (ab + cd) = 0.$
(3)
위 (1)의 어려움을 무시하고 사례 A에서 취한 접근 방식이 [위의 (2) 바로 위에 설명 된대로] 사용되었다고 가정하고이 접근 방식에 컴퓨터 지원 이 필요 하다고 가정하면 ) 질문은 다음과 같습니다.
사례 A 접근 방식의 컴퓨터 효율성은 John Omielan의 답변에 대한 Steven Stadnicki의 의견에서 참조한 알고리즘의 컴퓨터 효율성과 어떻게 비교됩니까?
답변
일반적인 경우의 모든 솔루션을 찾는 우아한 알고리즘이나 알고리즘을 개선하는 특별한 방법은 없습니다. 그럼에도 불구하고 Lagrange의 4 제곱 정리 상태에 유의하십시오.
Bachet의 추측 이라고도하는 Lagrange의 4 제곱 정리 는 모든 자연수가 4 개의 정수 제곱의 합으로 표현 될 수 있다고 말합니다.
그러나 여기에는 이러한 사각형 중 하나 이상이 $0$. 당신이 모든 것을 말했기 때문에$4$제곱은 양수 여야합니다. 고유성 섹션에는 0이 아닌 네 개의 제곱 의 합으로 표현할 수없는 유일한 양의 정수 는 다음과 같습니다.
... 8 개의 홀수 $1, 3, 5, 9, 11, 17, 29, 41$ 및 양식의 모든 번호 $2(4^{k}),6(4^{k})$ 또는 $14(4^{k})$.
따라서 $A^2 + B^2$ 이 숫자 중 하나가 아닙니다 (예 : $A = 1$ 과 $B = 2$ 그 이후로 해결책이 없다 $1 + 4 = 5$, 그리고 또한 $A = B = 2^{n}$ 어떠한 것도 $n \ge 0$해결책이 없음), 적어도 하나의 해결책이 있습니다. 이것은 솔루션이 존재하기 위해 요청한 필요하고 충분한 조건을 모두 제공합니다.
업데이트 : 이미 알고 있지 않은 경우, 질문에서 언급했듯이 알고리즘이 확인해야하는 횟수를 줄일 수있는 매우 간단하고 효율적인 방법이 몇 가지 있습니다. 예를 들어, 모든 완전 제곱은 다음 요소에 합동합니다.$\{0, 1, 4, 9\}$ 모듈로 $16$. 이것을 사용하여 확인할 수 있습니다.$i$ 경우 (a) 및 $j$ 당신의 경우 $b$.
또한 $2$ 정사각형은 다음의 요소에만 합동 할 수 있습니다. $\{0, 1, 2, 4, 5, 8, 9, 10, 13\}$ 모듈로 $16$, 확인하는 데 사용할 수 있습니다. $i$ 과 $j$ 귀하의 경우 (c).
마지막으로, 딕슨의 "숫자의 현대 초등 이론"책과 같이 표 5 , 식$ax^2 + by^2 + cz^2$, 어디 $a = b = c = 1$, 다음 형식의 양의 정수와 같을 수 없습니다. $A = 4^{k}(8n + 7)$. 이것을 사용하여 확인할 수 있습니다.$j$ 귀하의 경우 (a) 및 $i$ 귀하의 경우 (b).
우리는 항상 찾을 수 있습니다 $4$ 같은 사각형 $2$ 모든 항이 피타고라스 트리플의 일부인 경우 제곱 $A_1^2+B_1^2+A_2^2+B_2^2=C_1^2+C_2^2.$
유클리드의 공식부터 시작하겠습니다. $\quad A=m^2-k^2\quad B=2mk\quad C=m^2+k^2\quad$ 존재하는 경우 두 개의 트리플을 찾습니다. $C$-값. 한계 내에서 정수를 반환하는 C 값$m$ 제공합니다 $m,k$ 피타고라스 트리플을 생성하는 데 필요한 값.
$$C=m^2+k^2\implies k=\sqrt{C-m^2}\qquad\text{for}\qquad \bigg\lfloor\frac{ 1+\sqrt{2C-1}}{2}\bigg\rfloor \le m \le \lfloor\sqrt{C-1}\rfloor$$
하한은 $m>k$ 상한선은 $k\in\mathbb{N}$. 예를 들면 :
$$C=65\implies \bigg\lfloor\frac{ 1+\sqrt{130-1}}{2}\bigg\rfloor=6 \le m \le \lfloor\sqrt{65-1}\rfloor=8\quad\land \quad m\in\{7,8\}\Rightarrow k\in\{4,1\}\\$$ $$F(7,4)=(33,56,65)\qquad \qquad F(8,1)=(63,16,65) $$ 이 예에서는 두 쌍의 $A^2,B^2$ 추가되는 $65^2$ 그러나 우리는 합이되기를 원하지 않는 한 쌍 중 하나만 선택해야합니다. $2C^2$. 이제 다른 알려진 기술에 대해 동일한 기술을 사용하여$C$-값:
$$C=85\implies \bigg\lfloor\frac{ 1+\sqrt{170-1}}{2}\bigg\rfloor=7 \le m \le \lfloor\sqrt{85-1}\rfloor=9\quad\land \quad m\in\{7,9\}\Rightarrow k\in\{6,2\}\\$$ $$F(7,6)=(13,84,85)\qquad \qquad F(9,2)=(77,36,85)$$
이제 두 세트의 $A^2,B^2$ (하나 선택) $65^2$, 마찬가지로 $85^2$, 이들을 결합하는 네 가지 방법이 있습니다. 약간$C$-값은 하나 또는 여러 쌍을 갖습니다. $A,B$ 그러나 가치가 없다면 $m$ 정수를 산출 $k$, 그러면 트리플이 존재하지 않습니다. $C$-값.
우리는 다음과 같은 신원을 가지고 있습니다.
사례 A
$(a,b,c,d)^2=(p,q)^2$
어디, $(p,q)=[(a+b),(c+d)]$
그리고 조건은 : $(ab+cd=0)$
에 대한, $(a,b,c,d)=(9,7,-21,3)$ 우리는 얻는다 :
$(p,q)=(16,18)$
사례 B :
$(a,b,c,d,e,f)^2=(p,q,r)^2$
어디, $(p,q)=[(a+b),(c+d),(e+f)]$
그리고 조건은 : $(ab+cd+ef=0)$
에 대한, $(a,b,c,d)=(3,2,4,1,-10,1)$ 우리는 얻는다 :
$(p,q,r)=(5,5,9)$
사례 C :
$(a,b,c,d,e,f,g,h)^2=(p,q,r,s)^2$
어디, $(p,q)=[(a+b),(c+d),(e+f),(g+h)]$
그리고 조건은 : $(ab+cd+ef+gh=0)$
에 대한, $(a,b,c,d)=(15,13,12,9,8,4,-67,5)$ 우리는 얻는다 :
$(p,q,r,s)=(28,21,12,62)$
마찬가지로 방법을 적용 할 수 있습니다. $(2n)$ 사각형
LHS 및 받기 $(n)$ 모든 'n'&에 대한 RHS의 사각형
적절한 값 $(a,b,c,d,-----)$.
당신이 놓친 것은 효율성의 격차라고 생각합니다. 세트의 크기$S$ 선형이다 $N$, 어디 $N$2 개의 합과 4 개의 제곱의 합으로 동시에 표현되는 숫자입니다. 이것은 구성원을 통해 반복에 의존하는 모든 알고리즘을 의미합니다.$S$ 최고의 선형에서 시간이 걸립니다. $N$ 각 요소에 대해 수행해야하는 작업 수에 따라 더 오래 걸릴 수 있습니다.
이것은 표면적으로 나쁘지 않은 것처럼 보일 수 있지만 관점을 바꾸면 왜 '느린'지 이해하는 데 도움이 될 수 있습니다. 표준 2 진법 또는 10 진법 표기법을 사용하여 숫자를 '효율적으로'쓸 수 있기 때문에 숫자 이론 알고리즘의 경우 일반적으로 '효율적'이라고 생각 되는 것은 입력 숫자 의 로그 또는 동등하게 크기 ( ' 기억 '). 당신은에 포함되지 수 31415926복용하는없이 매우 긴 시간,하지만 당신은에 추가하는 방법을 알고 27182818작업의 단지 소수에. 또한 몇 단계 만 더 사용하면 두 숫자를 함께 곱할 수 있습니다. 특히,$n$-비트 수 — 즉, 크기 수 $\leq N=2^n$ — 할 수 있습니다 $O(n)$시각. 이것은$O(\log N)$조작되는 실제 숫자로 표현 될 때. 마찬가지로 순진한 곱셈은$O(n^2)$시간과 비슷한 시간에 분할이 가능하다는 것을 보여줄 수 있습니다. 지난 수십 년간 컴퓨터 과학에서 가장 근본적으로 중요한 결과 중 하나는 소수성 테스트가 테스트 된 숫자 의 길이 에 따라 시간 다항식으로 수행 될 수 있다는 결과였습니다.$O(n^k)$ 일부 지수 $k$.
이러한 용어로 생각하면 내 의견에서 언급 한 4 제곱 문제를 해결하는 알고리즘은 시간이 걸립니다 $O(n^2)$(아마 훨씬 더 작은 요인이 될 수 있습니다.) 반대로 알고리즘은 대략 시간이 걸립니다.$2^n$; 그건 기하 급수적으로 더 확률 알고리즘보다.
이것이 개념을 이해하는 데 도움이 되었기를 바랍니다.