まさかのNP困難?「九九って36種類しか数がないの不思議だよな」から始まる数学談義

九九から広がる素数の話
362
鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

九九って81マスあって最大値も81なのに36種類しか数がないの不思議だよな

2017-04-06 01:39:10
maki @maki_glenscape

$ python3 -c 'print(len(set([x * y for x in range(1, 10) for y in range(1, 10)])))' 36 へぇ、ほんとだ twitter.com/motcho_tw/stat…

2017-04-06 01:53:53
鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

1〜81まで全部の数をわたるあまり役に立ちそうにない九九がこちらです pic.twitter.com/tPvViKX9Ll

2017-04-06 01:42:01
拡大

※元ネタ

ThreaQ @3qua75

@motcho_tw 命題 A = {1,2,…,9} B = {1,2, …,81} f : A×A → B で全単射となるような関数fは自明である9N+Mの形を除いて存在する 変態が真であることを証明しそう

2017-04-06 01:43:40
鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

@3qua75 行ごとゴッソリ入れ替えたり、さっきの階段を2倍してmod81とかすればいいはずなので別にいくらでも作れるとは思いますね。

2017-04-06 01:53:42
ThreaQ @3qua75

@motcho_tw 確かにそんな感じですよね 逆関数の表現もmodの処理や逆行列あたりでどうとでもなりそうですね

2017-04-06 01:56:16
あるえむ・RedMuffleR @R_M___

九九に準じてn*nを埋めたときにでてくる数の種類ってnから求まる?

2017-04-06 01:40:25
あるえむ・RedMuffleR @R_M___

逆に、81までの合成数のうち九九に出てこないのはいくつで、nnで一般化出来るか?

2017-04-06 01:53:58
鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

n以下の2数の積としてとりうる数の総数の求め方って...?

2017-04-06 01:56:15
ゆぅくりっど @akatanana

@motcho_tw n^2の種類 1→1 2→3(+2) 3→6(+3) 4→9(+3) 5→14(+5) 6→18(+4) 7→25(+7) 8→30(+5) 9→36(+6) 10→42(+6) 11→53(+11) 12→59(+6) nが素数の時n増えるし規則性ありそう

2017-04-06 02:00:00
ゆぅくりっど @akatanana

@motcho_tw 偶数の半素数2pも(p+1)の増加で表せるので、増加分は約数の個数に何か関係がありそう

2017-04-06 02:05:31
TokusiN @toku51n

@akatanana @motcho_tw N-1からNになった時の増加量の上界はN-Nの最大の真の約数+1で示せますが、実際には例えば9の時は9x4の分が増えず、12の時は12x6の分が増えないなど、素因子を組み替えてNより小さい2数の積で表せるかどうかに依存するのでエレガントな式は無さそうです。

2017-04-06 02:24:46
TokusiN @toku51n

@akatanana @motcho_tw (Nの最大の真の約数)~Nのうち、Nを2数の積a*bと表した時にc<a, d<bであるようなcとdの積で表せるような数を除いた数の個数だけ増加する。 つまりは、9の時は3~9のうち、4は2*2と表せるので、残りの6個。12の時は6~12のうち6は2*3と表せるので残りの6個。

2017-04-06 02:33:22
あるえむ・RedMuffleR @R_M___

前提知識がないんですけど、n以下の合成数の数ってそもそもnを用いた計算式で表せるんですか?

2017-04-06 01:57:50
鯵坂もっちょ🐟『つれづれなる数学日記』発売中 @motcho_tw

@R_M___ n以下のnと互いに素な数の個数を与えるオイラーのトーシェント関数でなんかできそう...?

2017-04-06 02:01:42
あるえむ・RedMuffleR @R_M___

@motcho_tw n-(n以下の素数の数)という感じですかね いいですね

2017-04-06 02:02:50
TokusiN @toku51n

@R_M___ @motcho_tw ja.wikipedia.org/wiki/%E3%83%AA… リーマンの素数公式を使って、nから引けば合成数の数も計算できます。

2017-04-06 02:03:27
リンク Wikipedia リーマンの素数公式 リーマンの素数公式(Riemann's prime number formula、あるいは明示公式、explicit formula)とは、ドイツの数学者ベルンハルト・リーマンが1859年に自身の論文「与えられた数より小さい素数の個数について」において発表した、素数の個数関数 π(x) をゼータ関数の非自明な零点を用いて表示する公式である。素数公式のリーマン自身の証明は同論文の他のいくつかの結果同様不完全だったが、フォン・マンゴルドによって1895年に厳密に証明された。リーマンの定義した素数の個数関数とは
TokusiN @toku51n

@motcho_tw @R_M___ リーマンの素数公式は、N以下の素数の数(合成数の数)を計算する式があるか、に対する答えでしょう。実際に巨大なNに対しては実際に素数を数えるよりもこの式で計算する方が計算時間は短くて済むようです。

2017-04-06 02:06:09