「オイラープロジェクト51～60」の編集履歴（バックアップ）一覧はこちら

オイラープロジェクト51～60 - (2012/09/01 (土) 07:10:58) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

*問い50
連続した素数の和として表される１００万以下の素数のうち和の長さが最長になる数を求めよという問題。
素数のみという条件が意外と手ごわい問題。
この条件がなければ簡単な尺取り虫アルゴリズムで片がつくんだけどな、、、
とりあえず力づくの全探索に近い手法で解いたけどかなり工夫の余地がありそうな問題。


 #include<stdio.h>
 #include<string.h>
 #include<vector>
 
 const int up=1000001;
 bool so[up];
 int memo[up];
 std::vector<__int64> sosuu;
 void setSo(){
	int i2;
	__int64 add=2;
	memset(so,true,sizeof(so));
	sosuu.push_back(0);
	sosuu.push_back(2);
	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
		add+=i;
		sosuu.push_back(add);
		i2=i*2;
		for(int j=i*3;j<up;j+=i2){
			so[j]=false;
		}
	}
 }
 int main(){
	setSo();
	memset(memo,0,sizeof(memo));
	int ans=0,len=0;
	__int64 t;
	for(int i=0;i<sosuu.size();i++){
		for(int j=0;j<i;j++){
			if(i-j<=len)break;
			t=sosuu[i]-sosuu[j];
			if(t>=up||(t>2&&t%2==0))continue;
			if(so[(int)t]==true){
				len=i-j;
				ans=t;
			}
		}
	}
	printf("%d %d",ans,len);
 }


*問い52
125874を2倍すると251748となる. これは元の数125874と同じ数を含む.
2x, 3x, 4x, 5x, 6xがxと同じ数を含むような最小の正整数xを求めよ.

数字一つの確認コストが高くないので一つずつ全探索してみる。
数字が大きくなったらもう一工夫が必要。
例えば先頭桁は1意外認められないとか。


 #include<stdio.h>
 bool check(int p1,int p2){
	int count[10]={0};
	while(p1!=0){
		count[p1%10]++;
		p1/=10;
	}
	while(p2!=0){
		count[p2%10]--;
		p2/=10;
	}
	bool ok=true;
	for(int i=0;i<10;i++)ok=(ok&&(count[i]==0));
	return ok;
 }
 int main(){
	for(int i=1;i<1000000;i++){
		//とりあえず100万まで試しにさがしてみる。
		bool ok=true;
		for(int j=2;j<7;j++){
			if(check(i,i*j)==false){
				ok=false;
				break;
			}
		}
		if(ok==true){
			for(int j=1;j<7;j++){
				printf("%d ",j*i);
			}
			printf("\n");
		}
	}
 }



*問い53
nCr (n=1...100)の時100万を超えるnCrは何個あるか？

１００万を超えたらどんな値だろうがその位置の影響下にある下の段の数字は全部１００万を超えます。
これを利用して１００万以上を特別扱いして値あふれを防ぎます。
どの問題ももっと賢い方法が幾らでもありそうなのがオイラープロジェクトのサイトの特徴のようです。



 #include<string.h>
 int main(){
 	int memo[102][102];
 	memset(memo,0,sizeof(memo));
 	int mymax=1000000,ans=0;
 	for(int i=1;i<101;i++){
 		memo[i-1][0]=1;
 		for(int j=0;j<=i;j++){
 			memo[i][j]=memo[i-1][j];
 			if(j>0)memo[i][j]+=memo[i-1][j-1];
 			if(memo[i][j]>mymax){
 				memo[i][j]=mymax+1;
 				ans++;
 			}
 			//printf("%d ",memo[i][j]);
 		}
 		//printf("\n");
 	}
 	printf("%d",ans);
 }






*問い55
7とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.
全ての数が素早く回文数になるわけではない. 349を考えよう,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
349は, 3回の操作を経て回文数になる.
回文数にたどり着かない数をLychrel数とする。
10000以下の数は５０回未満の操作で回文数になるか、５０回以上で Lychrel数と仮に分類しておくかである。
10000以下のLychrel数の数を数えよ。
4994は回文数だが一回目の操作以降回文数にたどり着かないので回文数かつLychrel数と分類される。



