面白い問題おしえて～な 35問目

**１３２人目の素数さん** · 2021/02/27(土) 13:20:25.58

過去ログ(1-16問目)
//www3.tokai.or.jp/meta/gokudo-/omoshi-log/

まとめwiki
//w.atwiki.jp/omoshiro2ch/

過去スレ
1 //cheese.5ch.net/test/read.cgi/math/970737952/
2 //natto.5ch.net/test/read.cgi/math/1004839697/
3 //mimizun.com/log/2ch/math/1026218280/
4 //mimizun.com/log/2ch/math/1044116042/
5 //mimizun.com/log/2ch/math/1049561373/
6 //mimizun.com/log/2ch/math/1057551605/
7 //science2.5ch.net/test/read.cgi/math/1064941085/
8 //science3.5ch.net/test/read.cgi/math/1074751156/
9 //science3.5ch.net/test/read.cgi/math/1093676103/
10 //science4.5ch.net/test/read.cgi/math/1117474512/
11 //science4.5ch.net/test/read.cgi/math/1134352879/
12 //science6.5ch.net/test/read.cgi/math/1157580000/
13 //science6.5ch.net/test/read.cgi/math/1183680000/
14 //science6.5ch.net/test/read.cgi/math/1209732803/
15 //science6.5ch.net/test/read.cgi/math/1231110000/
16 //science6.5ch.net/test/read.cgi/math/1254690000/
17 //kamome.5ch.net/test/read.cgi/math/1284253640/
18 //kamome.5ch.net/test/read.cgi/math/1307923546/
19 //uni.5ch.net/test/read.cgi/math/1320246777/
20 //wc2014.5ch.net/test/read.cgi/math/1356149858/
21 //wc2014.5ch.net/test/read.cgi/math/1432255115/
22 //rio2016.5ch.net/test/read.cgi/math/1464521266/
23 //rio2016.5ch.net/test/read.cgi/math/1497416499/
24 //rio2016.5ch.net/test/read.cgi/math/1502016223/
25 //rio2016.5ch.net/test/read.cgi/math/1502032053/
26 //rio2016.5ch.net/test/read.cgi/math/1518967270/
27 //rio2016.5ch.net/test/read.cgi/math/1532793672/
28 //rio2016.5ch.net/test/read.cgi/math/1540739963/
29 //rio2016.5ch.net/test/read.cgi/math/1548267995/
30 //rio2016.5ch.net/test/read.cgi/math/1572866819/
31 //rio2016.5ch.net/test/read.cgi/math/1580123521/
32 //rio2016.5ch.net/test/read.cgi/math/1586230333/
33 //rio2016.5ch.net/test/read.cgi/math/1598637093/
34 //rio2016.5ch.net/test/read.cgi/math/1608679703/
(前スレ)

**１３２人目の素数さん** · 2021/02/27(土) 16:35:33.59

数列pn,qnが以下で定められている

p0=4,p1=0
p(n+1) = (2n+1)pn+ n^2p(n-1)

q0=2,q1=1
q(n+1) = (2n+1)qn+ n^2q(n-1)

lim pn/qnを求めよ

**１３２人目の素数さん** · 2021/02/27(土) 18:42:51.13

訂正

数列pn,qnが以下で定められている

p0=4,p1=0
p(n+1) = (2n+1)pn+ n^2p(n-1)

q0=1,q1=1 ←ココ!
q(n+1) = (2n+1)qn+ n^2q(n-1)

lim pn/qnを求めよ

**１３２人目の素数さん** · 2021/02/27(土) 22:11:54.13

こんな数列の問題を思い出した

数列a(n)は
a(0)=0,a(1)=1
a(n+2)=a(n)×1/2+a(n+1)

a(n)に出てくる整数は有限個か

**１３２人目の素数さん** · 2021/02/27(土) 23:35:30.43

>>4
ヒントおながいします

**１３２人目の素数さん** · 2021/02/28(日) 00:54:28.22

わかった
bn=(12 an^2-(-2)^(n+1))/2^(n+1)
とおくとbnは漸化式
b0=1,b1=2,b(n+2)=4b(n+1)-bn
を満たす
この時bnが4の倍数となるのはないので十分大きなnでanは整数ではない

**１３２人目の素数さん** · 2021/02/28(日) 02:10:49.45

最初の方の項は

a(0)=0
a(1)=1
a(2)=1
a(3)=3/2=1.5
a(4)=2
a(5)=11/4=2.75
a(6)=15/4=3.75
a(7)=41/8=5.125
a(8)=7
a(9)=153/16=9.5625
a(10)=209/16=13.0625

ここまでの整数は0,1,1,2,7の5つだけど…

**１３２人目の素数さん** · 2021/02/28(日) 10:01:39.05

