Math by Code
コードで問題解決することを追求してみよう。 特に従来型のフロー型、手続き型のプログラミングだけではなく、 数学の集合定義のような内包型、宣言型のコードも取り入れよう。 そうすることで、 プログミングを処理の連続という視点だけではなく、 集合と集合の関係性という数学の関数に近い視点で構造化できるようになるきっかけができるといいね。 それをgeogebraのコマンド活用につなげてみよう。
Índice analítico
- List
- Listをやろう
- mapをやろう
- filterをやろう
- fibをやろう
- factをやろう
- whileをやろう
- filterとmapでピタゴラス
- Primes
- メルセンヌさんの素数
- １だけならぶ素数
- 双子素数はレア物か？
- 素数のこさを予想する
- Power
- ≡はmagic
- 2乗・2進 is magic
- Fermatでスリム化
- FermatとPrime
- mutual Primeの関数
- Eulerは拡張する
- 原始根探し
- 原始根で指数・対数
- 平方剰余（オイラーの基準）
- Function
- zipで関数とグラフ
- curryで数論関数
- 関数で関数を微積しよう
- 関数合成でcollatzしよう
- pellの行列で平方根近似
- Fractionで平方根近似
- 乱列を関数EUで
- スターリング数の２タイプ
- 母は分解をgenerateする
- Graph
- Graphをやろう
- データからGraphをつくろう
- 完全グラフをKnで作る
- 2部グラフのjudge関数
- 連結グラフと一筆書き
- matchingを安定させよう
- Kuratowskiで平面にかこう
- 最短はDIJKだけ？
- treeで遊ぼう
- calcRPN関数で電卓を作ろう
- Bstをclassで作ろう
- dfsでhamiltonPathをめざす
- graphのパズル
- 半順序をhasseで図にしよう
Listをやろう
1から10の和
Geogebraで関数型プログラミングにとりくむ
[b][size=150][b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][/b][br]＜プログラミングってなんだっけ？＞[br][/size][/b][br]プログラミングといえば、[br]計算などの記号・数値の操作をして、[br]問題を解決したりするための計画書を作ることだね。[br][br]詳しい話は省きますが、[br][color=#38761d][size=200][b]プログラミングには３つの側面がある[/b][/size][/color][br]といわれているね。[br]さて、何でしょう？[br][br]順番にやる「[color=#0000ff][b][size=100][size=150]順次[/size][/size][/b][/color]」、[br]同じようなことをくり返す「[size=150][color=#0000ff][b]反復[/b][/color][/size]」、[br]条件をつけて枝分かれする「[b][size=150][color=#0000ff]分岐[/color][/size][/b]」。[br][br]やりたいことを１行１行書き並べえて、上から順に実行するのが順次だね。[br]for文やwhile文を使って条件をつけて同じようなことを繰り返すのが反復だ。[br]分岐は、変数の値の範囲などで、次にどうするかを変えるのが分岐だ。[br][br]また、[br]同じようなことを何回もかくのも無駄だから、[color=#0000ff][b][size=150]変数と関数[/size][/b][/color]を用意して、記述を短くするのも便利だ。[br][br]プログラミングを建築としたら、堅牢で柔軟でエコなものが求められるだろう。[br][br]変数に対する手続きの流れを構造化するためにいろんな思想や言語やツールが次々に登場しているね。[br][br]現実の情報の流れにそってデータと処理の「型」を作り、それをデータとつなぐ「[color=#0000ff][b][size=150]オブジェクト指向[/size][/b][/color]」。[br]関数を数学の定義に近づけようとする「[size=150][b][color=#0000ff]宣言型、関数型[/color][/b][/size]」プログラミングの研究。[br]データ処理が表に対するものと考える行列・表・データベースの編集・探索のための「[color=#0000ff][b][size=150]パッケージ[/size][/b][/color]」。[br]AI、機械学習の研究開発、組み込み、Web、バックエンド、モバイルなど用途別の「[color=#0000ff][b][size=150]サービス[/size][/b][/color]」。[br]。。。などがある。[br][br][u][b][size=150][color=#38761d]質問：あなたが関数型プログラミングについて知っていることや用語を伝えてください。[br][/color][/size][/b][/u]
[b][size=150]＜手続き型 VS 宣言型＞[br][/size][/b][br][b][color=#38761d][size=200]200行５列の[br]200人の５科目（国、数、英、理、社）の得点表があるとしましょう。[br]これから200人分の平均点を出したい。[br][/size][/color][/b][br]１人目の得点は[br]国＋数＋英＋理＋社で出して、第６列(C6)に記入し、第７列(C7)にも書こう。[br]そして、2人目も同じように第６列(C6)を書く。第７列(C7)には上の行の７列目(C7)+この行の６列目(C6)。[br]こんな感じでやると、７列目(C7)には、どんどん、６列目(C6)が足されていく。[br]そして、200行７列目(C7)には200人分の5科目合計点の合計が入る。[br]最後に201行目にC7÷200を計算して書く。[br][br]これが、「[color=#0000ff][b][size=150]手続き型[/size][/b][/color]」だね。[br]juliaは手続き的にも関数型でも対応できるし、[br]添字が１スタートでgeogebraと同じだし、[br]記述がpythonに似ているので基本juliaで書いてみよう。[br][br][br][IN]julia[br]0点から100点までの200行5列の表データdataを適当に作る。[br]#データ作成***************************************[br][color=#0000ff][br]data=rand(0:100,200,5)[br][/color][br]#手続き的***************************************[br][color=#0000ff][br]C7 = 0[br]for hito in 1:200[br] C6 = 0[br] for kamoku in 1:5[br] C6 = C6 + data[hito, kamoku][br] end[br] C7 = C7 + C6[br]end[br]C7/200[br][/color][br]#***************************************[br][br]juliaは添え字が１開始で終了までの範囲をかくだけだから、初心者でも使いやすい。[br][br]しかし、他の言語はちがう。[br]範囲指定は繰り返しの書き方はＣ言語由来のスタート、増分、終了という書き方が[br]主流なので慣れが必要だ。しかも、今人気のpythonでさえも、添え字が０スタートだ。[br]「[color=#0000ff][b][size=150]フローチャートのパラダイム・流儀[/size][/b][/color]」に慣れるのにはよいでしょう。[br][br]しかし、この程度の課題なら、エクセルとかの表アプリがあれば、そんな苦労は不要だ。[br]エクセルを使った人ならわかるだろうけど[br]6列目に=Σ(1行目の5列の範囲指定)という関数をかき、それを200行までコピーする。[br]2001行目6列目に=Ave(6列目の1行から200行の範囲指定）という関数を書けば、計算式も不要だ。[br]そして、7列目という加算の繰り返し結果の順次記入という手間がいらないね。[br][br]このように、[color=#0000ff][b][size=150]順次や繰り返しというプログラミングのパラダイムを減らし、[br]数学的に(つまり、宣言的、内包的に)かける[/size][/b][/color]と、簡単だしわかりやすいね。[br][br]たとえば、6列目(L)は数データのリストになるね。[br]これを内包的にかいてみよう。[br] sum は、 hito番目のdataのすべての列のデータｘの合計だ。[br]6列目(L)は、hitoが１から200番までいるときのsumの列だ。[br]あとは、平均=6列の合計÷6列の行数[br]＝sum(L)÷size(L)のようにかける。[br][color=#980000](※size関数はプログラミング言語によってちがうので注意しよう）[br][/color]julia[br]#内包的***************************************[br][br][color=#0000ff]L= [ sum( [ x for x in data[hito, : ] ] ) for hito in 1:200 ] [br][br]sum(L)/length(L)[br][/color][br]#***************************************[br]つまり、[math]\sum_{hito=1}^{200}\sum_{i=1}^5data\left(hito,i\right)\div200[/math] と同じ書き方だ。[br]数学そのものの書き方だね。[br]ただ、2重のΣ計算の範囲をforのあとに記述しているだけだとわかるね。
では、geogebraで宣言型にかいてみよう
[size=150][b]＜ウォーミングアップ＞[/b][/size][br][br]手続き型でも宣言型でも、for条件が入れ子になっていることがわかるね。[br]そこで、もっと簡単な1重のfor条件をgeogebraでやってみよう。[br][br]1から10までの和をjuliaでかく。[br][color=#0000ff][IN][br]#======================[br]lst=[n for n in 1:10][br]sumlst=sum(lst)[br]#======================[br][OUT][br]55[br][/color][br][color=#cc0000]ワークシートにgeogebraアプリを作成したかったら、[br]最下行の「＋要素の追加ボタン」を押して作成を選びます。[br]次に適当にたとえば、図形や関数を選びましょう。メニューバーの右上の３本線「三」マークを押し、[br]プルダウンメニューから表示を選べます。その真中あたりの「表示」を押して[br]チェックボックスの「数式」にチェックを入れましょう。[br]そうすると、数式、geogebraコードが表示されます。[br][br][/color][color=#38761d]関数コマンドは[url=https://geogebra.github.io/docs/manual/ja/]geobebraの日本語マニュアルページ[/url]を辞書代わりに使ってみましょう。[br][/color][br]geogebraではｘは座標として解釈される予約語なので、変数は基本nなどにしよう。
1から10の和
さあ、この調子で２重のΣ計算を、geobebraを使って宣言型でかいてみよう。[br][br][color=#0000ff]200人分のデータの生成には、[br]data=Sequence(Sequence(RandomBetween(0,100),kamoku,1,5),hito,1,200)[br][br]200人分の５科目の合計点リストは、[br]L=Sequence(Sum(data(hito,k),k,1,5),hito,1,200)[br][br]平均点の計算は、[br]((Sum(L))/(Length(L)))[/color]
２００人の平均点を宣言型で求めよう
メルセンヌさんの素数
[size=150][b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][br]＜メルセンヌ素数ってなんだっけ？＞[br][br][/b]1644年にフランスのメルセンヌさんが、「M(n)=2[sup]n[/sup]-1型のn<=257の素数は11個だ」[br]と[color=#9900ff]予想[/color]しました。（n=2,3,5,7,13,17,19,31[color=#ff0000],67,[/color]127,[color=#ff0000]257[/color]）[br]そこから、この型の素数をメルセンヌ素数と呼ばれるようになったようです。[br]1876年にリュカ(Lucas)さんが、127以下のメルセンヌ素数Mnは[br]n=2,3,5,7,13,17,19,31までは同じですが、[br]n=[color=#0000ff]61,89,107[/color],127になることを証明したそうです。[br]1952年以降、その続きがn=[color=#0000ff]512,607,1279,2203[/color],..........と発見が続いています。[br][br]メルセンヌ型素数は、mが素数であることは必要条件。[br]なぜなら、mが合成数だと2[sup]m[/sup]-1も合成数になるから。[br]このことは整式の分解で説明がつく。[br][b]ｍは素数であることが必要になる。しかし、十分とは限らないので要注意。[br]実際に調べてみよう。[br]juliaで素数判定関数を作る。[br]次に、juliaで2から31までの素数リストMを作る。[br]Mの要素mに対して2[sup]m[/sup]-1が素数になるものをfilterで取り出そう。[br]＜参考＞[br]（・[b][color=#0000ff]素数リスト[/color][/b]の作り方、[color=#0000ff][b]素数判定[/b][/color]については[url=https://www.geogebra.org/m/jxmueqdt]こちら、[br][/url] ・リストに[color=#0000ff][b]filterをかける方法[/b][/color]については[url=https://www.geogebra.org/m/vre8rh6h]こちら[/url]）[br][br][br][/b][color=#0000ff][IN]julia[br][/color][/size][color=#0000ff]#======================[br][/color]function isPrime(n)[br] lim = Int(round(n^0.5))[br] for num in 2:lim[br] if BigInt(n) % BigInt(num) ==0 [br] return false[br] end [br] end[br] return true[br]end[br]M=filter(n->length(filter( m -> n % m==0,1:n))==2, 2:31)[br]Ms=filter(m->isPrime(2^m-1),M)[br]println(M)[br]println(Ms)[br][color=#0000ff]#======================[/color][OUT][br][2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31][br][2, 3, 5, 7, 13, 17, 19, 31][br][br]このように少し調べただけでも[br]2[sup]m[/sup]-1が素数になる素数ｍを限定できたね。[br][br]geogebraでも試してみよう。[br]Juliaと同じロジックで、ほぼ同じような記述で調べることができる。
メルセンヌ素数判定法
＜リュカ数＞[br]Mp＝2^p-1[br]Spは漸化式で、S[sub]0[/sub]=4, S[sub]k[/sub]=S[sub]k-1[/sub][sup]2[/sup]-2.[br][br]p番めのメルセンヌ数をMp,リュカ数をSpとする。[br][color=#0000ff][b][size=200]S[sub]p-2[/sub]がM[sub]p[/sub]で割り切れるときに、Mpは素数になる[br][/size][/b][/color]ことが必要十分条件だ。[br]Spは2乗して２をひくことを繰り返すので、急激に桁が大きくなると予想されるね。[br]それでも多桁なのでJuliaで多桁用にBigInt()でかこってリュカ数(Lucas)を作ってみよう[br][color=#0000ff]#Julia[br][/color][color=#0000ff]#[IN][br][/color][color=#0000ff]#====================[br][/color]#リュカ数を作る[br]Lucas=BigInt(4^2-2)[br]S=[Lucas][br]for i in 1:8[br] Lucas=BigInt(Lucas^2-2)[br] push!(S,Lucas)[br]end[br]println(S)[br][color=#0000ff]#====================[br][OUT][br][/color]BigInt[14, 194, 37634, 1416317954, 2005956546822746114, 4023861667741036022825635656102100994, 16191462721115671781777559070120513664958590125499158514329308740975788034, 262163465049278514526059369557563039213647877559524545911906005349555773831236935015956281848933426999307982418664943276943901608919396607297585154, 68729682406644277238837486231747530924247154108646671752192618583088487405790957964732883069102561043436779663935595172042357306594916344606074564712868078287608055203024658359439017580883910978666185875717415541084494926500475167381168505927378181899753839260609452265365274850901879881203714][br][br]＜リュカ・レーマーテスト＞[br]S[sub]p-2[/sub]がMpの倍数であることがMpはメルセンヌ素数であることの必要十分条件だった。[br] S=[14, 194, 37634, 1416317954, 2005956546822746114][br]M=[1,3,7,15,31,63,.....][br]S1 % M3=14 / 7=2だから、M3=7は素数[br]S2 % M4=194 % 15 !==0だから、M4は素数ではない。[br]S3 % M5= 37634 / 31 =1214だから、M5は素数。[br]こうして、２つ番号ちがいのリュカ数列をメルセンヌ数列で割り切れると[br]素数と判定できる。割り切れるかどうかは、剰余が０になるかどうかだから、[color=#0000ff][b][u]Spそのものではなく、SpをMpで割った剰余で代用[/u][/b][/color]して、[br]けたの爆発を防止しよう。[br][color=#0000ff]#Julia[br][/color][color=#0000ff]#[IN][br][/color][color=#0000ff]#====================[/color][br]target=127[br]M=[][br]for x in 3:target[br] push!(M,BigInt(2)^x - 1)[br]end[br]#println(M)[br]function LucaModM(x)[br] #x番目のメルセンヌ数を法とした剰余でリュカ数列を作る。[br] res=4^2-2[br] for i in 2:x[br] res = BigInt(res^2-2) % BigInt(M[x])[br] end[br] return res[br]end[br]for n in 3:target-2[br] if LucaModM(n)==0[br] println("M",n+2,"=2^",n+2,"-1=",M[n]," is Prime")[br] end[br]end[color=#0000ff]#====================[/color][br][color=#0000ff][OUT][br]M5=2^5-1=31 is Prime[br]M7=2^7-1=127 is Prime[br]M13=2^13-1=8191 is Prime[br]M17=2^17-1=131071 is Prime[br]M19=2^19-1=524287 is Prime[br]M31=2^31-1=2147483647 is Prime[br]M61=2^61-1=2305843009213693951 is Prime[br]M89=2^89-1=618970019642690137449562111 is Prime[br]M107=2^107-1=162259276829213363391578010288127 is Prime[br]M127=2^127-1=170141183460469231731687303715884105727 is Prime[/color][br][br][br]
≡はmagic
１．≡という魔法
[b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br][br]整数が偶数と奇数のどちらかのクラスに分けられるというのは便利な考え方です。[br]偶数もたんさんあるし、奇数もたくさんある。[br]でも、偶数は０、奇数は１で代表すると、とても楽になります。[br]それが合同の発想です。[br][br][b][size=150]＜合同式＞[/size][/b][br]偶数、奇数は２で割った余りによる分類でした。[br]４で割った余りは０，１，２，３の４種類のどれかなので、[br]それでクラス分けしましょう。[br]aを４で割った余りとｂで割った余りが等しいとき、合同式「[color=#0000ff][b][size=150]a≡b(mod 4)」と書きます。[br]aとｂのクラスは同じとも言えますね。[br][/size][/b][/color][b][color=#0000ff]（pを[color=#0000ff][b]法ｐ[/b][/color]とか、モジュラスｐとか、ｐで割ったときとか、mod pとか読みます。[color=#0000ff][b]bは剰余。[/b][/color]）[br]この≡記号は＝よりも線が１本増えただけで、ほぼ等式の性質が使えます。[br][/color][/b]くわしく見ていきましょう。[br][br][br][b][size=150]（一般化しよう）[br][/size][/b][color=#0000ff][b][size=150]a-b≡０(mod p）[/size][/b][/color]とかくと、a-bはｐの倍数だ。ｐはa-bを割り切る(divide)[br][b]p｜a-b[/b]ともかけるし、[b](a-b)=pk[/b]ともかけるでしょう。[br][color=#9900ff]実は、これがもともとの合同式の定義でした。[br][/color]整数ｘ，ｙ，ｚに対してｚ|(x-y）が成り立つとき、ｘ≡ｙ(mod z)とかき、[br]ｚを法として、ｘとｙは[b]合同[/b]だという。この式を[b]合同式[/b]と呼ぶ。[br]合同式には３つの性質があり、合同は、同値関係だとわかるね。[br]性質１（反射）ｘ≡ｘ（mod ｎ）[br]性質２（対称）ｘ≡ｙ（mod ｎ）⇒ｙ≡ｘ（mod ｎ)[br]性質３（推移）x≡ｙ（mod ｎ) ∧ y≡ｚ（mod ｎ) ⇒ ｘ≡ｚ（mod ｎ)[br][br]法則（加減乗）２つの合同式の左辺どうし、右辺どうしの和差積は合同だ。[br] [br][br]
互除法
ABG法
ウィルソンの確認
２．≡と＝を比べる
[b]≡は＝と同じように、等式の性質が使えることが多い。[br][br][size=150][color=#0000ff][u]質問：≡と＝の同じところ、ちがうとこを調べてみよう。[br][/u][/color][br][/size][/b]移項したり、両辺に同じ数をたしたり、ひいたりできるだけでなく、[br]両辺同じ数をかけたり、[br]左辺どうしの積と右辺同士の積を結ぶことができる。[br]また、平方根も整数の範囲で求めることができる。[br]また、負の値はmod のｐを加えて正の値にすることができます。これはmod の意味から明らか。[br]（例）[br]x≡1(mod7)ならば、2x≡2(mod7)[br]x≡2(mod 7)ならば、7x≡14≡０(mod 7)[br]ｘ-1≡０（mod 7) ならば、x≡1(mod 7)[br]ｘ+6≡1（mod 7) ならば、x≡-5≡-5+7≡ 2(mod 7)[br]ｘ[sup]2[/sup]≡4 (mod 7) ならば、x≡±2≡2, -2+7≡ 2,5(mod 7)[br]・13≡4, 13[sup]2[/sup]≡16≡７≡-2, 13[sup]3[/sup]≡-2･4=-8≡1(mod 9)だから、[br] 13[sup]10000[/sup]≡(13[sup]3[/sup])[sup]3333[/sup]・13≡1･4＝４（mod 9)[br][br][br][b][size=150]＜法と剰余の関係＞[br][/size][/b]ただし、[color=#0000ff][b]等式とちがう部分もある。とくに、割り算だ[/b][/color]。[br][b]ｘ≡1(mod8)[/b]なら、x={1,9,17,25,.....} だから、剰余と法が互いに素なら[color=#0000ff][b]ｘ≡1(mod2, mod4)[/b][/color]となる。[br][b]ｘ≡4(mod 8)[/b]なら、x={4,12,20,28,....} だから、１以外の剰余と法の最大公約数ｄ=4で約すと、[br] x/4={1,3,5,7,....}だから、[b][color=#0000ff]x/4≡4/4(mod 8/4)≡1(mod 2)[br][/color][/b][br][b]ｘ≡6(mod 8)[/b]なら、x={6,14,22,30,....} だから、１以外の剰余と法の公約数d＝2で約すと、[br] x/2={3,7,11,15,....}だから、[color=#0000ff][b]x/2≡6/2(mod 8/2)≡3(mod 4)[/b][/color][br][br][b][size=150]＜合同方程式を解いてみよう＞[br][/size][/b]・1次方程式[b][color=#0000ff][size=150]ax≡b(mod p) [br][/size][/color][/b]ax - b = np となるｎがある。[br][b]ax + np =b[/b] という、積和の形に直せるね。 [br][br][b][color=#0000ff][size=150]ma≡mb(mod n) [/size][/color]ｍがｎの倍数でないとき、 両辺をｍで割って約せる。しかし、法については注意！[br][/b] 法ｎもｍの倍数、n=mｃなら、法もｍで約せる。a≡b( mod n/m) [br] そうでないとき（nとｍが互いに素なら）法はそのままだ。a≡b (mod n)[br] [color=#0000ff][b][size=150]一般に、G(m,n)＝ｄとすると、a≡b( mod n/d)[br][/size][/b][/color][br][color=#0000ff][b](例１）「4x≡3(mod 19)」の解は？ x ≡15[br][/b][/color]両辺を5倍する。20x≡(19+1)ｘ≡ x ≡15(mod 19) [br](別解) 3-19=-16。[br]右辺-19で、4x≡-16(mod 19) 両辺を4で約す。ｘ≡-4≡-4+19≡15。[br][color=#0000ff][b](例２）「4x≡16(mod 28)」の解は？ x ≡ 4 (mod 7)[br][/b][/color]係数の最大公約数d=4だから、[br]4x/4≡16/4(mod 28/4) x≡4(mod 7)[br]x≡4, 4+7, 4 +7+7, 4 + 7+7+7 ( mod 28)[br]x ≡ 4 , 11, 18, 25(mod 28)[br][b][color=#0000ff](例３）「18x≡8(mod 14)」の解は？ x≡2 ,9 (mod 7)[br][/color][/b]剰余と法の最大公約数d=2だから、[br]18x/2≡8/2(mod 14/2) 9x≡4(mod 7) [br]４≡4+7+7=18(mod 7)から、9x≡18(mod 7) x≡2(mod 7)[br]x≡2, 2+7 (mod 7)から、x≡2,9(mod 14)。 [br]（別解）[color=#0000ff][b][size=150]ax≡b(mod p)を言い換える。[br]ax-py=bの解はax-py=G(a,p)のb/G(a,p)倍。[br]この倍数が整数のときは解がある。[br] [/size][/b][/color]18・４ー14・5=G(18,14)=2だから、8/2＝４倍する。[br]x=4・4=16, y=5・4=20。[br][b]18[/b]・16=[b]14[/b]・20 + [b]8[/b]となる。[br]だから、18・16≡8(mod 14) x=16≡2(mod 14)。[br]他の解は14/2=7を加えて、ｘ＝2+7=9(mod 14)[br][b][color=#0000ff](例４）「35x≡105(mod 225)」の解は？ x≡3(mod 45)[br][/color][/b]両辺は35の倍数になっている。[br]35 と225 の最大公約数は5だから、[br]35x/35≡105/35(mod 225/5) [br]x≡3(mod 45)[br]x ≡ 3 , 48, 93, 138, 183 (mod 225)[br][color=#0000ff][b](例５）「893x≡266(mod 2432)」の解は？ x≡1106,1234, 1362,........, (mod 2432)[br]G(266,2432)=38[br]G(893,2432)=19[br]893x-2432y=266の解は893x-2432y=G(893,2432)=19の266/19=14倍。[br]「ユークリッドの互除法の逆算」（ABG計算）によって、ｘ，ｙの特殊解は求められるね。[br]（ABG計算の説明は省略。）[br][/b][/color]893・79ー2432・29=19だから、14倍する。[br]x=79・14=1106 y=29・14=406。[br][b]893[/b]・1106 = [b]2432[/b]・406+[b]266[/b]となる。[br]だから、893・1106≡266(mod 2432) [br] x≡1106(mod 2432)。[br][b]2432/19=128を1106に加えていく。[br][/b]pythonの対話モードで調べよう。[br]>>> y=1106[br]>>> for i in range(19):[br]... print(y)[br]... y=y+128[br]... y=y%2432[br]を実行する。[br]異なる解はｘ＝1106+128k(mod 2432)=[br]1106[br]1234[br]1362[br]1490[br]1618[br]1746[br]1874[br]2002[br]2130[br]2258[br]2386[br]82[br]210[br]338[br]466[br]594[br]722[br]850[br]978[br][br][b][color=#0000ff]（例６）6ｘ≡15（mod 514）[b]の解は？なし[/b][br][/color][/b]6x-15は必ず奇数。法の514は偶数。[br]偶数が割り切る奇数はないので、6x-15≡0(mod 514)の解はない。[br][br]・２次方程式[br][color=#0000ff][b](例７）x[sup]2[/sup]+2x≡０(mod 7)[b]の解は？ x ≡ 0, 5 (mod 7)[/b][br][/b][/color]左辺の因数分解で、x[sup]2[/sup]+2x≡x(x+2)≡0(mod 7)から、x≡0, -2≡0,5(mod 7)[br][color=#0000ff][b](例８）x[sup]2[/sup]+2x-1≡０(mod 7)[b]の解は？x≡ 2, 3 (mod 7)[/b][br][/b][/color]左辺-7して因数分解すると、x[sup]2[/sup]+2x-8=(x-2)(x+4)≡0(mod 7)から、x≡2, -4≡2,3(mod 7)[br][b][color=#0000ff](例９）x[sup]2[/sup]≡3(mod 10)[b]の解は？なし[/b][/color][/b][br]x(mod 10)={0,1,2,3,4,5,6,7,8,9}に対して、x[sup]2[/sup](mod 10)={0,1,4,9,6,5,6,9,4,1}から、剰余が３と合同に[br]ならない。だから、解なし。[br][br][color=#0000ff][b]このように、1次合同方程式でも解の数は１つとは限らない。[br]また、１次でも２次でも合同方程式は解なしもありうるね。[br][/b][/color][br][br]
３．「ウィルソンの定理」で≡記号に親しもう
[color=#0000ff][b][size=150]質問：ｐが素数のときに[br][br][size=200](p-1)! + 1 ≡ 0 (mod p)[br][/size][br]という[u]ウィルソンの定理[/u]というものがあります。[br]≡式の考えを使ってなぜそうなるかを考えてみよう。[br][/size][/b][/color][b][size=150]（例）[/size][/b][br]p=2,3,5,7,11のとき、[br](2-1)!+1= 1!+1 =2≡0(mod 2)[br](3-1)!+1= 2!+1 =3≡0(mod 3)[br](5-1)!+1= 4!+1 =25≡0(mod 5)[br](7-1)!+1= 6!+1 =721≡0(mod 7)[br](11-1)!+1= 10!+1 =3628801=329891*11≡0(mod 11)[br][br][b][size=150]（mod7で実験しよう）[/size][/b][br](7-1)!=(7-1)*5*4*3*2*1=(7-1)*(5*3)*(4*2)*1[br]≡(7-1)*1*1*1=7-1(mod 7)[br]だから、(7-1)!+1≡7-1+1=7≡0(mod 7)です。[br]7-1以下の１以上の整数は、単位元が１です。[br]剰余どうしの積が１になるペアは逆元といいますが、[br]同じ数が別のペアと逆元になることはありません。[br]１つの数には１つだけ逆元があります。[br]5*3=15≡１(mod 7)[br]4*2=8≡１(mod 7)[br]ただし、特殊なケースが２つあります。[br]１と６です。[br]1*1≡１(mod 7)[br]6*6=(7-1)*(7-1)≡(-1)*(-1)≡1(mod 7)です。[br]だから、7-1=6個の要素のうち、１と６だけは自分が逆元なので、そのままのこる。[br]のこりの6-2=4要素は4/2=2組の１ができるので、かけ算で１となり消える。[br]だから、[color=#0000ff][b]ウィルソンの定理は( )!がはずれる定理[/b][/color]と覚えられます。[br][br][b][size=150](一般化してみよう）[/size][/b][br]7を一般の素数pにしたときも同じ論法です。 [br][b][size=150][color=#0000ff](p-1)!=[/color][/size][/b](p-1)*(p-2)*..........*2*1 ( p-1個の偶数個の積）[br]=(p-1)*1* 1*1*......*1 ( 両端以外の（p-1-2）/2個の逆元ペアが１と合同。)[br][b][size=150][color=#0000ff]≡p-1 (mod p)[/color][/size][/b][br]だから、(p-1)!+1≡p-1+1=p≡0 (mod p) [br]ただし、p=3のときは、(3-1)!=(3-1)*1なので、両端だけで( )!が外れます。[br]また、p=2のときは、(2-1)!=1=2-1だから、先頭の2-1だけそのまま( )!が外れます。
zipで関数とグラフ
１．関数に式は必要か？
[color=#0000ff][b][size=150][b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br][br]関数は集合Xの要素ｘから集合Yの要素ｙへの対応づけだ。[br][/size][/b][/color]対応がつけばよいだけなのに、対応を式に表すことができると考えてしまいがちだ。[br]ｆ :: X→Y[br]f (x) = expr(x)[br]中学数学で学んだ１次関数、２次関数のイメージが強いためか、[br]関数というと、[color=#0000ff][b]y=ｘの式という、計算操作のイメージ[/b][/color]がつきまつ。[br][br]しかし、結果としてのグラフイメージで関数を俯瞰してみよう。[br]すると、[color=#0000ff][b]関数はXとYの直積空間（X-Y座標平面）の要素の点(x,y)のあつまり、部分集合[/b][/color]という風にとらえることもできる。[br][br]y=2xという関数は、この関数を満たす点と考えると、順序対、タプル(x,y)のリスト[br]と考えることもできるね。[br]連続量に近いイメージがほしければ、ｘの範囲を細かく区切ると良い。[br][color=#0000ff]#[IN]julia[br]#============================[br]F=[(x,2*x) for x in 1:10][br]G=[(x,2*x) for x in 1:0.001:10][br]#============================[br][/color][OUT][br]10-element Vector{Tuple{Int64, Int64}}:[br] (1, 2)[br] (2, 4)[br] (3, 6)[br] (4, 8)[br] (5, 10)[br] (6, 12)[br] (7, 14)[br] (8, 16)[br] (9, 18)[br] (10, 20)[br][OUT][br]91-element Vector{Tuple{Float64, Float64}}:[br] (1.0, 2.0)[br] (1.1, 2.2)[br] (1.2, 2.4)[br] (1.3, 2.6)[br] (1.4, 2.8)[br] (1.5, 3.0)[br] (1.6, 3.2)[br] (1.7, 3.4)[br] (1.8, 3.6)[br] (1.9, 3.8)[br] (2.0, 4.0)[br] (2.1, 4.2)[br] (2.2, 4.4)[br] ⋮[br] (8.9, 17.8)[br] (9.0, 18.0)[br] (9.1, 18.2)[br] (9.2, 18.4)[br] (9.3, 18.6)[br] (9.4, 18.8)[br] (9.5, 19.0)[br] (9.6, 19.2)[br] (9.7, 19.4)[br] (9.8, 19.6)[br] (9.9, 19.8)[br] (10.0, 20.0)[br][br]すると、１対１にこだわらなければ、xの剰余を対応させたり、[br][color=#0000ff]ｘの値と無関係に乱数を作ってzipで順序対(タプル）を作ったり[/color]と[br]関数は自由だ。[br][br][color=#0000ff][b][size=200]zipを使うと、関数も作れるし、グラフもすぐかけるね。[br][/size][/b][br]#[IN]julia[br]#============================[br]H=[(x,x % 3) for x in 1:10][br][/color][color=#0000ff]#============================[br][OUT][br]10-element Vector{Tuple{Int64, Int64}}:[br] (1, 1)[br] (2, 2)[br] (3, 0)[br] (4, 1)[br] (5, 2)[br] (6, 0)[br] (7, 1)[br] (8, 2)[br] (9, 0)[br] (10, 1)[br]#[IN]julia[br]#============================[br]xs=Vector(1:10)[br]ys=rand(10)[br]z=[(x,y) for (x,y) in zip(xs,ys)][/color][br]#============================[br][OUT][br]10-element Vector{Tuple{Int64, Float64}}:[br] (1, 0.20169081026514768)[br] (2, 0.17422295843712776)[br] (3, 0.25178803264424066)[br] (4, 0.5264239612886585)[br] (5, 0.4820281573212978)[br] (6, 0.23582173409057716)[br] (7, 0.06452661349364275)[br] (8, 0.6707651637338825)[br] (9, 0.3189198173371426)[br] (10, 0.4016041332227487)[br][br][b][br][/b]
関数と順序対
mod関数 の視覚化
2.暗号解読は逆関数？
[b][size=150]＜シーザー暗号とは＞[br][/size][/b]シーザー[color=#9900ff][b]暗号[Cipher][/b][/color]というものがある。[br][br]これって、ルールは単純で、[br]文字ｘに対して、文字コードy=f(x)を対応させる。[br]f(x)は数値だから、それに定数sを足す。[br]そして、文字コードsに対する文字をf-1(x)で求めたものをｚとしよう。[br]これが暗号化関数Cだ。[br][br]これを、入力した文字列Xの文字ｘすべて対してｚを求めて出力したものが文字列Zとなる。[br]つまり、暗号化はC :: X→Zとかけるね。[br][br]とうことは暗号解読はその逆関数C[sup]-1[/sup] ::Z→Xとかくことができるはずだ。[br][br][b][size=150]＜暗号化と復号化を比べると＞[br][/size][/b]それでは、暗号を作る関数Cと暗号を解読（復号）する逆関数C[sup]-1[/sup]を作ってみようか？。[br]しかし、この発想には無駄がある。[br][br]暗号化のときに、文字コードを＋ｓしているとしたら、[br]復号化のときは、文字コードをーｓすればよいだけだ。[br]だったら、[b]暗号と復号の両方に使える関数Ci[/b]を作った方がよいことがわかるね。[br]シフト数をshift 、入力文字をｘとすると[br][br][color=#0000ff][b][size=150]コード化::Char→Int x -> y = codepoint(x)[br]シフト:: Int →Int y -> z = y + shift[br]デコード化:: Int→Char z -> d=Char(z)[br][/size][/b][/color][br]この３ステップを合成した関数がCiになるね。[br][br][b]＜実装しよう＞[br][/b][color=#0000ff]#julia[br]#============================[br]Int(codepoint('A'))[br]#============================[br][/color][OUT][br]65[br][color=#0000ff]#============================[br]Char(65)[br]#============================[br][/color][OUT][br]'A': [br]このように、コード化とデコード化はできることがわかる。[br]英数字、つまり、アスキー文字に限った暗号だとすると、[br]コード番号にshiftを加算してずらそう。[br]ただ、たすのではなく、Aが０番になるようにして、[br]からshiftをたして、それでも65を超えた番号は[br]振り出しのAから順にぐるぐる回るようにしたい。[br][color=#0000ff]#julia[br]#============================[br]Ci(shift::Int, x::Char)::Char = Char((Int(codepoint(x)) - 65 + shift) % 65 + 65)[br]Ci(0,'A'),Ci(1,'A'),Ci(2,'A'),Ci(3,'A')[br]#============================[br][/color][OUT][br]('A', 'B', 'C', 'D')[br][br]では、もっと先の文字も含めて、暗号と復号がうまくいくことを確認しよう。[br][color=#0000ff]#julia[br]#============================[br]Target = "ABCDE PQRSTU abcde,.xyz";[br][br]println(Target)[br]Ciphered=join([Ci(5,x) for x in Target] )[br]println(Ciphered)[br]Recovered=join([Ci(-5,x) for x in Ciphered] )[br]println(Recovered)[br][/color][color=#0000ff]#============================[br][/color][OUT][br]ABCDE PQRSTU abcde,.xyz[br]FGHIJ%UVWXYZ%fghij13}~[br]ABCDE PQRSTU abcde,.xyz[br][color=#0000ff][br]#julia[br]#============================[br]Target = "THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG";[br][br]println(Target)[br]Ciphered=join([Ci(5,x) for x in Target] )[br]println(Ciphered)[br]Recovered=join([Ci(-5,x) for x in Ciphered] )[br]println(Recovered)[br][/color][color=#0000ff]#============================[br][/color][OUT][br]THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG[br]YMJ%VZNHP%GWT\S%KT]%OZRUX%T[JW%YMJ%QF_^%ITL[br]THE QUICK BROWN FOX JUMPS OVER THE LAZY DOG[br]
Graphをやろう
点と線でできた図をデータにしてみる。
[b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][br]＜図形を使うことで処理が見やすくなる＞[br][/size][/b]グラフは頂点の集まりVとそれらをいくつか結ぶ線分（辺）の集まりEでできている。[br][br][color=#38761d][b][u][size=150][size=200]頂点がnodeか vertexかpointだ。[br]辺がedgeかsegmentだ。[br][/size][/size][/u][/b][/color][br]辺の情報を与えれば、頂点の隣接状態の図としてのグラフはかける。[br]特に指定しなければ、点の位置は任意になる。[br][br]pythonでグラフを使うためにパッケージがいろいろ必要になる。[br]昔からnetworkxとかgraphvizが有名だね。[br]（juliaでは典型的なグラフ用パッケージがあるかどうか不明なのでpythonとnetworkでコードをかく。）[br][color=#ff00ff]#======================[br]pip install scipy[br]pip install networkx[br]pip install [/color][color=#ff00ff]matplotlib[br][/color][color=#0000ff]#======================[br]import networkx as nx[br]G =nx.Graph()[br]G.add_edge(1,2)[br]G.add_edge(2,3)[br]G.add_edge(2,4)[br]nx.draw_networkx(G)[br]#======================[br][/color][OUT][br][br][color=#0000ff]#geogebra[br][/color][b][size=150][color=#38761d]グラフ用のパッケージがないので、[br]座標Nodesをランダムに4個発生させる。[br]その座標を引用して、点の番号NumTを打つ。[br][/color][/size][/b][color=#0000ff]Nodes=Sequence((RandomBetween(1,20),RandomBetween(1,20)),k,1,4)[br]NumT=Sequence(Text(k,Element(Nodes,k)),k,1,4)[br][br][/color][color=#38761d][size=150][b]描画のスピードは気にせず、4個の総当たりで辺のリストAllComiを作り、非表示にする。[br]データ作成上、リストが2層になってしまったので、辺のリストをフラットなCsにする。[br][/b][/size][/color][color=#0000ff]AllCombi=Sequence(Sequence(Segment(Element(Nodes,i),Element(Nodes,j)),j,i+1,4),i,1,3)[br]Cs=Flatten(AllCombi)[br][br][/color][color=#38761d][b][size=150]ランダムに連結すると辺が3本できないおそれがあるので辺をシャッフルして前から3本選ぶ。[br][/size][/b][/color][color=#0000ff]Take(Shuffle(Cs),1,3)[br][br][/color]
4点グラフ
4頂点3辺グラフ
[b][size=150]＜ランダムに頂点を連結してみる＞[br][br][/size][/b]randomにｍ辺できるまで、ｎ頂点を適当に結ぶ。[br]辺の集合edge_setに２頂点の組を, [color=#0000ff][b]隣接行列[/b][/color]graph_dataに２頂点の連結情報を１に[br]セットしよう。これが[color=#0000ff][b]グラフを適当につくる関数generate_G(n,m)[/b][/color]だ。[br][br][[color=#0000ff]IN]Python[br]#================================================[br]import random[br][br]def generate_G(n, m):[br] graph_data = [[0] * n for i in range(n)][br] edge_set = set()[br] while len(edge_set) < m:[br] i, j = random.sample(range(n), 2)[br] if i > j: i, j = j, i[br] edge_set.add((i, j))[br] graph_data[i][j] = graph_data[j][i] = 1[br] return graph_data, edge_set[br][br][/color][color=#0000ff]random.seed(6)[br]node_num = 16[br]edge_num = 20[br]figGraph, edgeSet = generate_G(node_num, edge_num)[br][br]edgeSet[br][/color]figGraph[br]#================================================[br][OUT][br]{(0, 2),[br] (0, 4),[br] (0, 8),[br] (1, 9),[br] (2, 5),[br] (2, 7),[br] (2, 13),[br] (3, 12),[br] (3, 15),[br] (5, 11),[br] (5, 13),[br] (6, 8),[br] (6, 11),[br] (6, 13),[br] (7, 8),[br] (7, 11),[br] (8, 10),[br] (12, 13),[br] (12, 15),[br] (13, 14)}[br][br]geogebraの場合は、上記とほぼ同じでできます。[br]3本の頂点の選び方は、4C3＝6本の辺をすべて引いてしまい。その順番をシャッフルしから前から3本[br]選びましたね。[br]これが16本になっても同じロジックで16C2＝120本引いておき、その順番をシャッフルしてから20本選んだものだけを表示するという方法です。