MENU
275,766

玠数ではなくお   (2)

> 䞀点、質問をさせおいただきたく思いたす。
> ミラヌラビンの底には玠数をずるのが良いのでしょうか 確率の評䟡に圱響をあたえたすか
圱響は倧いにあるず思いたす。
䟋えば2で確率的玠数ず刀定されたら4や8でも倚分確率的玠数ず刀定されたすが、確率が䞊がるわけではないですね。
同様に、2ず3で確率的玠数ずなれば6でも倚分確率的玠数ず刀定されるず思いたす。
「倚分」ずしおいるのは堎合によるかも知れないからですが、圱響する可胜性があるのは間違いないですから、同じ玠因数を持぀数は避けた方が良いかず思いたす。

匕甚しお返信線集・削陀(線集枈: 2023幎05月20日 20:15)

> 同様に、2ず3で確率的玠数ずなれば6でも倚分確率的玠数ず刀定されるず思いたす。

私はこれはなんずなく停ではないかず思いたす。
反䟋はただ芋぀けられおいたせんが。

匕甚しお返信線集・削陀(未線集)

> 2ず3で確率的玠数ずなれば6でも倚分確率的玠数
䟋えばnが玠数でn-1=16mmは奇数だずするず、mod nで
(a^m,a^(2m),a^(4m),a^(8m),a^(16m))≡
(1,1,1,1,1),
(-1,1,1,1,1),
(A,-1,1,1,1),
(B,C,-1,1,1),
(D,E,F,-1,1)
(A,B,C,D,E,Fは-1,0,1以倖の数)
のいずれかになるわけですが、
a=2で
(A,-1,1,1,1)
a=3で
(D,E,F,-1,1)
のようになったずするず、a=6では
(A*D,-E,F,-1,1) A*Dも-EもFも-1,0,1以倖
のようになり、やはり確率的玠数ず刀定されたす。
問題は
底2で (A,B,C,-1,1)
底3で (D,E,F,-1,1)
のように同じタむミングで-1になった堎合で、
このような堎合はC*F≡-1になるずは限りたせんので
底6で確率的玠数ず刀定されるかどうかわかりたせん。
これの反䟋があるのかどうかもわかりたせん。ありそうな気はしたすが
ずいうわけで、少なくずも-1になるタむミングが異なる玠因数の積を
底にした刀定は確率の向䞊になりたせんので、同じ玠因数は避けた方がいい、
ずいうこずを蚀いたかったのです。

匕甚しお返信線集・削陀(未線集)

> 少なくずも-1になるタむミングが異なる玠因数の積を底にした刀定は確率の向䞊になりたせんので、同じ玠因数は避けた方がいい、

これ、実は少し考えなければいけないずころではないかず思いたす。

䟋えば 13 をミラヌラビンテストにかけるずしたす。
このずき、a = 3, 7, 11 ずいう 3 ぀の玠数で刀定を行うこずは有効でしょうか

普通の自然数の䞖界では、7 は玠数です。
しかし、13 をミラヌラビンテストにかける堎合、行う蚈算は党お mod 13 の䞖界です。
その䞖界では、3*11=7 ですから、7 はらすかるさんが仰るずころの避けた方がいい数に該圓したす。

こう考えおみるず、確率向䞊に貢献する a ず貢献しない a の刀別は「通垞の自然数の䞖界で合成数だから」ずいう単玔な話ではない気がしおいたす。

匕甚しお返信線集・削陀(未線集)

らすかるさん、DD++ さん。

「ミラヌラビンの底には玠数をずるのが良いのでしょうか 確率の評䟡に圱響をあたえたすか」ずいう私の疑問にお答えくださっおありがずうございたす。

私のほうでも調べおみたこずがありたす。

Miller-Rabin 玠数刀定法は確率的に玠数らしい数かどうかを刀定するのに有甚ですが、
底のずりかたによっおは、限定的な範囲内にお、確率100で刀定できる堎合がありたす。泚目点ずしおは、この底の取り方です。

①
a = {2, 3, 5, 7, 11, 13, 17} を詊せば 341550071728321 以䞋の玠数刀定を確率100でできる。

②
a = {2, 3, 5, 7, 11, 13, 17, 19, 23} を詊せば 3825123056546413051 以䞋の玠数刀定を確率100%でできる

うえの①、②では、底ずしお玠数のみの組を䜿っおいたす。

なお、①、②はOEISの https://oeis.org/A014233 によりたす。

䞀定の範囲の数に぀いお玠数刀定を確率100%で刀定するには
底ずしおは玠数の組を䜿うのがよいのかず
思ったずころですが、䞀方においお、これに反するような、
次のようなサむトがありたした。


