2021-03-24

【オイラー関数】FoxQ(または上岡)のφ類別予想【同値類】

オリジナルプチ研究数学

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

オイラー関数と同値類

自然数nに対して、ｎと互いに素な自然数の個数を $\phi(n)$ と書き、オイラー関数という。自然数Nが与えられた時、

$\phi(n)=N$

を満たす自然数nの全体を考える。これにより同値関係

$\phi(n)=\phi(m)\iff n\sim m$

を定義することができる。このしぜんすうによる同値類 $\mathbb{N}/\sim$ を考える。Nの小さい方から書き出すと、

$\mathbb{N}/\sim=\{ \{1,2\}, \{3,4,6\}, \{5,8,10,12\},\{7,9,14,18\},\cdots \}$

となる。このとき、

$a \in \mathbb{N}/\sim$ に対して、同値類の集合 $(a)$ の要素の個数 $||(a)||$ について、

$\forall (a) \in \mathbb{N}/\sim, \exists \phi_{max} \in \mathbb{N},||(a)|| \le \phi_{max}$

となる最大値 $\phi_{max}$ は存在するか？

というのが問題だ。これを

特に、 $N$ の素因数の種類が $r$ 種類のとき、

$\forall (a) \in \mathbb{N}/\sim s.t. \phi(a)=p_1^{\alpha_1}\cdots p_r^{\alpha_r}, \exists \phi_{r} \in \mathbb{N},||a|| \le \phi_{r}$

となる最大値 $\phi_{r}$ は存在するか？

$r=1$ の場合

$r=1$ のとき、自明に $N=2^\alpha$ または $N=1$ である。以下、 $N=2^\alpha$ とする。

$n=2^\beta p_1^{\alpha_1}\cdots p_r^{\alpha_r}$ とすると、

$\alpha_j=1$ でなければならない。また、

$\phi(n)=2^{\beta-1} (p_1-1)\cdots (p_r-1)$

であるので、

$\exists \beta_j p_j=2^\beta_j + 1$ でなければならない。

また、 $i \lt j \Rightarrow \beta_i \lt \beta_j$ である。

よって、

$\phi(n) = 2^{\beta+\beta_1+\cdots+\beta_r-1}$

$\alpha-\beta+1=\beta_1+\cdots+\beta_r$

ここで、 $2^\gamma+1$ 型の素数が無数に存在しないと仮定し、その最大値を $\gamma_{r_{max}}$ とおくと、

$\alpha-\beta+1=k_1\gamma_1+\cdots+k_{r_{max}}\gamma_{r_{max}}$

と書けるので、 $k_1,\cdots,k_{r_{max}}$ が0か1かの2通りあり、その組み合わせは、 $2^{r_{max}}$ 以下である。任意のNに対して、この組み合わせが決定すると、自動的に $\beta$ も決定する。よって、 $n$ としてありうる値は、 $2^{r_{max}}$ 以下である。

一方で、 $2^\gamma+1$ 型の素数が無数に存在するならば、この組み合わせに上限はないので、

$N$ の素因数の種類が $r=1$ 種類のとき、

$\forall (a) \in \mathbb{N}/\sim s.t. \phi(a)=p_1^{\alpha_1}\cdots p_r^{\alpha_r}, \exists \phi_{r} \in \mathbb{N},||a|| \le \phi_{r}$

となる最大値 $\phi_{1}$ は存在しないことになる。

フェルマー 素数

$F_n=2^{2^n}+1$ で表される数をフェルマー数 - Wikipediaという。フェルマー数で素数のものをフェルマー素数という。フェルマー素数が無限にあるかどうかは、まだ知られていない。従って、 $2^\gamma+1$ 型の素数が無数にあるかもわからない。そう、今回のFoxQ(または上岡)の $\phi$ 類別の予想はフェルマー素数に関する未解決問題を含むより、一般的な問題だったのである。

数値実験

$\phi(n)=2^m$ を満たす $n$ はM個としてプロットしてみると、

