平成２６年３月１６日

[流れ星]

　　　　　第303回数学的な応募解答

　　　　　　＜解答募集期間：2月16日～3月16日＞

［特殊な約数］

問題１：整数n＝2014とする。nより小さいｎ2　の正の約数であって、nの約数でないような整数は何個あるか。また、具体的にこの数を求めよ。

       例えば、整数18のとき、18より小さい18２＝324の正の約数であって、18の約数でない数は４と12の2個です。

問題２：整数n＝pa qb (pとqは異なる素数)とする。nより小さいｎ2　の正の約数であって、nの約数でないような整数は何個あるか。

問題３：整数n＝pa qbｒc (pとqとｒは異なる素数)とする。nより小さいｎ2　の正の約数であって、nの約数でないような整数は何個あるか。

NO1「uchinyan」  02/16 13時57分　受信 更新3/16

最初から一般的に解いてしまいましょうか。

整数 n = p^a * q^b * r^c * …，p，q，r，… は異なる素数，とすると，

n^2 = p^(2a) * q^(2b) * r^(2c) * …

そこで。n^2 の約数は (2a + 1)(2b + 1)(2c + 1)… 個。

ここで，k を n^2 の約数とすると n^2/k も n^2 の約数で，

1 <= k < n ならば n < n^2/k <= n^2

k = n ならば n^2/k = n

n < k <= n^2 ならば 1 <= n^2/k < n

なので，n^2 の n 以下の約数は ((2a + 1)(2b + 1)(2c + 1)… + 1)/2 個。

一方で，n を含む n の約数は (a + 1)(b + 1)(c + 1)… 個。

そこで，n^2 の約数で n より小さく n の約数でないものは，

((2a + 1)(2b + 1)(2c + 1)… + 1)/2 - (a + 1)(b + 1)(c + 1)… 個

になります。　以下ではこの結果を使います。

問題１：

2014 = 2 * 19 * 53，2014^2 = 2^2 * 19^2 * 53^2，なので，

個数は，((2 + 1)(2 + 1)(2 + 1) + 1)/2 - (1 + 1)(1 + 1)(1 + 1) = 14 - 8  = 6 個。

具体的には，2^x * 19^y * 53^z の形で，x，y，z は 0 ～ 2 で少なくとも一つは 2 ですが，

53^2 = 2809 > 2014 なので z は 2 にはなれません。そこで，

2^2 * 19^0 * 53^0 = 4

2^2 * 19^1 * 53^0 = 76

2^2 * 19^0 * 53^1 = 212

2^0 * 19^2 * 53^0 = 361

2^1 * 19^2 * 53^0 = 722

2^2 * 19^2 * 53^0 = 1444

になります。

問題２：

n = p^a * q^b，n^2 = p^(2a) * q^(2b)，なので，

((2a + 1)(2b + 1) + 1)/2 - (a + 1)(b + 1)

= (2ab + a + b + 1) - (ab + a + b + 1)

= ab 個

になります。

問題３：

n = p^a * q^b * r^c，n^2 = p^(2a) * q^(2b) * r^(2c)，なので，

((2a + 1)(2b + 1)(2c + 1) + 1)/2 - (a + 1)(b + 1)(c + 1)

= (4abc + 2ab + 2bc + 2ca + a + b + c + 1) - (abc + ab + bc + ca + a + b + c + 1)

= 3abc + ab + bc + ca 個

になります。

 

(感想)　これで合っていれば簡単でした。　最初に書いたことに気付くかどうか，かな。

NO2「二度漬け白菜」 02/16 22時17分 受信更新3/16

 


問題1：
n=2014より小さい n^2 の正の約数であって，n の約数でないような整数は
6 個ある．
具体的には，4，76，212，361，722，1444．(答)

 

問題2：
n=(p^a)*(q^b)より小さい n^2 の正の約数であって，n の約数でないような整数は
a*b 個ある．(答)

 

問題3：
n=(p^a)*(q^b)*(r^c)より小さい n^2 の正の約数であって，n の約数でないような整数は
3*a*b*c+a*b+b*c+c*a 個ある．(答)

 

 以下では，mを2以上の任意の正整数として，nの異なる素因子が m 個ある場合を考えます．

 

nの素因数分解を，
n=(p[1]^e[1])*(p[2]^e[2])*…*(p[m]^e[m])とする．
(p[1]，p[2]，…，p[m] は異なる素数で，
e[1]，e[2]，…，e[m]は0以上の整数)

 

集合A,B,C,Dを次のように決める．


A={x|xはn^2の正の約数}
B={x|xはnの正の約数}
C={x|x∈A-B かつ x＜n}
D={x|x∈A-B かつ x＞n}

 

A=B∪C∪Dであり，B∩C=C∩D=D∩B={  }．
また，C≠{  }，D≠{  } ．

 