Deterministic variants of the Miller-Rabin primality test
http://miller-rabin.appspot.com/

䞊のサむトによれば7぀の底を䜿っお
2^64 たでの数を確定的に玠数刀定できる底の䟋ずしお
2, 325, 9375, 28178, 450775, 9780504, 1795265022
が挙げられおいたす。
偶数か5の倍数かが、底になっおいお
唖然ずしたした。

悩みは続きたす。

匕甚しお返信線集・削陀(未線集)

奇玠数の抜け穎

奇玠数Pがそれより小さい玠数pず自然数kを甚いお
P=p+k*(k+1)/2
の圢匏で衚せるものを探すず
3=2+1*2/2
5=2+2*3/2

13=3+4*5/2
(7+3*4/2も可胜)

31=3+7*8/2

97=19+12*13/2
(31+11*12/2,61+8*9/2も可胜)


の様にP,pの間でk*(k+1)/2の繋がりが構成されおくる。

ずころで、いくら頑匵っおもその構成が芋぀からない奇玠数Pが存圚しおいたすが
それは䜕でしょうか

匕甚しお返信線集・削陀(未線集)

7ず61かな

(远蚘)
プログラムを䜜っお調べたら、211も該圓しおいたした。

匕甚しお返信線集・削陀(線集枈: 2023幎05月22日 08:06)

GAI様、らすかる様、こんにちは。

P=p+k*(k+1)/2

ずいうず
P=p+(1+2+3+・・・+k)
ずいうこずですか

匕甚しお返信線集・削陀(未線集)

この3個以倖に芋圓たらないのが面癜かったです。
Pが倧きくなっおいくず、構成できる堎合の可胜性が圧倒的に増倧しおいくのでこれ以䞊は芋぀からないのでしょうね。

匕甚しお返信線集・削陀(未線集)

ミラヌ・ラビン法のStorong pseudoprimeの発芋においお
底を2,3,6の぀で調査すれば110^8たでには
次の21個が発芋でき
1373653;[829, 1; 1657, 1]
1530787;[619, 1; 2473, 1]
1987021;[997, 1; 1993, 1]
2284453;[1069, 1; 2137, 1]
3116107;[883, 1; 3529, 1]
5173601;[929, 1; 5569, 1]
6787327;[1303, 1; 5209, 1]
11541307;[1699, 1; 6793, 1]
13694761;[2617, 1; 5233, 1]
15978007;[1999, 1; 7993, 1]
16070429;[1637, 1; 9817, 1]
16879501;[1453, 1; 11617, 1]
25326001;[2251, 1; 11251, 1]
27509653;[3709, 1; 7417, 1]
27664033;[3037, 1; 9109, 1]
28527049;[2389, 1; 11941, 1]
54029741;[1733, 1; 31177, 1]
61832377;[3517, 1; 17581, 1]
66096253;[5749, 1; 11497, 1]
74927161;[6121, 1; 12241, 1]
80375707;[4483, 1; 17929, 1]

同じく底を2,3,7で調査するず次の1個が
2284453;[1069, 1; 2137, 1]

たた底を2,3,11でも
2284453 が発芋される。

底を2,3,13なら
6787327;[1301,1;5209,1]が出珟

ずころでP=p+k*(k+1)/2
ず構成できなかったタむプ(2を含めお),2,7,61を底にしお調査すれば、
䞀぀も擬玠数は存圚しないこずが刀明する。

りィキペディアのミラヌ-ラビン玠数刀定法の蚘事によれば
もし
n<4759123141なら、底を2,7,61に぀いお調べればよい。 
ずある。
n=10^810^10では
4759123141;[48781, 1; 97561, 1] が出珟しおしたう。

これず䜕かしら関係しおいるかもず思われたした。

匕甚しお返信線集・削陀(線集枈: 2023幎05月23日 06:27)

玠数ではなくお  

任意の正の敎数 n に぀いお
(334*10^n -1)/9
は、垞に合成数です。

さお、どうしおでしょうか

匕甚しお返信線集・削陀(線集枈: 2023幎05月13日 22:23)

正の敎数 n に぀いお
(109*10^n -1)/9
は、かならずしも合成数ずはかぎりたせん。

さお、どうしおでしょうか

匕甚しお返信線集・削陀(線集枈: 2023幎05月13日 22:23)

[前者]
分子が3339,33399,333999,3339999, のようになる

n=3mのずき
分子が333999,333999999,333999999999, のように3m+3桁だから
333で割り切れ、333÷9=37なので䞎匏は37で割り切れる

n=3m-1のずき
分子は33399,33399999,33399999999, だから
䞎匏は3711,3711111,3711111111, のようになり
党桁の合蚈が3の倍数だから3で割り切れる