f:id:FoxQ:20210324140355p:plain — m=1から50までのMのプロット

f:id:FoxQ:20210324140428p:plain — m=100から2000までのMのプロット(500ずつの間隔)

このプロットを見る限り、

$M\le33$

と上から抑えられているように見える。従って、フェルマー素数は有限個しか存在しないことが予想される。また、 $\phi_1=33$ であることも同時に予想される。

2021-03-18

【Kindle】収縮遡及法(プログラム実装者求む！)【素因数分解】

Kindle オリジナルプチ研究数学素因数分解

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

Kindleにて、「収縮遡及法」と名づけた新しい素因数分解法についての本を出版しました。詳細はAmazonのページを見てください。

最初に、PythonのJupyter notebook上で動作するソースコードを作成してくれた方に、コードと引き換えに3000円分のAmazonギフトコードをプレゼントします。

よろしくお願いします。

収縮遡及法: とある物理学博士が素因数分解を考えてみた

作者:上岡　良季
発売日: 2021/03/17
メディア: Kindle版

2021-02-27

【Kindle】多因数分解法【素因数分解】

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

僕の新しい数学書が出版されました。

多因数分解法: ~素因数分解を考えよう~

作者:上岡　良季
発売日: 2021/02/26
メディア: Kindle版

以下、本の紹介です。

15=3×5のように、ある自然数を素数のかけ算に分解して表すことを素因数分解という。
素因数分解は、分解したい数が大きくなると急激に難しく面白い問題となる。
素因数分解への人類の挑戦の歴史は長く、その難しさのために現代でもRSA暗号に応用されるなどしている。
２つの巨大な数をかけ算することは簡単で合成数が１つ計算できる。
元のかける数を１つ知っていれば、合成数を素因数分解することは簡単だが、しらなかったり忘れてしまうととてつもなく大変になってしまう。これはちょうど、ダイヤルキーの番号を忘れると開けるのに苦労することと似ている。

著者である上岡は、日々趣味の１つとして数学をしている。この本では素因数分解の新しい一手法として著者が考案した「多因数分解法」について、その着想にまで立ち戻って丁寧に解説している。
そのため、この本を読めば、１つの数学的手法が生まれる仮定を追体験することができるだろう。
著者は「多因数分解法」を用いて、20桁と素数二つの積からなる40桁の合成数の素因数分解にすでに成功している。
この手法が今後どこまで発展しうるかについては未知数であり、また新しい派生が生まれる可能性もある。

いずれにせよ、この本を通して素因数分解という面白い問題を見つめ直すことで、楽しい数学の体験をできると期待している。「多因数分解法」のアイデアに刺激されて、別の新しいアイデアが生まれることも可能性もあるだろう。

2021-02-22

【素因数分解】ぼくの考えたアルゴリズム【RSAに挑む】

オリジナルプチ研究数学素因数分解

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

2つの素数の積からなる合成数の素因数分解

2つの素数 $p,q$ の積からなる合成数 $N=pq$ を考える。

ここで、 $p$ または $q$ の片方のみを素因数に持つ自然数 $X$ を用意すると、

$\gcd(N,X)$ をユークリッドの互除法で計算すれば、求める素因数の片方が分かるので、素因数分解できる。

ここで、自然数 $X$ をいかにして用意するかが問題となる。

素数階乗冪多項式

$P$ を素数階乗とする。このとき、

$P=p_n \#=2 \times 3 \times 5 \times \cdots \times p_n$

とおき、自然数 $1 \le a \le p_n$ に対して、多項式

$f^{(P)}(a)=P^P-a^P$

を考える。

$X=f^{(P)}(a)$ とおいて、 $\gcd(N,X)$ が $1$ でも $N$ でもない自然数になれば、それが $N$ の素因数となる。これが見つかるかどうかは、確率次第だと思うので、成功確率は今のところ不明である。

計算量

ユークリッドの互除法を行う回数は、 $p_n$ 回である。よって、計算量は、

$O(p_n \log N)$ である。

