メインメニュー
PR
facebook

Re: 十進BASICの有理数モード

投稿ツリー


このトピックの投稿一覧へ

FarSeer08

なし Re: 十進BASICの有理数モード

msg# 1.2.1.1.1.1.1.2
depth:
7
前の投稿 - 次の投稿 | 親投稿 - 子投稿.1 | 投稿日時 2017/6/2 19:53 | 最終変更
FarSeer08  常連   投稿数: 241
引用:
4ケタから1000桁まで調べるプログラムです。
(中略)
65桁で約数が極端に大きく、ここで多大な時間がかかりました。
(中略)
65 1265011073

ちょっと観察してみましょう。
同じような数が頻繁に出てきて入り乱れているようですが……よくみると、7, -, 11, -, 11, -, 7, ... などのパターンの繰り返しも見つかります。パターンを見るには、1つ前の素因数分解のプログラムの出力の方が良さそうです。

その前に表記を簡潔にするため、数列を


で定義します(ついでに、想定されている規則に[たぶん]反せずに含められる 11 も 101 の前に入っています)。

素因数分解の出力では、後のプログラムの出力で( 7 が先に見つかるので) 隠れていた 11 も出ています。



:

奇数番項(2k + 1, k = 0, 1, 2, ...)はすべて、11 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→奇数番項はすべて合成数であり、素数が含まれる可能性が残るのは、偶数番項で構成される部分数列内に絞られて「大きさ」は半分に。
(追記:最初の 11, 101 は素数ですけど、ここでは他の素数を探すと言う意味で)

同様にして



:
(4k + 2, k = 0, 1, 2, ...)番項はすべて、101 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→(4k + 2, k = 0, 1, 2, ...)番項はすべて合成数です。
{4k + 2| k = 0, 1, 2, ...}は、4 で割ると 2 余る自然数の集合です。前のステップで、素数候補は偶数番項に絞られましたが、このステップで 4 で割ると 2 余る数(当然、偶数)もアウトのため、素数が含まれる可能性が残るのは、第(4 の倍数)項だけになりました。

同様にして



:
(8k + 4, k = 0, 1, 2, ...)番項はすべて、73 を素因数として含んでいます。
計算機まかせではなく筆算でもしてみると帰納的にわかります。
→(8k + 4, k = 0, 1, 2, ...)番項はすべて合成数です。
{8k + 4| k = 0, 1, 2, ...}は、8 で割ると 4 余る自然数の集合です。前のステップで、素数候補は(4の倍数)番項に絞られましたが、このステップで 8 で割ると 4 余る数(当然、4 の倍数)もアウトのため、素数が含まれる可能性が残るのは、ここまでで第(8 の倍数)項だけということになりました……

ところで、YMNさんが見つけだした「凶悪」な数(最小の素因数が、1265011073である数)は、ここでの定義でいうと(元発言とでは 1 ずれるので)第64項です。 これは第(16 の倍数)項の 1 つです。

#6/3 追記で補足
投票数:0 平均点:0.00
返信する

この投稿に返信する

題名
ゲスト名
投稿本文

  条件検索へ



ログイン

ユーザー名:


パスワード:





パスワード紛失  |新規登録
PR
twitter
Created by: twitter website widget