とりあえず愚直に実装してみたけど少し速度が遅い。
うーんもう少し賢い実装方法がありそう。
まあちょっとだけ巨大な数を扱ったが流石Ｌｉｓｐだ何ともないぜ。

 (defun rev (n re)
   (if (= n 0)
       re
     (rev (floor (/ n 10)) (+ (mod n 10) (* re 10)))))
 rev
 (defun calc (n deep)
   (let ((next (+ n (rev n 0))))
     (if (< 49 deep) 1
       (if (= next (rev next 0)) 0
 	(calc next (+ deep 1))))))
 calc
 (let ((sum 0))
   (dotimes (i 10000 sum)
     (setq sum (+ sum (calc (+ i 1) 1)))))




*問い56
Googol (10100)は非常に大きな数である: 1の後に0が100個続く. 100100は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である.
a, b < 100について自然数a^bを考える. 桁の和の最大を答えよ.
Ｌｉｓｐの整数処理能力にものを言わせてゴリ押しで全探索。
もう少し賢い方法がありそうだけど思いつかないな。


 (defun sum (n wa)
   (if (= n 0) wa
     (sum (floor (/ n 10)) (+ wa (mod n 10)))))
 sum
  (let ((max 0))
   (dotimes (a 100 max)
     (dotimes (b 100 max)
       (let ((c (sum (expt (+ a 1) (+ 1 b)) 0)))
 	(if (< max c)
 	    (setq max c)
 	  0)))))

*問い50
連続した素数の和として表される１００万以下の素数のうち和の長さが最長になる数を求めよという問題。
素数のみという条件が意外と手ごわい問題。
この条件がなければ簡単な尺取り虫アルゴリズムで片がつくんだけどな、、、
とりあえず力づくの全探索に近い手法で解いたけどかなり工夫の余地がありそうな問題。


 #include<stdio.h>
 #include<string.h>
 #include<vector>
 
 const int up=1000001;
 bool so[up];
 int memo[up];
 std::vector<__int64> sosuu;
 void setSo(){
	int i2;
	__int64 add=2;
	memset(so,true,sizeof(so));
	sosuu.push_back(0);
	sosuu.push_back(2);
	for(int i=3;i<=up;i+=2){
		if(so[i]==false)continue;
		add+=i;
		sosuu.push_back(add);
		i2=i*2;
		for(int j=i*3;j<up;j+=i2){
			so[j]=false;
		}
	}
 }
 int main(){
	setSo();
	memset(memo,0,sizeof(memo));
	int ans=0,len=0;
	__int64 t;
	for(int i=0;i<sosuu.size();i++){
		for(int j=0;j<i;j++){
			if(i-j<=len)break;
			t=sosuu[i]-sosuu[j];
			if(t>=up||(t>2&&t%2==0))continue;
			if(so[(int)t]==true){
				len=i-j;
				ans=t;
			}
		}
	}
	printf("%d %d",ans,len);
 }


*問い52
125874を2倍すると251748となる. これは元の数125874と同じ数を含む.
2x, 3x, 4x, 5x, 6xがxと同じ数を含むような最小の正整数xを求めよ.

数字一つの確認コストが高くないので一つずつ全探索してみる。
数字が大きくなったらもう一工夫が必要。
例えば先頭桁は1意外認められないとか。


 #include<stdio.h>
 bool check(int p1,int p2){
	int count[10]={0};
	while(p1!=0){
		count[p1%10]++;
		p1/=10;
	}
	while(p2!=0){
		count[p2%10]--;
		p2/=10;
	}
	bool ok=true;
	for(int i=0;i<10;i++)ok=(ok&&(count[i]==0));
	return ok;
 }
 int main(){
	for(int i=1;i<1000000;i++){
		//とりあえず100万まで試しにさがしてみる。
		bool ok=true;
		for(int j=2;j<7;j++){
			if(check(i,i*j)==false){
				ok=false;
				break;
			}
		}
		if(ok==true){
			for(int j=1;j<7;j++){
				printf("%d ",j*i);
			}
			printf("\n");
		}
	}
 }



*問い53
nCr (n=1...100)の時100万を超えるnCrは何個あるか？