事前に用意する素数の個数nが多ければ多い程、素因数分解の成功確率は上がると期待されるが、計算量がその代わりに増加するので、適切な素数の個数を見つけなければいけない。

例

素数を１つ取って、 $n=1,p_1=2$ とする。

$f^{(2)}(1)=3$

この場合、9までの素因数分解が可能である。

素数を２つ取って、 $n=2,p_2=3$ とする。

$f^{(6)}(1)=5\times 7\times 31\times 41$

$f^{(6)}(2)=2^9 \times 7 \times 13$

$f^{(6)}(3)=3^8\times 7$

この場合、素因数に11を含む場合を除く、169までの素因数分解が可能である。

素数を3つ取って、 $n=3,p_2=5$ とする。

$f^{(30)}(1)=7 \times 11\times 13 \times 19\times29 \times 31 \times 67 \times \cdots$

$f^{(30)}(2)=2^6 \times 7\times 43 \times \cdots$

$f^{(30)}(3)=3 \times 7\times 13^2 \times 41 \times \cdots$

$f^{(30)}(4)=2^{12} \times 7 \times 13\times 17 \times \cdots$

$f^{(30)}(5)=5^6 \times 7 \times 31 \times 79 \times \cdots$

この場合、素因数に23を含む場合を除く、1296までの素因数分解が可能である。

2021-02-09

【Kindle】系統別・レベル別　整数問題集『序』を発売しました！【問題集】

Kindle オリジナル数学

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

系統的に体系化された整数問題集の3部冊『序・破・急』の1冊目『序』です。
整数問題の内、最も基本的な問題８８題を収録。

三段階の難易度別だから、読者のレベルに合わせて少しずつステップアップすることもできます。
難易度の幅は広く、教科書レベルから入試問題レベルや数学オリンピックレベルまであります。
解答もきちんとついているので安心して勉強できます。

整数問題の教科書(仮題)も出版予定です。

系統別・レベル別　整数問題集　『序』系統別　整数問題

作者:上岡　良季
発売日: 2021/02/08
メディア: Kindle版

2021-01-29

【twitterのフォロワーさん】懸賞問題の解答例【3333人記念】

twitter オリジナル数学

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

問題

今日は、twitterのフォロワー3333人記念の懸賞問題の解答例を挙げます。この問題です。

【フォロワーさん3333人記念懸賞問題】
p,qを素数、nは平方因子を持たない自然数とするとき、次の自然数Nを全て求めよ。
N=q(p^8+p^7q^2-pq^3-q^5)=n^3-3n+q

解答は過程つきでリプしてください。写真等を使ってokです。

最初の正答者に『Nの値』円からアマゾンギフト券のコードをプレゼントします!!
— FoxQ@作家@初心者絵師@フォロバ99% (@foxq0113) 2021年1月26日

最初の正答者は、おざささん(@smash033_)でした。

こんばんは、こちらでいかがでしょう。 pic.twitter.com/az4Om26GMe
— おざさ (@smash033_) 2021年1月27日

問題に挑戦してくださった皆さん、改めてありがとうございました。

想定解答

それでは、想定していた解答を書いておきます。

$N=q(p^8+p^7q^2-pq^3-q^5)=n^3-3n+q$

$N=q(p+q^2)(p^7-q^3)=n(n^2-3)+q$

ここで、 $p,q$ が共に奇素数だと仮定すると、左辺が偶数、右辺が奇数となり矛盾。よって、素数 $p,q$ の少なくとも一方は、 $2$ である。

$q=2$ とすると、

$N=2(p+4)(p^7-8)=n^3-3n+2$

$4$ を法として、 $p^2\equiv 1$ なので、

$N\equiv 2p^8=n^3-3n+2$

$n(n^2-3)\equiv 0$

$n$ は平方因子を持たないので、 $n\neq 0 (\mod 4)$ であり、 $n\equiv 1,2,3$ のとき、

$1(1^2-3)\equiv (1+1)\equiv 2$

$2(2^2-3)\equiv 2\times1\equiv 2$