Cの任意の元 c に対して，(n^2)/c ∈ D．
(∵c∈Aより(n^2)/c∈A．また，(n^2/c)-n=n*(n/c-1)＞0より，(n^2)/c＞n．
(n^2)/cはnより大きいのでBの元ではないことがわかる．)

Cの任意の元 c に対して，Dの元 (n^2)/c を対応させる写像は単射．

 

Dの任意の元 d に対して，(n^2)/d ∈ B∪C．
(∵d∈Aより(n^2)/d∈A．また，(n^2/d)-n=n*(n/d-1)＜0より，(n^2)/d＜n．
よって，(n^2)/d∈B or (n^2)/d∈C)
Dの任意の元 d に対して，B∪Cの元 (n^2)/d を対応させる写像は単射．

 

集合Eを次のように決める．
 E={x|x∈D かつ (n^2)/x ∈ B }


集合Cの元と集合D-Eの元とは，1 対 1 に対応する．

 

|E|の値を調べる．

 

「d∈E」
⇔
「d∈D　かつ，
(n^2)/d=(p[1]^g[1])*(p[2]^g[2])*…*(p[m]^g[m])
かつ，
0≦g[i]≦e[i] (i=1，2，…，m)」
⇔
「d=(p[1]^h[1])*(p[2]^h[2])*…*(p[m]^h[m])
かつ，
e[i]≦h[i]≦2*e[i] (i=1,2,…,m)，
かつ，
(h[1]，h[2]，…，h[m])≠(e[1]，e[2]，…，e[m])」

よって，|E|=Π[i=1～m](e[i]+1)-1．

|A|=|B|+|C|+|D|=|B|+|C|+|D-E|+|E|=|B|+2*|C|+|E|より，
|C|=(1/2)*(|A|-|B|-|E|)
=(1/2)*(Π[i=1～m](2*e[i]+1)-Π[i=1～m](e[i]+1)-(Π[i=1～m](e[i]+1)-1))
=(1/2)*(Π[i=1～m](2*e[i]+1)-2*Π[i=1～m](e[i]+1)+1)．


問題2：
(1/2)*((2*a+1)*(2*b+1)-2*(a+1)*(b+1)+1)
=a*b 個．

 

問題3：
(1/2)*((2*a+1)*(2*b+1)*(2*c+1)-2*(a+1)*(b+1)*(c+1)+1)
=3a*b*c+a*b+b*c+c*a 個．

 

NO3「早起きのおじさん」 02/19 08時27分　受信更新3/16

 

 

●まずｎの素因数がp、qの2種類のときを考えます。（）

の約数は次の表に示されます。

たてに、横に2b+1なので、全部で個あります。

水色に塗った部分はｎの約数です。

この表の中で、ｎに関して点対称の位置にある赤枠で囲った2数に注目します。

この2数の積は、です。

左下の数とｎを比べると 、右上の数とｎを比べると  となりこの比の値は互いに逆数の関係です。

赤枠の2数のうち一方はｎより大きく、他方はｎより小さくなります。

 

 

1

･･･

･･･

･･･

･･･

1

1

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･

･･･


黄色と橙色の部分の数は、ｎより大きくなります。

（ｎに関して対称の位置にある数がｎより小さいからです。つまり、ｎの約数です）

よって、白い部分のｎに関して対称な2数のどちらか一方がｎより小さくなります。

つまり、太枠で囲った白い部分の一つ分なので、の約数であって、ｎの約数でない数はab個あります。

 

計算では、全体から、①水色の部分、②黄色の部分、③橙色の部分を引いて半分にします。

 

なので、の約数であって、18の約数でない数は、1×2＝2個です。

 

 

●次にｎの素因数がp、q、ｒの3種類のときを考えます。（）

の約数の表を作ると、3次元的になります。

ｒの指数が増えたものを上に重ねていくように作ります。

前後に、横に2b+1、たてになので、全部で個あります。

水色で囲った部分はｎの約数です。

この表の中で、ｎに関して点対称の位置にある2数に注目します。

一方が なら、他方は です。（ は整数です）

この2数の積は、です。

これらの数とｎを比べると  と  となりこの比の値は互いに逆数の関係にあります。

　　　　　　　　　　　

水色は2014の約数です。

 

 

問題２：ab個です。

 

問題３： 3abc+ab+bc+ca個です。

 

 

●上の結果から考えると、ｎの素因数が4個になると（）、

全体から、ｎの約数の個数、4次の基本対称式、3次の基本対称式、2次の基本対称式、1次の基本対称式を引いて半分にすれば良いようです。

つまり、

NO4「にいばりZ12」3/16  02時02分 受信 更新 03/16

問題１：整数n＝2014とする。nより小さいｎ2　の正の約数であって、nの約数でないような整数は何個あるか。また、具体的にこの数を求めよ。

 

約数の定義は単位数とその数自体も含みます

2014を素因数分解すると

2014=2×19×53

2014＾2を素因数分解すると

2014＾2=2×2×19×19×53×53

 

2014は3つの重複しない(互いに素な2,19,53)素数で素因数分解できるので

