頁籤選單縮合
題 名 | 正整數分解成正等差數列和之研究=Decompose a Positive Integer into an Arithmetic Series |
---|---|
作 者 | 李銘城; | 書刊名 | 龍華科技大學學報 |
卷 期 | 18 民94.06 |
頁 次 | 頁91-95 |
分類號 | 313 |
關鍵詞 | 等差數列; 偶數等差數列; 奇數等差數列; 連續整數和; 公差; Arithmetic series; Sum of continuous integer; Even arithmetic series; Odd arithmetic series; Common difference; |
語 文 | 中文(Chinese) |
中文摘要 | 假設N是一個正整數,如何將N分解成一個一個公差為2的正等差數列,也就是說對於任一正整數N,是否存在一個公差為2的正等差數列,其數列和恰好等於N,當然,其解可能存在一組以上,也可能無解。 如果使用窮舉法來尋找所有解的話,其時間複雜度為O(N),我們順利的將此問題轉化成因數分解的問題,我們發現到如果N存在二個正整數的因數,則存在一組對應的解,而且彼此為充分必要條件。因為因數分解的時間複雜度為O(√N),從演算法的角度而言,程式執行的效能獲得顯著的改進。 以下定理是關於正整數與等差數列的關係式,定理二和定理三是尋找公差為2的正等差數列;定理四則是關於演算法複雜度的探討;推論二則告訴我們,任何質數均不存在公差為2的正等差數列。 |
英文摘要 | Assume N is a positive integer, how to decompose N into an arithmetic series with common difference 2, i.e., if there exist an arithmetic series with common difference 2 and its sum is equal to N. The solution possibly does not exist. In general, the time complexity to find al 1 the solution is O(N). Now we reduce this problem into a factor problem. If we can find two positive integers that their product is equal to N, then a relative arithmetic series with common difference 2 exists. The time complexity is down to O(√N). It is a very good result from the view point of computer algorithms. There are three theorems and one corollary in this article. Theorem 2,3 are about how to find arithmetic series with common difference 2. Theorem 4 is about the time complexity of computer algorithms. Corollary 2 said that all the prime numbers can be a sum of arithmetic series with common difference 2. |
本系統中英文摘要資訊取自各篇刊載內容。