$3(3^2-3)\equiv 3 \times 2\equiv 2$

となり、矛盾。従って、 $q \neq 2$ である。

これより、 $p=2$ でなければならない。このとき、 $N$ は自然数つまり正の数なので、

$N=q(2+q^2)(2^7-q^3)\ge 1$

これより、

$(128-q^3)\ge 1$

これを満たす素数 $q$ は、 $q=3,5$ のみである。

$q=5$ のとき、

$5(2+5^2)(2^7-5^3)=n^3-3n+5$

$5(2+5^2)(2^7-5^3)-3=n^3-3n+2$

$402=(n-1)^2(n+2)$

$2\times 3 \times 67=(n-1)^2(n+2)$

$n=2$ は明らかにこの式を満たさないので、右辺は平方因子を持つ。一方、左辺は平方因子を持たないので矛盾。

最後に、 $q=3$ のとき、

$N=3(2+3^2)(2^7-3^3)=n^3-3n+3$

$N-1=3332=(n-1)^2(n+2)$

$N-1=2^2\times7^2\times17=(n-1)^2(n+2)$

これを満たす $n$ は、右辺に現れる2種類の因数の差が $3$ であることに着目すると、 $n=15$ のみである。したがって、 $p=2,q=3,n=15$ のとき、求める自然数は、

$N=3333$

である。

2021-01-23

空間中の円の決定方法

twitter オリジナル数学ヤフー知恵袋

Amazon.co.jp: Yoshiki Ueoka:作品一覧、著者略歴

数学関連の絶版本・品切れ本をコチラから購入できます！

事始めと問題

twitterのNAKさんが、空間中の円の決定問題についてツイートしていたので、解いてみました。以下のツイートです。