やり直し
数列bとcを
b0=0, b1=1, bn= 2(b(n-1)+b(n-2))
c0=2, c1=1, cn= 2(c(n-1)+c(n-2))
で定める
an = 2bn/(2^n)
なので問題は bnが2^(n-1)の倍数となるのはいつか？になる
vを2進付値としてcnのv値は
v(c) : 113233545576...
は容易、特にn≧3の時v(cn)<n
同じく漸化式だけで
v(b) : ≧<≧<≧<≧<≧<‥
も容易で特にv(bn)=(n-1)/2 ( if n odd )も容易
よって奇数項で条件を満たすのはn=1のみである
偶数項についてはb(2n) = bn cnと先に述べたことから
b(2n)≧2n-1 only if b(n)≧n-1 for n≧3
ココでn:0～16で条件を満たすのがn=0,1,2,4,8しかないからn≧17に条件を満たす偶数は存在しない

**１３２人目の素数さん** · 2021/02/28(日) 11:58:46.02

>>8
> vを2進付値としてcnのv値は
> v(c) : 113233545576...
> は容易
これは何で？

**１３２人目の素数さん** · 2021/02/28(日) 12:38:42.04

>>8
帰納法

a,a,a+2,a+1
cn=2(c(n-1)+c(n-2))
だから前２つの付値が違う時は小さい方+1
なので次の２つがa+2,a+2まで確定
cn=16c(n-3)+12c(n-4)で
a,a,a+2,a-1,a+2,a+2
の次は３つ前からのa-1+4と4つ前からのa+2+2の小さい方+1でa+4確定
最後のa+3も同様

**１３２人目の素数さん** · 2021/02/28(日) 12:49:10.19

訂正
cn=16c(n-3)+12c(n-4)より
a,a,a+2,a+1,a+2,a+2のa+1+4とa+2+2の小さい方でした

**１３２人目の素数さん** · 2021/02/28(日) 16:13:38.03

cn=14c(n-3)+12c(n-4)では

**１３２人目の素数さん** · 2021/02/28(日) 16:15:32.04

ごめんミス
無視して

**１３２人目の素数さん** · 2021/02/28(日) 17:53:51.96

>>3
p_n / q_n → {(1-π/4)p_0 + (π/4)p_1} / {(1-π/4)q_0 + (π/4)q_1},

特に　q_0 = q_1 = 1 のときは

p_n / q_n → (1-π/4)p_0 + (π/4)p_1 = 4-π = 0.8584073464102…

**１３２人目の素数さん** · 2021/02/28(日) 18:00:26.87

>>14
不正解です
最初の1000桁計算するプログラム

https://ideone.com/Bj68Zu

**１３２人目の素数さん** · 2021/02/28(日) 18:06:57.12

あ、いや
失礼しました
オレが出題ミスしてる
orz

**１３２人目の素数さん** · 2021/02/28(日) 18:10:36.17

p0とp1が逆

**１３２人目の素数さん** · 2021/02/28(日) 18:12:36.09

もう答え書きますね
p0=0,p1=4なら>>3の漸化式でπに収束します
ガウスの超幾何関数というやつでした
出題ミスしといて何をいうかですけど...

**１３２人目の素数さん** · 2021/02/28(日) 18:19:04.58

ちなみに漸化式が線形なので(p0,p1)=(4,0)のときは
(4,0)= (4,4) - (0,4)
より>>14さんの指摘通り4-πに収束します

p 0 = 4
p 1 = 0
p n = (2*n-1) * ( p$ n-1)+ ( n-1) ^2 * ( p $ n-2)

q 0 = 1
q 1 = 1
q n = (2*n-1) * ( q$ n-1)+ ( n-1) ^2 * ( q $ n-2)

main = do
print $ ( p 10) / ( q 10 )
print $ 4-pi
----
0.85840745955346
0.8584073464102069

**１３２人目の素数さん** · 2021/02/28(日) 18:27:54.42

>>3
　p_0 = 4,　q_0 = 1,　r_0 = 4,
　p_1 = 0,　q_1 = 1,　r_1 = 0,
　p_2 = 4,　q_2 = 4,　r_2 = 1,
　p_3 = 20,　q_3 = 24,　r_3 = 0.83333333
　p_4 = 176,　q_4 = 204,　r_4 = 0.86274510
　p_5 = 1904,　q_5 = 2220,　r_5 = 0.85765766
　p_6 = 25344,　q_6 = 29520,　r_6 = 08585365854
　p_7 = 398016,　q_7 = 463680,　r_7 = 0.85838509
　p_8 = 7212096,　q_8 = 8401680,　r_8 = 0.858411175
　p_9 = 148078656,　q_9 = 172504080,　r_9 = 0.85840669
　p_10 = 3397674240,　q_10 = 3958113600,　r_10 = 0.85840746
　・・・
となったが。。。

**１３２人目の素数さん** · 2021/02/28(日) 18:34:06.60

>>20
はい
>>3のままの出題だと4-πに収束します

**１３２人目の素数さん** · 2021/02/28(日) 20:46:01.09

sin_N(x):=sin(sin(…sin(sinx))…)(N回合成)とおく

sin_N(x)=Σa_n(N)x^n/n!と展開したとき

各係数a_n(N)はNの多項式になることを示せ