「プロジェクトオイラー問い41~50」の編集履歴(バックアップ)一覧はこちら
プロジェクトオイラー問い41~50 - (2012/12/21 (金) 15:53:25) の1つ前との変更点
追加された行は緑色になります。
削除された行は赤色になります。
*問い41
n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁(この問題の定義では9桁以下)Pandigitalな素数の中で最大の数を答えよ.
解法
9桁や8桁のパンデジタル数の各桁の和は45と36で9の倍数となっておりこれは8桁と9ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。
よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。
末尾の数字が2の倍数であってはいけないや大きな数字から試すなど各種ルールを適用すればもっと計算量が下がるかもしれません。
#include<stdio.h>
#include<stdlib.h>
bool spents[10]={true,false,false,false,false,false,false,false,false,false};
int ans=0;
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool isPandigital(int n,int keta){
for(int i=0;i<keta;i++){
if(n%10>keta)return false;
n/=10;
}
return true;
}
void saiki(int n,int keta){
if(isPrime(n)&&isPandigital(n,keta)==true&&ans<n){
ans=n;
}
if(7<=keta)return;
for(int i=1;i<=7;i++){
if(spents[i]==false){
spents[i]=true;
saiki(n*10+i,keta+1);
spents[i]=false;
}
}
}
int main(){
saiki(0,0);
printf("%d",ans);
}
*問い42
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042
ファイルから単語を読み取り、それを数字に置き換えた時三角数になるかどうか調べる問題。
解法
単語を一つずつ読み込んで数字を計算するだけです。
実はCの処理系ではアルファベットが連続していることは保証されてないのでtoHash関数は実はインチキ関数なのですが、ま手元の環境では連続しているし連続してないことが超レアケースなので気にしません。
スクリプトなら物凄く短く記述できる可能性があります。
一気にデータを読んでスプリットして、それを一気に処理して結果を返す関数に入れて条件を満たすものをカウントさせれば一行で記述が済むかも。
#include<stdio.h>
#include<stdlib.h>
#include<set>
int toHash(char *text){
int re=0;
for(int i=0;text[i]!='\0';i++){
re+=text[i]-'A'+1;
}
return re;
}
int main(){
int ans=0,sum=0;
std::set<int> memo;
for(int i=1;i<50;i++){
sum+=i;
memo.insert(sum);
}
FILE *fp;
if ((fp = fopen("euler42Data.txt", "r")) == NULL) {
printf("file open error!!\n");
exit(EXIT_FAILURE); /* (3)エラーの場合は通常、異常終了する */
}
char text[100],c;
while(1){
fscanf(fp,"\"%[^\"]\"",text);
if(fscanf(fp,"%c",&c)==EOF)break;
if(memo.find(toHash(text))!=memo.end())ans++;
}
fclose(fp);
printf("ans=%d",ans);
}
*問い43
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2043
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分列が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406は2で割り切れる
d3d4d5=063は3で割り切れる
d4d5d6=635は5で割り切れる
d5d6d7=357は7で割り切れる
d6d7d8=572は11で割り切れる
d7d8d9=728は13で割り切れる
d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.
解法
再帰関数で全部試すだけです。
先頭桁0が許されるかは不明ですが先頭桁0でこの条件を満たす数はないようです。
#include<stdio.h>
#include<iostream>
bool spents[10]={false,false,false,false,false,false,false,false,false,false};
int mask=1000;
int mod[]={2,3,5,7,11,13,17};
__int64 ans=0;
void saiki(int n,int keta,__int64 num){
if(keta>=4){
if(n%mod[keta-4]!=0)return ;
}
if(keta==10){
ans+=num;
}else{
for(int i=0;i<=9;i++){
if(spents[i]==false){
spents[i]=true;
saiki((n*10+i)%mask,keta+1,num*10+i);
spents[i]=false;
}
}
}
}
int main(){
saiki(0,0,0);
std::cout<<"ans="<<ans;
}
*問い44
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044
二つの五角数の和と差がともに5角数になるとき差の最小値を求めよという問題。
解法
とりあえず小さい方から全組み合わせを検討するコードを書いてみました。
もちろんこんなコードで速度が出るはずもなくC++で4秒もかかっています。
どうしたら速度が出るか、ちょっと考えあぐねています。
変数の数が3つになるとけっこう悩むものです。
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<time.h>
bool is5(__int64 m){
__int64 m1=sqrt(1+24*m);
return m1*m1==1+24*m && (1+m1)%6==0;
}
int main(){
__int64 ans=0,n1,n2;
double start=clock();
for(__int64 a=2;;a++){
if(ans!=0&&6*a-4>ans)break;
n1=(a*(3*a-1))/2;
for(__int64 b=a-1;b>0;b--){
n2=(b*(3*b-1))/2;
if(ans!=0&&n1-n2>=ans)break;
if(is5(n1+n2)&&is5(n1-n2)){
ans=n1-n2;
std::cout<<"("<<n1<<" "<<a<<" "<<n2<<" "<<b<<")";
}
}
}
std::cout<<"ans="<<ans<<" time="<<clock()-start;
}
*問い45
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045
三角数, 五角数, 六角数は以下のように生成される.
三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
解法
特に賢い解法を思いつかなかったので、三角数、5角数、6角数を求め、ループの中で3つの数のうち一番小さい数になったものだけをインクリメントしていきます。
そうすると答えがあればきちんとそろうわけです。
#include<stdio.h>
#include<iostream>
int main(){
__int64 t=285+1,p=165,h=143,t1,p1,h1;
while(1){
t1=(t*(t+1))/2;
p1=(p*(3*p-1))/2;
h1=(h*(2*h-1));
if(t1==p1&&t1==h1)break;
if(t1<=p1&&t1<=h1)t++;
if(p1<=t1&&p1<=h1)p++;
if(h1<=t1&&h1<=p1)h++;
}
std::cout<<t1;
}
*問い46
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?
解法
小さい数から試します。
2乗の方が検討する数が少なくなるので2乗*2を引いて、残りが素数かどうか検討すれば十分です。
数式で解くのが一番賢いでしょうが、それをする能力は私にはないのでプログラムで楽をします。
#include<stdio.h>
#include<time.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
double start=clock();
for(int a=3;;a+=2){
if(isPrime(a)==true)continue;
bool ok=false;
for(int b=1;b*b*2+2<=a;b++){
if(isPrime(a-b*b*2)==true){
ok=true;
break;
}
}
if(ok==false){
printf("ans=%d",a);
break;
}
}
printf("time %lf",clock()-start);
}
*問い47
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:
14 = 2 × 7
15 = 3 × 5
それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:
644 = 2^2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?
解法
異なる4数がそんなに大きくない数だと想定し100万以下で探索してみました。
異なる4数のうち3数が最小の2,3、5だとすると30で残りの一つは4万当たりまでの素数と想定すれば100万までの4種の異なる素因数からなる数を網羅できます。
最初にこれを再帰関数で求めて後は4つ連続する部分を線形的に探すだけです。
#include<stdio.h>
#include<vector>
#include<time.h>
#include<algorithm>
const int up=40000;
std::vector<int> sosuu;
bool so[up+1];
const int limit=1000*1000;
bool is4[limit+1];
void setSo(){
int i2;//素数を求める処理
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
void saiki(__int64 num,int count,int p){
if(num>limit)return;
if(count==4)is4[(int)num]=true;//4種の異なる素因数の組の積を求めてセットする関数
for(int i=p;i<sosuu.size()&&sosuu[i]*num<limit;i++){
saiki(num*sosuu[i],count==0?1:count+(p!=i),i);
if(count==4)break;
}
}
int main(){
double start=clock();
setSo();
memset(is4,false,sizeof(is4));
saiki(1,0,0);
int count=0;
for(int i=2;i<limit;i++){
if(is4[i]==true){
count++;
if(count==4){
printf("ans=%d time=%lf",i-3,clock()-start);
break;
}
}else{
count=0;
}
}
}
*問い48
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2048
次の式は, 11 + 22 + 33 + ... + 1010 = 10405071317 である.
では, 1^1 + 2^2 + 3^3 + ... + 1000^1000 の最後の10桁を求めよ.
解法
計算回数50万回なので定義通り計算するだけでも十分間に合います。
大きい数を扱える整数型があれば計算量を減らせますが残念なことにC++標準の型では19桁程度までしか扱えません。
10ケタ*10ケタが桁あふれするためにC++ではライブラリか特殊な処理が必要となります。
めんどくさいのでそのまま計算しました。
#include<stdio.h>
#include<iostream>
int main(){
__int64 mod=1,sum=0,num;
for(int i=0;i<10;i++)mod*=10;
for(int i=1;i<=1000;i++){
num=i;
for(int j=1;j<i;j++){
num=(num*i)%mod;
}
sum=(sum+num)%mod;
}
std::cout<<sum;
}
*問い41
n桁Pandigitalであるとは, 1からnまでの数を各桁に1つずつ持つこととする.
#下のリンク先にあるような数学的定義とは異なる
例えば2143は4桁Pandigital数であり, かつ素数である. n桁(この問題の定義では9桁以下)Pandigitalな素数の中で最大の数を答えよ.
解法
9桁や8桁のパンデジタル数の各桁の和は45と36で9の倍数となっておりこれは8桁と9ケタのパンデジタル数は全て素数でないということを示しています、組み合わせ数を考えると驚く話です。
よって7桁までのパンデジタル数を全て全探索して検討すれば良いと分かります。
末尾の数字が2の倍数であってはいけないや大きな数字から試すなど各種ルールを適用すればもっと計算量が下がるかもしれません。
#include<stdio.h>
#include<stdlib.h>
bool spents[10]={true,false,false,false,false,false,false,false,false,false};
int ans=0;
bool isPrime(int n){
if(n<2)return false;
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
bool isPandigital(int n,int keta){
for(int i=0;i<keta;i++){
if(n%10>keta)return false;
n/=10;
}
return true;
}
void saiki(int n,int keta){
if(isPrime(n)&&isPandigital(n,keta)==true&&ans<n){
ans=n;
}
if(7<=keta)return;
for(int i=1;i<=7;i++){
if(spents[i]==false){
spents[i]=true;
saiki(n*10+i,keta+1);
spents[i]=false;
}
}
}
int main(){
saiki(0,0);
printf("%d",ans);
}
*問い42
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2042
ファイルから単語を読み取り、それを数字に置き換えた時三角数になるかどうか調べる問題。
解法
単語を一つずつ読み込んで数字を計算するだけです。
実はCの処理系ではアルファベットが連続していることは保証されてないのでtoHash関数は実はインチキ関数なのですが、ま手元の環境では連続しているし連続してないことが超レアケースなので気にしません。
スクリプトなら物凄く短く記述できる可能性があります。
一気にデータを読んでスプリットして、それを一気に処理して結果を返す関数に入れて条件を満たすものをカウントさせれば一行で記述が済むかも。
#include<stdio.h>
#include<stdlib.h>
#include<set>
int toHash(char *text){
int re=0;
for(int i=0;text[i]!='\0';i++){
re+=text[i]-'A'+1;
}
return re;
}
int main(){
int ans=0,sum=0;
std::set<int> memo;
for(int i=1;i<50;i++){
sum+=i;
memo.insert(sum);
}
FILE *fp;
if ((fp = fopen("euler42Data.txt", "r")) == NULL) {
printf("file open error!!\n");
exit(EXIT_FAILURE); /* (3)エラーの場合は通常、異常終了する */
}
char text[100],c;
while(1){
fscanf(fp,"\"%[^\"]\"",text);
if(fscanf(fp,"%c",&c)==EOF)break;
if(memo.find(toHash(text))!=memo.end())ans++;
}
fclose(fp);
printf("ans=%d",ans);
}
*問い43
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2043
数1406357289は0から9のPandigital数である (0から9が1度ずつ現れるので). この数は部分列が面白い性質を持っている.
d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.
d2d3d4=406は2で割り切れる
d3d4d5=063は3で割り切れる
d4d5d6=635は5で割り切れる
d5d6d7=357は7で割り切れる
d6d7d8=572は11で割り切れる
d7d8d9=728は13で割り切れる
d8d9d10=289は17で割り切れる
このような性質をもつ0から9のPandigital数の総和を求めよ.
解法
再帰関数で全部試すだけです。
先頭桁0が許されるかは不明ですが先頭桁0でこの条件を満たす数はないようです。
#include<stdio.h>
#include<iostream>
bool spents[10]={false,false,false,false,false,false,false,false,false,false};
int mask=1000;
int mod[]={2,3,5,7,11,13,17};
__int64 ans=0;
void saiki(int n,int keta,__int64 num){
if(keta>=4){
if(n%mod[keta-4]!=0)return ;
}
if(keta==10){
ans+=num;
}else{
for(int i=0;i<=9;i++){
if(spents[i]==false){
spents[i]=true;
saiki((n*10+i)%mask,keta+1,num*10+i);
spents[i]=false;
}
}
}
}
int main(){
saiki(0,0,0);
std::cout<<"ans="<<ans;
}
*問い44
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2044
二つの五角数の和と差がともに5角数になるとき差の最小値を求めよという問題。
解法
とりあえず小さい方から全組み合わせを検討するコードを書いてみました。
もちろんこんなコードで速度が出るはずもなくC++で4秒もかかっています。
どうしたら速度が出るか、ちょっと考えあぐねています。
変数の数が3つになるとけっこう悩むものです。
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<time.h>
bool is5(__int64 m){
__int64 m1=sqrt(1+24*m);
return m1*m1==1+24*m && (1+m1)%6==0;
}
int main(){
__int64 ans=0,n1,n2;
double start=clock();
for(__int64 a=2;;a++){
if(ans!=0&&6*a-4>ans)break;
n1=(a*(3*a-1))/2;
for(__int64 b=a-1;b>0;b--){
n2=(b*(3*b-1))/2;
if(ans!=0&&n1-n2>=ans)break;
if(is5(n1+n2)&&is5(n1-n2)){
ans=n1-n2;
std::cout<<"("<<n1<<" "<<a<<" "<<n2<<" "<<b<<")";
}
}
}
std::cout<<"ans="<<ans<<" time="<<clock()-start;
}
*問い45
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2045
三角数, 五角数, 六角数は以下のように生成される.
三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ...
T285 = P165 = H143 = 40755であることが分かる.
次の三角数かつ五角数かつ六角数な数を求めよ.
解法
特に賢い解法を思いつかなかったので、三角数、5角数、6角数を求め、ループの中で3つの数のうち一番小さい数になったものだけをインクリメントしていきます。
そうすると答えがあればきちんとそろうわけです。
#include<stdio.h>
#include<iostream>
int main(){
__int64 t=285+1,p=165,h=143,t1,p1,h1;
while(1){
t1=(t*(t+1))/2;
p1=(p*(3*p-1))/2;
h1=(h*(2*h-1));
if(t1==p1&&t1==h1)break;
if(t1<=p1&&t1<=h1)t++;
if(p1<=t1&&p1<=h1)p++;
if(h1<=t1&&h1<=p1)h++;
}
std::cout<<t1;
}
*問い46
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2046
Christian Goldbachは全ての奇合成数は平方数の2倍と素数の和で表せると予想した.
9 = 7 + 2×1^2
15 = 7 + 2×2^2
21 = 3 + 2×3^2
25 = 7 + 2×3^2
27 = 19 + 2×2^2
33 = 31 + 2×1^2
後に, この予想は誤りであることが分かった.
平方数の2倍と素数の和で表せない最小の奇合成数はいくつか?
解法
小さい数から試します。
2乗の方が検討する数が少なくなるので2乗*2を引いて、残りが素数かどうか検討すれば十分です。
数式で解くのが一番賢いでしょうが、それをする能力は私にはないのでプログラムで楽をします。
#include<stdio.h>
#include<time.h>
bool isPrime(int n){
for(int i=2;i*i<=n;i+=(i&1)+1){
if(n%i==0)return false;
}
return true;
}
int main(){
double start=clock();
for(int a=3;;a+=2){
if(isPrime(a)==true)continue;
bool ok=false;
for(int b=1;b*b*2+2<=a;b++){
if(isPrime(a-b*b*2)==true){
ok=true;
break;
}
}
if(ok==false){
printf("ans=%d",a);
break;
}
}
printf("time %lf",clock()-start);
}
*問い47
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2047
それぞれ2つの異なる素因数を持つ連続する2つの数が最初に現れるのは:
14 = 2 × 7
15 = 3 × 5
それぞれ3つの異なる素因数を持つ連続する3つの数が最初に現れるのは:
644 = 2^2 × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19
最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数を求めよ. その最初の数はいくつか?
解法
異なる4数がそんなに大きくない数だと想定し100万以下で探索してみました。
異なる4数のうち3数が最小の2,3、5だとすると30で残りの一つは4万当たりまでの素数と想定すれば100万までの4種の異なる素因数からなる数を網羅できます。
最初にこれを再帰関数で求めて後は4つ連続する部分を線形的に探すだけです。
#include<stdio.h>
#include<vector>
#include<time.h>
#include<algorithm>
const int up=40000;
std::vector<int> sosuu;
bool so[up+1];
const int limit=1000*1000;
bool is4[limit+1];
void setSo(){
int i2;//素数を求める処理
memset(so,true,sizeof(so));
so[0]=so[1]=false;
for(int i=4;i<=up;i+=2)so[i]=false;
sosuu.push_back(2);
for(int i=3;i<=up;i+=2){
if(so[i]==false)continue;
sosuu.push_back(i);
i2=i*2;
for(int j=i*3;j<=up;j+=i2){
so[j]=false;
}
}
}
void saiki(__int64 num,int count,int p){
if(num>limit)return;
if(count==4)is4[(int)num]=true;//4種の異なる素因数の組の積を求めてセットする関数
for(int i=p;i<sosuu.size()&&sosuu[i]*num<limit;i++){
saiki(num*sosuu[i],count==0?1:count+(p!=i),i);
if(count==4)break;
}
}
int main(){
double start=clock();
setSo();
memset(is4,false,sizeof(is4));
saiki(1,0,0);
int count=0;
for(int i=2;i<limit;i++){
if(is4[i]==true){
count++;
if(count==4){
printf("ans=%d time=%lf",i-3,clock()-start);
break;
}
}else{
count=0;
}
}
}
*問い48
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2048
次の式は, 1^1 + 2^2 + 33 + ... + 10^10 = 10405071317 である.
では, 1^1 + 2^2 + 3^3 + ... + 1000^1000 の最後の10桁を求めよ.
解法
計算回数50万回なので定義通り計算するだけでも十分間に合います。
大きい数を扱える整数型があれば計算量を減らせますが残念なことにC++標準の型では19桁程度までしか扱えません。
10ケタ*10ケタが桁あふれするためにC++ではライブラリか特殊な処理が必要となります。
めんどくさいのでそのまま計算しました。
#include<stdio.h>
#include<iostream>
int main(){
__int64 mod=1,sum=0,num;
for(int i=0;i<10;i++)mod*=10;
for(int i=1;i<=1000;i++){
num=i;
for(int j=1;j<i;j++){
num=(num*i)%mod;
}
sum=(sum+num)%mod;
}
std::cout<<sum;
}