3点と中心がわかっていれば空間上の円の方程式を出せると思うんだけど…全然わからん。数学弱いんだよ…。
— NAK@(; ･`д･´) (@nakscpcgoca) 2021年1月21日

この記事では、３つの条件下で空間中の円の決定問題を解いてみます。

中心と1点と法線ベクトルが分かっている場合

中心の位置ベクトルを $\vec{p}=(p_x,p_y,p_z)$ とする。1点を $\vec{x_1}=(x_1,y_1,z_1)$ とする。

このとき、中心が $\vec{p}$ の円の方程式は、半径を $r$ とすると、

$(\vec{x}-\vec{p})^2=r^2$ ……①

であるので、この円が点 $\vec{x_1}$ を通るので、半径 $r$ は、

$r=|\vec{x_1}-\vec{p}|=\sqrt{(x_1-p_x)^2+(y_1-p_y)^2+(z_1-p_z)^2}$

と求まる。

円の存在する平面の法線ベクトルを $\vec{n}=(n_x,n_y,n_z)$ とすると、

$(\vec{x}-\vec{p})\cdot \vec{n}=0$ ……②

これから、 $\vec{x}=(x,y,z)$ の $z$ 座標を変数 $x,y$ で表せる。

決定された $r$ を用いて、空間中の球が方程式①により決定される。②式と連立して、 $z$ 座標を消去したものが、 $xy$ 平面に射影した円の方程式となり、その各点に対して、求める円の $z$ 座標を②式で計算できる。

半径と2点と円の平面の法線ベクトルがわかっている場合

2点の内、一点を原点とする三次元座標をとると、既知の情報は、半径 $r$ と2点 $\vec{0}=(0,0,0),\vec{x_1}=(x_1,y_1,z_1)$ を通ること、および、円が与えられた法線ベクトル $\vec{n}=(n_x,n_y,n_z)$ に垂直な平面内にあることである。このとき、円の中心の位置ベクトルを $\vec{p}=(p_1,p_2,p_3)$ として円の方程式を書くと、

$(\vec{x}-\vec{p})^2=r^2$ ……①

与えられた2点を通ることから、

$\vec{p}^2=r^2$ ……②

$r^2=(\vec{x_1}-\vec{p})^2=\vec{x_1}^2-2\vec{x_1} \cdot \vec{p}+\vec{p}^2$

$r$ を消去すると、

$\vec{x_1}^2-2\vec{x_1} \cdot \vec{p}=0$

$2\vec{x_1} \cdot \vec{p}=\vec{x_1}^2$

を得る。ここで、実数 $X$ を

$X=\vec{x_1}^2=x_1^2+y_1^2+z_1^2$

と定義しておく。すると、

$2(x_1p_x+y_1p_y+z_1p_z)-X=0$ ……③

次に、円のある平面内に、円の中心もあるので、

$\vec{p}\cdot\vec{n}=0$

$p_x n_x+p_y n_y+p_z n_z=0$

3次元空間中の円を考えているので、 $n_z\neq 0$ と設定しておくと、

$p_z=-\frac{1}{n_z}(p_x n_x+p_y n_y)$

$p_z=ap_x+bp_y$ ……④

ここで、実数 $a,b$ を

$a=-\frac{n_x}{n_z}$

$b=-\frac{n_y}{n_z}$

とおいた。④を③に代入して、

$2(x_1p_x+y_1p_y+z_1(ap_x+bp_y))-X=0$

$p_y=\frac{(X/2)-(x_1+a z_1)p_x}{y_1+b z_1}$

$p_y=c+d p_x$ ……⑤

ここで、実数 $c,d$ を

$c=\frac{X}{2(y_1+b z_1)}$

$d=-\frac{x_1+a z_1}{y_1+b z_1}$

で定義した。すると、④式より、

$p_z=ap_x+b(c+d p_x)=bc+(a+bd)p_x$

そして、②式より、

$p_x^2+p_y^2+p_z^2=r^2$

なので、

$p_x^2+(c+d p_x)^2+(bc+(a+bd)p_x)^2=r^2$

$p_x^2+(c+d p_x)^2+(bc+(a+bd)p_x)^2-r^2=0$

$(1+d^2+(a+bd)^2)p_x^2+2(cd+abc+b^2cd )p_x+c^2(1+b^2)-r^2=0$

これは、 $p_x$ についての2次方程式なので、中心の $x$ 座標は２つあり、円は2通り考えられる。 $p_x$ について解くと、2次方程式の解の公式より、

$p_x=\frac{-(cd+abc+b^2cd)\pm \sqrt{(cd+abc+b^2cd)^2-(1+d^2+(a+bd)^2)(c^2(1+b^2)-r^2)}}{(1+d^2+(a+bd)^2)}$

従って、各 $p_x$ に対して、④⑤式より、 $p_y,p_z$ が決定できる。与えられた半径 $r$ と中心の位置ベクトル $\vec{p}=(p_x,p_y,p_z)$ が求まったので、球の方程式は、①となる。

この式と法線ベクトルの式を用いて、変数 $z$ を消去すると、 $xy$ 平面に射影した円の方程式が得られ、同じ式を用いることで、求める円の $z$ 座標も求まる。

３点が与えられている場合

3点の内、 $x$ 座標の値が最も値が小さいものが原点になるように、座標を取り直す。すると、3点は $\vec{0}=(0,0,0),\vec{x_1}=(x_1,y_1,z_1),\vec{x_2}=(x_2,y_2,z_2)$ と表せる。全ての点を適切に平行移動することで、一般性は失われない。

この3点により、円の存在する平面が決定されるので、その平面の法線ベクトルに平行なベクトル $\vec{n}$ は、

$\vec{n}=\vec{x_1}\times\vec{x_2}=(n_x,n_y,n_z)=(y_1z_2-z_1y_2,z_1x_2-x_1z_2,x_1y_2-y_1x_2)$

と計算できる。円上の点の位置ベクトルを $\vec{x}$ とすると、円はこのベクトルに垂直なので、

$\vec{n}\cdot \vec{x}=0$ ……①

また、円の中心の位置ベクトルを $\vec{p}=(p_1,p_2,p_3)$ 、半径を $r$ とすると、

$(\vec{x}-\vec{p})^2=r^2$ ……②

となる。円上の3点が1直線上にあることはないので、位置ベクトル $\vec{x_1},\vec{x_2}$ は平行ではないので、この２つベクトルの線形結合で中心の位置ベクトルを表すことができる。すなわち、ある実数 $s,t$ を用いて

$\vec{p}=s\vec{x_1}+t\vec{x_2}$ ……③

と表せる。ここで、座標軸の取り方から、

$s,t\ge 0$

である。円の中心の位置ベクトルは、平面の法線ベクトルに垂直なので、

$0=\vec{n} \cdot \vec{p}$

$=\vec{n} \cdot (s\vec{x_1}+t\vec{x_2})$

$=(\vec{n} \cdot \vec{x_1})s+(\vec{n} \cdot \vec{x_2}) t=0$

$= t=-\frac{\vec{n} \cdot \vec{x_1}}{\vec{n} \cdot \vec{x_2} }s$

$t=\alpha s$ ……④

ここで、実数 $\alpha$ を

$\alpha=-\frac{\vec{n} \cdot \vec{x_1}}{\vec{n} \cdot \vec{x_2} }$

$=-\frac{n_x x_1+n_y y_1+n_z z_1}{n_x x_2+n_y y_2+n_z z_2}$

で定義した。

また、円は原点を通るので、

$\vec{p}^2=r^2$

$r=\sqrt{p_x^2+p_y^2+p_z^2}$ ……⑤

となる。従って、中心の位置ベクトルを決定できれば、円の半径がこの式により求まる。

②式と連立して、

$\vec{x}^2-2\vec{x}\cdot \vec{p}=0$

となる。円は、点 $vec{x_1}$ を通るので、

$\vec{x_1}^2-2\vec{x_1}\cdot (s\vec{x_1}+t\vec{x_2})=0$

④式を $t$ に代入して、

$\vec{x_1}^2-2\vec{x_1}\cdot (s\vec{x_1}+\alpha s\vec{x_2})=0$

$\vec{x_1}^2-2\vec{x_1}^2s-2\alpha s\vec{x_1}\cdot\vec{x_2}=0$

$2\vec{x_1}^2s+2\alpha s\vec{x_1}\cdot\vec{x_2}=\vec{x_1}^2$

$2(\vec{x_1}^2+\alpha \vec{x_1}\cdot\vec{x_2})s=\vec{x_1}^2$

$s=\frac{\vec{x_1}^2}{2(\vec{x_1}^2+\alpha \vec{x_1}\cdot\vec{x_2})}$

$s=\frac{x_1^2+y_1^2+z_1^2}{2(x_1^2+y_1^2+z_1^2+\alpha (x_1x_2+y_1y_2+z_1z_2))}$

以上より、3点の座標から $s$ が求まったので、④式より $t$ が求まり、結局、円の中心の位置ベクトル $\vec{p}$ が③式により、求まる。 $\vec{p}$ から半径 $r$ が、⑤式により求まるので、これらの量を用いて、球の方程式は②式により決定される。

流れる空の中で数学を。

とある数学好きの「手作りすうがく」と「気ままな雑記」。

【オイラー関数】FoxQ(または上岡)のφ類別予想【同値類】

オイラー関数と同値類

$r=1$ の場合

フェルマー 素数

数値実験

【Kindle】収縮遡及法(プログラム実装者求む！)【素因数分解】

【Kindle】多因数分解法【素因数分解】

【素因数分解】ぼくの考えたアルゴリズム【RSAに挑む】

2つの素数の積からなる合成数の素因数分解

素数階乗冪多項式

計算量

例

【Kindle】系統別・レベル別　整数問題集『序』を発売しました！【問題集】

【twitterのフォロワーさん】懸賞問題の解答例【3333人記念】

問題

想定解答

空間中の円の決定方法

事始めと問題

中心と1点と法線ベクトルが分かっている場合

半径と2点と円の平面の法線ベクトルがわかっている場合

３点が与えられている場合