数論 素数の求め方(サンダラムの篩(ふるい))
エラトステネスの篩(ふるい)を少し改良したサンダラムの篩(ふるい)をつかって素数をもとめます。サンダラムの篩をつかって奇素数を求めます。２を追加すれば素数リストになります。エラトステネスの篩を使った方法より２倍ぐらい処理とメモリ使用に関して...
数論
数論 数論 素数の求め方
サンダラムの篩を使った方法はこちらにあります。素数の判定なにか与えられた自然数が素数かどうか判定するには、その数の約数を調べればわかります。約数を調べるためには、その数以下の自然数で割ってみて、割り切れているかどうかで調べます。例えば、５３...
代数 n^4+n^2+1が素数となるときの整数nは？(素数になりにくい多項式)
問題\(n^4+n^2+1\)が素数となるときの整数nの値をもとめよ。素数かどうか、nにいろいろ代入していけばわかるのですが、・・・。解答例因数分解できることがミソです。\(n^4+n^2+1\)\(=(n^4+2n^2+1)-n^2\)\...
代数 数を作るのに必要な事
数とは何かを考えるのは、実は数を作るためである。新しい数を作るために、数が必要であることは述べた。その数として自然数を使うのが基本であることを述べた。ただ、あまり抽象的な話しばかりしても、生産的でないので、もっと具体的な話をしよう。数の定義...
数論 数の起源
数は、階層構造を持っていることは前にかいた。すなわち、新しい数は古い数をもって定義できる。数の起源をたどっていくと、1にたどり着く。1の裏には0がある。数の起源数の起源をたどってみよう。まずは、一番身近な有理数。有理数は(有理)整数から定義...
代数 東大数学2017年前期第4問(整数漸化式)
ルート（√）がありますが、これは整数問題です。ちょっと変則的な数学的帰納法を使います。最後の方で、この問題の「発展」についても記載しました。ただ解くだけではつまらないですから。問題\(p=2+\sqrt{5}\)とおき、自然数n=1,2,3...
代数 数学的帰納法の変化形
数学的帰納法の簡単な変化形数学的機能法の変化形（１）まず、簡単にわかるのは、最初のn=1の場合をn=0にしたり、n=2にすることです。(1) n=2の場合に成立。(2) n=kの場合が成立するならn=k+1の時も成立する。(3) 上記の(1...
代数 数学的帰納法とは
数学的帰納法とは数学的帰納法とは、数学の命題を証明する時に使う手法の一つです。任意の自然数nに関する命題を証明するときに使います。証明方法自然数nに関する命題を数学的帰納法で証明するときには、下記の２つのことを証明します。(1) n=1の場...
数論 約数の総和を求める関数は乗法的である
約数関数約数関数とは、約数の総和を返す関数のことです。定義をきちんと書くと、下記のようになります。自然数nに対し、そのnの約数全ての総和を返す関数を約数関数と呼び、σ(n)で表す。例えば、σ(1)=1σ(2)=1+2=3σ(3)=1+3=4...
数論 メルセンヌ素数
メルセンヌ素数と完全数の定義自然数nに対して\(M_n=2^n-1\)の形で表される素数をメルセンヌ素数と呼ぶ。自然数nに対してnのnより小さい約数の和がnであるとき、nを完全数よ呼ぶ。完全数の例：6, 28, 496, 8128 など問題...