黄昏より暗きもの、血の流れより赤きもの

読者です 読者をやめる 読者になる 読者になる

黄昏より暗きもの、血の流れより赤きもの

自分の好きな事を好きなように書いて行きます。

【自作問題】全ての素数が仲間外れとなる不定方程式(類:Project Euler Problem 12)

C 整数

記事のネタ切れ、次の記事の準備の為に以下の例題を用意した。手計算でもプログラムでもやりやすい方法で解いて欲しい。尚類題として「約数の個数が初めて500を超える三角形数は?:Project Euler Problem 12 を解き、約数の個数をグラフ化してみた」もあるので、興味があったら是非参考にしてほしい。

問題

(1):a,b自然数である。このとき全ての正の素数pに対し、不定方程式
ab+a+b+1=p自然数(a,b)を持たない事を示せ。
(2):a,b,c自然数である。c=1,2,3...nと変化させていくとき、c=kのときの不定方程式 ab+a+b+1 = k の自然数(a,b)の個数をa_kとし、S(k) = \sum_{k=1}^n a_kとおく。このときS(2016)を求めよ。

(1)の解説

(1):ab+a+b+1 = p <=> (a+1)(b+1) = p a > 0 かつ b > 0 より a+1 > 0 かつ b+1 > 0 これより a+1 = p かつ b+1 = 1 または a+1 = 1 かつ b+1 = p の場合に限られる。この事から解は(a,b)=(p-1,0),(0,p-1)の場合に限られる。しかし上記はa,bが自然数である事に反する。この事から全ての正の素数pに対して、ab+a+b+1 = p は自然数解(a,b)を持たない。

(2)の解説

(a+1)(b+1) =k を満たす不定方程式の解の個数について考える。k=1のときは(1)より、(a,b)=(0,0)となるので自然数解が存在しない。

この事からk>=2として考える。c=kのときにおけるkの約数の個数をT_kする。このとき自然数解の個数a_kは、(a,b)=(k-1,0),(0,k-1)となる2つの場合を除き a_k = T_k - 2と表せる。以下計算をC言語に行わせて、S(2016)=11641(個) (答)

(2)のプログラム

#define N 2016
#include<stdio.h>
/*
約数の個数
単純に1~kまでの数字を総当たりし、
余りの出ないものをカウント
*/
int division(int k)
{
	int i=1;
	int a_k = 0;
	for(i=1;i<(k+1);i++)
	{
		if(k%i == 0 ) a_k++;
	}
//約数の個数a_kを出力
return a_k; 
}

/*
k>=2の場合において、実際に
不定方程式の個数を計算
*/

int main()
{
	int j = 2;
	int S_k = 0;
	for(j=2;j<(N+1);j++)
	{
		S_k += (division(j) -2) ;//a_k = T_k - 2 (k >1) を足し合わせて
	}
	printf("%d\n",S_k);
	return 0;
}