n=6m-2のずき
分子は3339999,3339999999999,3339999999999999999, のようになり
3339999÷13=256923、999999÷13=76923だから
分子÷13は256923,256923076923,256923076923076923, ずなり分子は13で割り切れる
そしお13は分母の9ず互いに玠だから䞎匏も13で割り切れる

n=6m-5のずき
分子は3339,3339999999,3339999999999999, のようになり
3339÷7=477、999999÷7=142857だから
分子÷7は477,477142857,477142857142857, ずなり分子は7で割り切れる
そしお7は分母の9ず互いに玠だから䞎匏も7で割り切れる

たずめ
n=3mのずき37で割り切れ、
n=3m-1のずき3で割り切れ、
n=6m-2のずき13で割り切れ、
n=6m-5のずき7で割り切れるから
垞に合成数。

[埌者]
n=136のずき玠数ずいう反䟋があるから合成数ずは限らない。

匕甚しお返信線集・削陀(未線集)

玠晎らしいです。

なおネタ元は以䞋です。
https://oeis.org/A112386

远䌞
https://oeis.org/A107612
こちらも、参考にしたした。

匕甚しお返信線集・削陀(線集枈: 2023幎05月14日 11:13)

A112386はなぜこんなにちょっずしかデヌタがないんでしょうね。
せっかく37の䟋を茉せおいるんだから
251,26111,271,281,29111111,3011,311,3211111111111111111111111111111111111,34111111,3511,361111,-1
ぐらい茉せればいいのに。
先頭の3行のずころではなくLINKSにある衚のこずです
ちょっず調べおたくさん远加しおみようかな。

匕甚しお返信線集・削陀(未線集)

正攻法で真面目に玠因数分解をしおいくず
56111
11
(505*10^n -1)/9
での玠数探しで蚈算量が爆発するのではず
危惧いたしたす。

匕甚しお返信線集・削陀(線集枈: 2023幎05月14日 13:50)

以前あった 381111

 の話かず思ったら、今回は 371111

 なのですね。

http://shochandas.xsrv.jp/mathbun/mathbun1315.html

匕甚しお返信線集・削陀(未線集)

381
1
は個人的は未解決だったのでした。
これは
(343*10^n -1)/9
ですが

1n ≡ 0 (mod 3)
のずきには、
n = 3*k
ずおいお
343 = 7^3
に留意するず
((7*10^k)^3 -1^3)/9
ですから、分子は3乗−3乗の圢ずなり
因数分解できるこずから
合成数でありそうです。

n ≡ 1 (mod 3)
のずきには
381, 381111, 381111111


などですから
の倍数です。

n ≡ 2 (mod 3)
のずきには
どうしたものでしょうか

匕甚しお返信線集・削陀(未線集)

あっそうですね。

n ≡ 2 (mod 3)
ずいうこずは

3811, 3811111, 3811111111
ですが、
3811 は 37 の倍数、
111 は 37 の倍数ですね。

匕甚しお返信線集・削陀(未線集)

(a10^n-1)/9ずかa10^n-1にしたらどうでしょう。

aは2m,2m+1ずか、3m,3m+1,3m+2ずか、10m,10m+1,10m+2,10m+3,10m+4,10m+5,10m+6,10m+7,10m+8,10m+9なんかどうでしょう・・・・・

匕甚しお返信線集・削陀(線集枈: 2023幎05月15日 07:15)

䞀応蚀い出しっぺなので、圢だけでもなんずか・・・・・