１００万を超えたらどんな値だろうがその位置の影響下にある下の段の数字は全部１００万を超えます。
これを利用して１００万以上を特別扱いして値あふれを防ぎます。
どの問題ももっと賢い方法が幾らでもありそうなのがオイラープロジェクトのサイトの特徴のようです。



 #include<string.h>
 int main(){
 	int memo[102][102];
 	memset(memo,0,sizeof(memo));
 	int mymax=1000000,ans=0;
 	for(int i=1;i<101;i++){
 		memo[i-1][0]=1;
 		for(int j=0;j<=i;j++){
 			memo[i][j]=memo[i-1][j];
 			if(j>0)memo[i][j]+=memo[i-1][j-1];
 			if(memo[i][j]>mymax){
 				memo[i][j]=mymax+1;
 				ans++;
 			}
 			//printf("%d ",memo[i][j]);
 		}
 		//printf("\n");
 	}
 	printf("%d",ans);
 }






*問い55
7とその反転を足し合わせると, 47 + 74 = 121となり, 回文数になる.
全ての数が素早く回文数になるわけではない. 349を考えよう,
349 + 943 = 1292,
1292 + 2921 = 4213
4213 + 3124 = 7337
349は, 3回の操作を経て回文数になる.
回文数にたどり着かない数をLychrel数とする。
10000以下の数は５０回未満の操作で回文数になるか、５０回以上で Lychrel数と仮に分類しておくかである。
10000以下のLychrel数の数を数えよ。
4994は回文数だが一回目の操作以降回文数にたどり着かないので回文数かつLychrel数と分類される。



とりあえず愚直に実装してみたけど少し速度が遅い。
うーんもう少し賢い実装方法がありそう。
まあちょっとだけ巨大な数を扱ったが流石Ｌｉｓｐだ何ともないぜ。

 (defun rev (n re)
   (if (= n 0)
       re
     (rev (floor (/ n 10)) (+ (mod n 10) (* re 10)))))
 rev
 (defun calc (n deep)
   (let ((next (+ n (rev n 0))))
     (if (< 49 deep) 1
       (if (= next (rev next 0)) 0
 	(calc next (+ deep 1))))))
 calc
 (let ((sum 0))
   (dotimes (i 10000 sum)
     (setq sum (+ sum (calc (+ i 1) 1)))))




*問い56
Googol (10100)は非常に大きな数である: 1の後に0が100個続く. 100100は想像を絶する. 1の後に0が200回続く. その大きさにも関わらず, 両者とも桁の和は1である.
a, b < 100について自然数a^bを考える. 桁の和の最大を答えよ.
Ｌｉｓｐの整数処理能力にものを言わせてゴリ押しで全探索。
もう少し賢い方法がありそうだけど思いつかないな。


 (defun sum (n wa)
   (if (= n 0) wa
     (sum (floor (/ n 10)) (+ wa (mod n 10)))))
 sum
  (let ((max 0))
   (dotimes (a 100 max)
     (dotimes (b 100 max)
       (let ((c (sum (expt (+ a 1) (+ 1 b)) 0)))
 	(if (< max c)
 	    (setq max c)
 	  0)))))


*問い57
2の平方根は無限に続く連分数で表すことができる.
√ 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
最初の4回の繰り返しを展開すると以下が得られる.
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...
次の3つの項は99/70, 239/169, 577/408である. 第8項は1393/985である. これは分子の桁数が分母の桁数を超える最初の例である.
最初の1000項を考えたとき, 分子の桁数が分母の桁数を超える項はいくつか?
Ｌｉｓｐの分数処理能力にものを言わせて愚直に計算します。
おそらく数式を使うのが賢いのだとは思いますが。


 (defun keta (n deep)
   (if (= n 0) deep
     (keta (floor (/ n 10)) (+ 1 deep))))
 (defun calc (deep k)
   (if (<= k deep) (+ 2 (/ 1 2))
     (+ 2 (/ 1 (calc (+ 1 deep) k)))))
 (let ((n 3/2) (a 0) (b 0) (ans 0))
   (dotimes (i 999 ans)
      (setq n (+ 1 (/ 1 (+ 1 n))))
     (setq a (keta (numerator n) 0) b (keta (denominator n) 0))
     (if (< b a)
 	(setq ans (+ ans 1))
       )))