その約数の個数は

素数の次数を0,1の２個とし

2×2×2＝8

(3C0+3C1+3C2+3C3=8)

素因数をp,q,r(1<p<q<r)としたとき具体的には

1,,p,q,r,,pq,qr,pr,, pqrの8個(単位数,その数自体を含む)で            

1,2,19,53,2×19,2×53,19×53,2×19×53

 

2014＾2は3つの素数の２乗で素因数分解できるので

その約数の個数は

素数の次数を0,1,2の3個とし

3×3×3＝27

(3C0+3C1+3C2+3C3)　　　　　　　　・・・nの約数の個数（素因数の２乗が出てこない）（A）

+ (3C1+(3C2-1)×3+3C3×3)　　 ・・・２乗する素因数を1個だけ含む場合の個数（B）

+( (3C2-2)×3+3C3×3)　　　　・・・２乗する素因数を2個以上含む場合の個数（C）     

素因数をpqrとしたとき上記を具体的に示すと

1,,p,q,r,,pq,qr,pr,, pqrの8個

p2,q2,r2,,p2q,p2r, q2p,q2r, r2p, r2q,,p2qr, q2pr, r2pqの12個（B）

p2q2,q2r2,p2r2,, p2q2 r, p2q r2, pq2 r2, p2q2 r2の7個（C）

の27個(単位数,その数自体を含む)で                                                     

1,2,19,53,2×19,2×53,19×53,2×19×53

2×2,19×19,53×53,,2×2×19,2×2×53,19×19×2, 19×19×53,53×53×2,53×53×19,, 2×2×19×53,2×19×19×53, 2×19×53×53

2×2×19×19,19×19×53×53, 2×2×53×53,, 2×2×19×19×53, 2×2×19×53×53, 2×19×19×53×53, 2×2×19×19×53×53

 

 

n2の約数でnの約数でない数はp,q,rの2乗を因数に持つのでその総数は27-8＝19（B、C）です

その内、pqr（2014）より小さい数は

2×2, 19×19, 2×2×19,2×2×53,19×19×2,2×2×19×19  

4,361,76,212,722,1444の6個となります・・・・回答     

 

----------------------------------------------------------------------

 

上記で、pqrとB、Cの大小関係を考えます(<>は≠と同じ)

 

B

pq r >p2

pq r > q 2

pq r <> r 2

 

pq r >p2r>p2q             

q2r> pq r >pq2            

pqr <pr2<qr2

pqr<p2q r<pq2 r<pqr2

 

C

pqr<> p2q2

pqr<p2 r2<q2 r2                                                                                                                                 

pqr< p2q2 r<p2q r2<pq2 r2<p2q2 r2

 

よってB、Cの内pqrより小さいのは

p2,q 2, p2r, p2q, pq2

で、大小を特定できないのが

r 2, p2q2

ここで

 

pq <r ・・・①

とすると

①の両辺にrをかけて　pq r < r 2

①の両辺にpqをかけて　p2q2 < pqr

B、C　のうちpqrより小さいのは

p2, q 2, p2r, p2q, pq2, p2q2

の６個となります。

 

pq >r ・・・②

とすると

②の両辺にrをかけて　pq r> r 2

②の両辺にpqをかけて　p2q2 > pqr

B、C　のうちpqrより小さいのは

p2, q 2, p2r, p2q, pq2, r 2                        

のやはり６個となります。

 

つまり、pqとrを比較しpqが大きいときにはr 2が入りその逆の時にはp2q2が入ります。

 

------------------------------------------------

 

問題1を見てすぐに問題3の特殊な形と思い

例示するうちにｒ＾2が入る場合と入らない場合があり深く考えずに

約数の数（pqrより小さな約数の個数）は特定でいないと思い込んでしまいました。

その後、場合分けをしてみるとどちらにしても約数の個数が変わらないことに気づき

あわてましたが時間切れとなってしまいました・・・・。

--------------------

全く回答にはなっていませんが問題２と問題３の

ｎ2　の正の約数であって、nの約数でないような整数の個数は

 

問題２

(2a+1)(2b+1)-((a+1)(b+1)=4ab-ab=3ab

問題3

(2a+1)(2b+1)(2c+1)-(a+1)(b+1)(c+1)=7abc+3(ab+bc+ac)+(a+b+c)

 

 

NO5「ＳＰＣ」3/26  15時41分 受信 更新 04/01

　パソコン部部員です。募集期間の過ぎた第３０３回問題の１番だけですが、パソコンのゲーム作成プログラムＨＳＰで解きました。

（プログラム）
n=2014
k=0
repeat n-1,1
     if ((n*n)\cnt=0)&(n\cnt>0) : k+ : mes str(k)+":"+str(cnt)
loop

（解答）
４

７６

２１２

３６１

７２２

１４４４

 

皆さん、問題や質問に答えてください。一部でも構いませんから、解答とペンネームを添えて、メールで送ってください。待っています。