a=10mずするず、(mは自然数
a10^n-1=10m10^n-1=(m-1)10^(n+1)+10^(n+1)-1
ここで、10^(n+1)-1=99・・99=(11・・11)x9
11・・11を考えるず1がn+1䞊んだ数なので、n+1が合成数なら、かならず割れる。
n+1=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、n+1が偶数なら、11の倍数。
n+1が3の倍数なら、111(=3x37)の倍数。
n+1が5の倍数なら、11111(=41x271)の倍数。
n+1が7の倍数なら、1111111(=239x4649)の倍数。
n+1が11の倍数なら、11111111111(=21649x513239)の倍数。
n+1が13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以䞋省略
たた、(m-1)10^(n+1)は、(m-1)x2^(n+1)x5^(n+1)
したがっお、
n+1が偶数なら、m-1は11の倍数なら、a10^n-1は11の倍数。
n+1が3の倍数なら、m-1は3か37の倍数なら、a10^n-1は3か37の倍数。
n+1が5の倍数なら、m-1は41か271の倍数なら、a10^n-1は41か271の倍数。
以䞋省略

a=10m+1ずするず、(mは自然数
a10^n-1=(10m+1)10^n-1=m10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えるず1がn䞊んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以䞋省略
たた、m10^(n+1)は、mx2^(n+1)x5^(n+1)
したがっお、
nが偶数なら、mは11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、mは41か271の倍数なら、a10^n-1は41か271の倍数。
以䞋省略

a=10m+2ずするず、(mは自然数
a10^n-1=(10m+2)10^n-1=(m+1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えるず1がn䞊んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以䞋省略
たた、(m+1)10^(n+1)は、(m+1)x2^(n+1)x5^(n+1)
したがっお、
nが偶数なら、(m+1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(m+1)mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(m+1)mは41か271の倍数なら、a10^n-1は41か271の倍数。
以䞋省略

匕甚しお返信線集・削陀(未線集)

> "Dengan kesaktian Indukmu"さんが曞かれたした:
> 正攻法で真面目に玠因数分解をしおいくず
> 56111
11
> (505*10^n -1)/9
> での玠数探しで蚈算量が爆発するのではず
> 危惧いたしたす。

A069568;
によりたすずの埌に1が18470個も続くようです。

匕甚しお返信線集・削陀(線集枈: 2023幎05月16日 07:09)

"GAI"さんが曞かれたした:

> A069568;
> によりたすずの埌に1が18470個も続くようです。

わあっ
A069568
にはちやんず 38111
111
に぀いお も 觊れおあるのですね
芋萜ずし、恥ずかしいです。

私は次に挙げる「暡範解答」をみおいお
意味がわからずに難儀しおいたのでした。

http://bxmo.org/problems/bxmo-problems-2015-zz.pdf

3乗マむナス3乗だず気が぀くこずで
個人的には玍埗したのですが
いただにこの暡範解答の筋立おの意味を
぀かみかねおいたす。

匕甚しお返信線集・削陀(線集枈: 2023幎05月16日 10:18)

a=10m+rずするず、(mは自然数、rは3,4,5,6,7,8,9のいずれか
a10^n-1=(10m+r)10^n-1=(m+r-1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えるず1がn䞊んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以䞋省略
たた、(m+r-1)10^(n+1)は、(m+r-1)x2^(n+1)x5^(n+1)
したがっお、
nが偶数なら、(m+r-1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(m+r-1)mは3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(m+r-1)mは41か271の倍数なら、a10^n-1は41か271の倍数。
以䞋省略

a=10m+sずするず、(mは自然数、sは1,2,3,4,5,6,7,8,9のいずれか
a10^n-1=(10m+s)10^n-1=(m+s-1)10^(n+1)+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
より、10^n-1は、の倍数。
たた、(m+s-1)10^(n+1)は、(m+s-1)x2^(n+1)x5^(n+1)
より、m+s-1がの倍数なら、a10^n-1は、の倍数。

a=10mずするず、(mは自然数
a10^n-1=(10m)10^n-1=(m-1)10^(n+1)+10^(n+1)-1
ここで、10^(n+1)-1=99・・99=(11・・11)x9
より、10^(n+1)-1は、の倍数。
たた、(m-1)10^(n+1)は、(m-1)x2^(n+1)x5^(n+1)
より、m-1がの倍数なら、a10^n-1は、の倍数。

匕甚しお返信線集・削陀(線集枈: 2023幎05月16日 11:59)

> Dengan さん

たさしく No.1089 ず No.1090 で述べられおいる通りの蚘述に芋えたすが、疑問点はどこなのでしょう

匕甚しお返信線集・削陀(未線集)

DD++ さん。
ご指摘をありがずうございたした。
仰る通りです。

慎重に読み盎したずころ、私の誀読ずわかりたした。

正しくは暡範解答の PDF にありたすずおり、
If n = 3*k ≡ 0 (mod 3), observe that
9*a*(3*k) = 34299 · · · 99
= (7*10^k)^3 −1
which is properly divisible by 7*10^k − 1,
a number that is larger than 9.
Hence a(3k) admits a non-trivial factor and so is not prime.

なのですが、私はずんでもない読み間違いを
しおおりたした。すなわち。
If n = 3*k ≡ 0 (mod 3), observe that
9*a*(3*k) = 34299 · · · 99
= (7*10^k)^3 −1
which is properly divisible by (7*10^k)^3 −1
,
a number that is larger than 9.
Hence a(3k) admits a non-trivial factor and so is not prime. 

こんな読み方をしおいおはダメダメに決たっおいたす。[ pdf を読みながらノヌトに写経したずきの転蚘ミスが最初のきっかけです。いったん思い蟌むず沌にはたる悪い癖が今回も発生したしたした。]

DD++ さん、ご教瀺をありがずうございたした。
たた、みなさたに぀きたしおは
私からのわけの分からない投皿で
埡迷惑をおかけしたしたこず、
お詫び申し䞊げたす。

匕甚しお返信線集・削陀(未線集)

> "らすかる"さんが曞かれたした:
> A112386はなぜこんなにちょっずしかデヌタがないんでしょうね。

1331, 13311, 133111, 1331..1
がダバそうです。
これは
(1198*10^n -1)/9
ですが、任意の正の敎数 n に぀いお
合成数のような
なかなか玠数がみ぀からず
さりずおなぜ合成数になるのか
芋通しも぀けられず、、、

匕甚しお返信線集・削陀(未線集)

間違っおおりたした。よくよく考えるず、これでいいず思いたす。

a10^n-1=(a-1)10^n+10^n-1
ここで、10^n-1=99・・99=(11・・11)x9
11・・11を考えるず1がn䞊んだ数なので、nが合成数なら、かならず割れる。
n=6=2x3なので、111111=11x(10101)=111x(1001)=11x3x7x13x37=(111)x(1001)=(3x37)x(7x11x13)
これより、nが偶数なら、11の倍数。
nが3の倍数なら、111(=3x37)の倍数。
nが5の倍数なら、11111(=41x271)の倍数。
nが7の倍数なら、1111111(=239x4649)の倍数。
nが11の倍数なら、11111111111(=21649x513239)の倍数。
nが13の倍数なら、1111111111111(=53x79x265371653)の倍数。
以䞋省略
たた、(a-1)10^nは、(a-1)x2^nx5^n
したがっお、
nが偶数なら、(a-1)は11の倍数なら、a10^n-1は11の倍数。
nが3の倍数なら、(a-1)は3か37の倍数なら、a10^n-1は3か37の倍数。
nが5の倍数なら、(a-1)は41か271の倍数なら、a10^n-1は41か271の倍数。
以䞋省略

たた、a-1がの倍数なら、a10^n-1は、の倍数。
特に、a-1が9の倍数なら、a10^n-1は、9で割れお、{(a-1)/9}x10^n+(11・・11)ずなる。

匕甚しお返信線集・削陀(線集枈: 2023幎05月17日 08:34)

> 1331, 13311, 133111, 1331..1
> がダバそうです。
> これは
> (1198*10^n -1)/9
> ですが、任意の正の敎数 n に぀いお
> 合成数のような

おそらく
(1198*10^2890-1)/9 133の埌に1が2890個
が玠数だず思いたす。

しかし、GAIさんが曞かれたA069568に118たでのデヌタが茉っおいたすので、
A112386は56で巚倧な数になるこずを考えおもせめお55たでは茉っおいおも
いいのに、ずは思いたす。

(远蚘)
「(1198*10^2890-1)/9は倚分玠数」の理由
ミラヌラビン法で15000以䞋の玠数1754個をそれぞれ底にしおテストしたずころ、
すべおパスしたしたので、「合成数である確率」は1/10^1000未満ずなりたす。

匕甚しお返信線集・削陀(線集枈: 2023幎05月18日 03:40)

昚日はずんちんかんなこずを曞いおしたいたした。毎床のこずですみたせん。

根本的に、間違いであるこずを指摘したした。

緑色のうんざりはちべえをクリックしおください。

匕甚しお返信線集・削陀(線集枈: 2023幎05月18日 08:57)

> "らすかる"さんが曞かれたした:
> おそらく
> (1198*10^2890-1)/9 133の埌に1が2890個
> が玠数だず思いたす。

> 「(1198*10^2890-1)/9は倚分玠数」の理由
> ミラヌラビン法で15000以䞋の玠数1754個をそれぞれ底にしおテストしたずころ、
> すべおパスしたしたので、「合成数である確率」は1/10^1000未満ずなりたす。


らすかるさん。怜蚌をありがずうございたした。
確率的玠数ずいうこずですね。

䞀点、質問をさせおいただきたく思いたす。
ミラヌラビンの底には玠数をずるのが良いのでしょうか 確率の評䟡に圱響をあたえたすか

匕甚しお返信線集・削陀(線集枈: 2023幎05月20日 18:11)

防衛医倧什和4のIV

>   がではない実数であるずき、敎匏 / の取りうる倀の範囲を求めよ。

敎匏  
これ、実際の入詊の原文ママなんですか

匕甚しお返信線集・削陀(未線集)

「実際の入詊の原文」通りなのですが、明らかに誀字ですよね。では「数匏」に修正しおおきたす。

匕甚しお返信線集・削陀(未線集)

たあ、防衛医倧だず数孊の専門家はいないでしょうから、そこらぞんの正確さは蔑ろにならざるを埗ないんでしょうねえ。

匕甚しお返信線集・削陀(未線集)

玠数 䞀億番目

「2038074743」らしいのですが
この手の問題は、
ずか、を含む玠数ずか、キリがないですね。
求められる努力ず技術は尊重したす。

匕甚しお返信線集・削陀(未線集)

玠数を2から玄1億個を求めるのに、25秒でできたす。(CPU:i5-2500)
経過時間= 0 分 25 秒
玠数個数=105080509
たあ、ここでは、ふさわしい話でもないし、膚倧なので、Webにもあげられないし、意味がないですね。
求めた最埌の5個は、
2147117417 2147117419 2147117507 2147117509 2147117519
でした。

匕甚しお返信線集・削陀(線集枈: 2023幎05月14日 18:32)

「敎数問題」の今日の曎新

41 の他に 27 も解ではないでしょうか

27 + (2+7) + (2*7) = 27 + 9 + 14 = 50

匕甚しお返信線集・削陀(未線集)

DD++ さん、誀りをご指摘いただきありがずうございたす。
蚈算を芋盎したら、はじいおはいけない解をはじいおいたした。
解は修正したした。

匕甚しお返信線集・削陀(未線集)

たち針の朚

区別が぀く n 本のたち針ず、1 個の針山がありたす。
このたち針は、自身の頭がたた針山のようになっおいお、そこに別のたち針を刺すこずができたす。

この n 本のたち針党おを、盎接的たたは間接的に針山に刺すこずを考えたす。

䟋えば、n=2 で赀いたち針ず青いたち針がある堎合、
「䞡方を盎接針山に刺す」
「赀を盎接針山に刺し、青を赀の頭に刺す」
「青を盎接針山に刺し、赀を青の頭に刺す」
の 3 通りの刺し方がありたす。

䟋えば、n=3 で赀青黄のたち針がある堎合、
「赀ず青を盎接針山に刺し、黄は赀の頭に刺す」
「青を盎接針山に刺し、赀ず黄を䞡方ずも青の頭に刺す」
「黄を盎接針山に刺し、赀を黄の頭に、青を赀の頭に刺す」
などなど、党郚で 16 通りの刺し方がありたす。

問題。
(1) n=3 の残りの 13 通りを芋぀けおください。
(2) n=4 の堎合、刺し方は 125 通りありたす。党お芋぀けられるでしょうか。
(3) n=5 の堎合、刺し方は䜕通りあるでしょう。
(4) n=6 や n=7 の堎合はどうでしょう。
(5) 䞀般の n の堎合に解けるでしょうか


n=7 たではずおも綺麗な結果になりたす。
n≧8 でも同じ法則が続くのならば、䞀般の n に぀いおパッず解く方法がありそうですが、私は今のずころ発芋できおいたせん。

グラフ理論方面にヒントがありそうな気がする、ずいうかモロにグラフ理論の範囲じゃないかず思うのですが、うたく情報が芋぀けられたせん。
どなたか、情報をお持ちでしたらぜひ教えおください。

匕甚しお返信線集・削陀(未線集)

n本の堎合に刺し方がF(n)通りあるずする。
ただし、n=0の堎合はF(0)=1ずする。

たち針がn+1本ある時を考える。
特定の1本のたち針[èµ€]に着目し、その先端偎にあるたち針の本数をi本、頭偎にあるたち針の本数をn-i本ずする(0≩i≩n)。
n本のたち針をこの2グルヌプに分ける方法はCombination(n,i)通り。
先端偎にあるi本のたち針の刺し方はF(i)通りで、その各々に察したち針[èµ€]を刺す堎所がi+1通り(針山ずi本のたち針の頭)。
頭偎にあるn-i本のたち針の刺し方はF(n-i)通り(たち針[èµ€]の頭を針山ずみなせばよいため)。
よっお挞化匏は、
F(n+1) = Σ[i=0...n] Combination(n,i) * F(i) * (i+1) * F(n-i)
ずなる。

F(n)の匏の圢は予想できおいるので数孊的垰玍法で瀺せばよい。

  のですが、匏倉圢できずに詰たっおいたす。

匕甚しお返信線集・削陀(未線集)

そうなんですよ。

Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n

Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

このどっちかが成り立っおくれれば話は終わりなんですけど、
「私の備忘録」->「代数孊分野」->「二項係数の性質」
にもそれっぜい匏はないんですよね。
二項係数関係の総和は、底か指数かどちらか固定されおいたら「よくある問題」なんですが、䞡方倉わっおいくのはほずんど芋たこずがありたせん。

匕甚しお返信線集・削陀(未線集)

どれが積でどれが添字か党くわからないので、添字は [ ] で曞くなど区別しやすい衚蚘にしおもらうこずはできたすか

匕甚しお返信線集・削陀(未線集)

やっず情報を芋぀けたした。
https://en.m.wikipedia.org/wiki/Cayley%27s_formula

こっちにある蚌明法がわかりやすかったので、この問題の甚語や数倀に合わせながら翻蚳したす。
https://en.m.wikipedia.org/wiki/Double_counting_(proof_technique)


たず、針山もたち針ずみなしたす。
぀たり「針山をたち針の頭に刺す」が、なぜかできそうな気分になっおおきたす。

以䞋の操䜜を行いたす。

(1) n+1 本のたち針本圓は針山であるものも含むを机䞊に䞊べたす。

(2) n+1 個の頭から 1 ぀を遞びたす。そしお、その頭ず぀ながっおおらず、か぀どこにも刺しおいない針先 n 個のうち 1 ぀を遞びたす。遞んだ針先を遞んだ頭に刺したす。

(3) n+1 個の頭から 1 ぀を遞びたす。そしお、その頭ず぀ながっおおらず、か぀どこにも刺しおいない針先 n-1 個のうち 1 ぀を遞びたす。遞んだ針先を遞んだ頭に刺したす。

(4) さらに繰り返し、合蚈 n 回行いたす。遞べる針先の遞択肢が 1 ぀ず぀枛っおいき、n 回目では 1 個のうち 1 個を遞んで刺すこずになりたす。

(5) ある 1 本のたち針の頭に他の n 本が党郚刺さっおいるオブゞェ朚ず呌びたいが根っこが刺さっおない  ができたら操䜜終了です。

各遞択肢の個数を考えるず、この操䜜の方法は党郚で (n+1)^n * n! 通りありたす。
ただし、同じ圢のオブゞェがたち針を刺す順番違いで n! 個ず぀できるので、オブゞェの皮類は (n+1)^n 通りです。

そしお、このオブゞェには n+1 本の各たち針が䞀番䞋になるパタヌンが (n+1)^(n-1) 通りず぀含たれたす。
぀たり、たち針ずみなしおいた針山の䞊に本物のたち針 n 本が党郚刺さっお、きちんず題意通りの圢になっおいるパタヌンは (n+1)^(n-1) 通りずなりたす。


これで「最長数列の総数」も解決したこずになりたす。
あるいは、考え方を流甚すれば「たち針の朚」の問題に垰着させるたでもなくあっちを解けるかも。
䞊手い説明ができるかどうか考えおみたす。

そしお残った No.1051 の恒等匏の謎。
組み合わせを甚いお蚌明できたこずになりたすが、匏倉圢で瀺せるのかどうか。

匕甚しお返信線集・削陀(未線集)

DD++さん
> そしお残った No.1051 の恒等匏の謎。
> 組み合わせを甚いお蚌明できたこずになりたすが、匏倉圢で瀺せるのかどうか。

匏倉圢できたした。
nCk を C[n,k] ず曞くこずにしたす。

事前準備その
C[n,i] * C[n-i,j] = C[n,j] * C[n-j,i]
蚌明略

事前準備その
f(k)をkのn-1次以䞋の倚項匏ずしお、
Σ[k=0...n] C[n,k] * (-1)^k * f(k) = 0
蚌明は、「私の備忘録」->「代数孊分野」->「二項係数の性質」の䞭の性質(5)ず(28)、あるいは
 平成幎月日から日にかけおのらいさん・攻略法さん・ さん・さんのやりずり を参照


それでは本番 (2行目から3行目の眮き換えはh=n-k)
Σ[h=0...n] C[n,h] * (h+1)^h * (n-h+1)^(n-h-1)
= Σ[h=0...n] C[n,n-h] * (n-h+1)^(n-h-1) * (h+1)^h
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * (n-k+1)^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * ((n+2)-(k+1))^(n-k)
= Σ[k=0...n] C[n,k] * (k+1)^(k-1) * { Σ[m=0...n-k] C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-k-m) }
= Σ[k=0...n] Σ[m=0...n-k] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= Σ[m=0...n] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,k] * C[n-k,m] * (n+2)^m * (-1)^(n-k-m) * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] Σ[k=0...n-m] C[n,m] * C[n-m,k] * (n+2)^m * (-1)^(n-m) * (-1)^k * (k+1)^(n-m-1)
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * { Σ[k=0...n-m] C[n-m,k] * (-1)^k * (k+1)^(n-m-1) }
= (n+2)^n + Σ[m=0...n-1] C[n,m] * (n+2)^m * (-1)^(n-m) * 0
= (n+2)^n

匕甚しお返信線集・削陀(未線集)

おお、なるほど、そんな方法で k+1 の指数から k を消せるずは。
これで

> Σ[k=0...n] nCk * (k+1)^k * (n-k+1)^(n-k-1) = (n+2)^n
>
> Σ[k=0...n] nCk * (k+1)^(k-1) * (n-k+1)^(n-k-1) = 2*(n+2)^(n-1)

の䞊の匏は瀺されたしたね。
䞋の匏はりらひいさんの蚌明の 1 行目 h をそのたた k に曞き換えず 3 行目を足したものが最終結果の 2 倍になるこずから埗られたす。

これらの総和、い぀かどこかでたた䜿うこずがあるかもしれないので、蚌明方法ずもども芚えおおきたいず思いたす。
ありがずうございたす。

匕甚しお返信線集・削陀(未線集)

先日の匏倉圢No.1068をもう䞀床眺めおいお思ったのですが、次の匏

(a+b)^n / a = Σ[k=0...n] C[n,k] * (a+k)^(k-1) * (b-k)^(n-k)

が成り立぀んですね。
ただし、 a≠0ずしたす。
蚈算は先日の3行目最終行ずたったく同様です。
先日の匏は、 a=1, b=n+1 の堎合にあたりたす。

a,bは敎数に限らず実数でいけるのが面癜いずころですね。

匕甚しお返信線集・削陀(未線集)

無限

ふず、無限の数孊的な、定矩が気になりたした。
コンピュヌタヌは、無限をどう理解するのか
具䜓的には、1÷3ずか、近䌌でしか理解できないず教わりたしたが、
最近の゚クセルでは、䞃桁䜍で理解しおいるようです。

匕甚しお返信線集・削陀(未線集)

ある本に、無限ずいうこずばが、自然に出おいたす。
限りなくずか、無数ずいう蚀葉が、出おきたす。圢匏䞻矩ず公理䞻矩、
盎芳䞻矩が、混雑しおいたす。

匕甚しお返信線集・削陀(未線集)

https://shayashiyasugi.com/wwwshayashijp/HistoryOfFOM/Axiomatik/axiomatism.html

長いですが、興味がおありの方もいらっしゃるこずかず。

匕甚しお返信線集・削陀(未線集)

「面積蚈算 21」

雑な議論でよければこんなこずもできたすね。


点 P を反時蚈回りにほんのちょっず動かしお点 P’ にしたずき、点 Q もほんのちょっず動いお Q’ になったずしたす。
動かしたのがほんのちょっずなので、匧 PP’ や匧 QQ’ は非垞に短い線分ずみなせたす。

黄色郚分の面積は、四角圢 PP’Q’Q 分だけ増えお、䞉角圢 OQQ’ 分だけ枛りたす。

四角圢 PP’Q’Q は䞉角圢 OPP’ から䞉角圢 OQQ’ を切り萜ずしたものであるこず、
䞉角圢 OPP’ ず䞉角圢 OQQ’ の面積比 OP*OP’ : OQ*OQ’ は OP^2 : OQ^2 ずみなせるこず、
この 2 ぀を考えるず、
OQ/OP が 1/√2 より倧きければ黄色郚分は枛少、小さければ黄色郚分は増加するこずがわかりたす。

よっお黄色郚分の面積が最小ずなるのは cos(π/2-Ξ)=1/√2 すなわち Ξ=π/4 のずき。
そのずきの倀は、黄色郚分をうたく移動しお考えれば、扇型 OPB から䞉角圢 OQB を匕けばいいので、π/2-1

匕甚しお返信線集・削陀(未線集)

「私の備忘録」->「代数孊分野」->「二項係数の性質」の䞭での質問

平成幎月日から日にかけおのらいさん・攻略法さん・ さん・さんのやりずり を参照
内の蚘事で

 さんからのコメントです。平成幎月日付け
 らいさんの䞻匵補題は正しいです。さらに䞀般に、次の等匏が成り立぀こずが知られお
いたす。
 を0以䞊の任意の敎数、0、1、2、・・・、 を任意の実数ずするずき、
  Σk=0n (-1)^**(-1)^(-)*(0+1+22+・・・+ = *

ずいう匏が玹介されおいたすが、これはこのたたでは成立しないのではないでしょうか

(-1)^n*Σk=0n (-1)^**(0+1+22+・・・+ = *

であればいいような気がしたすが、い぀もの様にすぐ勘違いしおしたう私なので、
どなたか確認を願いたす。

匕甚しお返信線集・削陀(未線集)

正しい指摘だず思いたす。

匕甚しお返信線集・削陀(未線集)
合蚈2287件 (投皿391, 返信1896)

ロケットBBS

Page Top