「オイラープロジェクト61～70」の編集履歴（バックアップ）一覧に戻る
オイラープロジェクト61～70 - (2012/10/26 (金) 20:41:34) のソース
*問い61
三角数, 四角数, 五角数, 六角数, 七角数, 八角数は多角数であり, それぞれ以下の式で生成される.
三角数 P3,n=n(n+1)/2 1, 3, 6, 10, 15, ...
四角数 P4,n=n2 1, 4, 9, 16, 25, ...
五角数 P5,n=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 P6,n=n(2n-1) 1, 6, 15, 28, 45, ...
七角数 P7,n=n(5n-3)/2 1, 7, 18, 34, 55, ...
八角数 P8,n=n(3n-2) 1, 8, 21, 40, 65, ...
3つの4桁の数の順番付きの集合 (8128, 2882, 8281) は以下の面白い性質を持つ.
この集合は巡回的である. 最後の数も含めて, 各数の後半2桁は次の数の前半2桁と一致する
それぞれ多角数である: 三角数 (P3,127=8128), 四角数 (P4,91=8281), 五角数 (P5,44=2882) がそれぞれ別の数字で集合に含まれている
4桁の数の組で上の2つの性質をもつはこの組だけである.
同じように, 6つの4桁の数からなる順番付きの集合で,
集合は巡回的である
三角数, 四角数, 五角数, 六角数, 七角数, 八角数が全て表れる 唯一の集合を求め, その和を求めよ.
最初に1000～9999の間の数が何角数であるかをメモ化します。
後は範囲が狭いのでスタートを決めて条件を満たす数を再帰で全探索するだけです。
このときｎ角数∧m角数であるような数に対処するために探索を分岐するだけです。
#include<stdio.h>
int memo[10000]={0};
int ans[6];
void saiki(int num,int perm,int deep,int ss){
if(deep==6){
int sum=0;
if(num==ss&&perm==63){
for(int i=0;i<6;i++){
printf("%d ",ans[i]);
sum+=ans[i];
}
printf(" %d\n",sum);
}
}else{
int next;
for(int i=0;i<100;i++){
next=num+i;
int p=memo[next];
for(int k=1;k<=32;k*=2){
if(((p&k)!=0)&&((perm&k)==0)){
ans[deep]=next;
saiki(i*100,perm|k,deep+1,ss);
}
}
}
}
}
int up=10000;
int main(){
int m;
for(int n=1;n<=up;n++){
m=(n*(n+1))/2;
if(m<up&&m>999)memo[m]|=1;
m=n*n;
if(m<up&&m>999)memo[m]|=2;
m=(n*(3*n-1))/2;
if(m<up&&m>999)memo[m]|=4;
m=n*(2*n-1);
if(m<up&&m>999)memo[m]|=8;
m=(n*(5*n-3))/2;
if(m<up&&m>999)memo[m]|=16;
m=(n*(3*n-2));
if(m<up&&m>999)memo[m]|=32;
}
for(int i=10;i<100;i++){
saiki(i*100,0,0,i*100);
}
}
*問い62
立方数 41063625 (3453) は, 桁の順番を入れ替えると2つの立方数になる: 56623104 (3843) と 66430125 (4053) である. 41063625は, 立方数になるような桁の置換をちょうど3つもつ最小の立方数である.
立方数になるような桁の置換をちょうど5つもつ最小の立方数を求めよ.
立法数の密度はすごく薄いので全探索で解きます。
#include<stdio.h>
#include<map>
#include<iostream>
struct S{
int count[10];
__int64 num;
bool operator<(const S& s)const{
for(int i=0;i<10;i++){
if(count[i]!=s.count[i])return count[i]<s.count[i];
}
return false;
}
void set(__int64 n){
num=n;
for(int i=0;i<10;i++)count[i]=0;
while(n!=0){
count[(int)(n%10)]++;
n/=10;
}
}
};
int main(){
S s,s2;
std::map<S,int> memo;
__int64 mymax=2097151,n;//int64の最大値の立方根
for(__int64 i=1;i<mymax;i++){
s.set(i*i*i);
if(memo.find(s)==memo.end()){
memo[s]=1;
}else{
memo[s]++;
}
}
std::map<S,int>::iterator it;
__int64 ans=-1;
for(it=memo.begin();it!=memo.end();it++){
if((*it).second==5){
n=(*it).first.num;
if(ans==-1)ans=n;
else ans=ans<n?ans:n;
}
}
std::cout<<ans;
}
*問い64
平方根の循環部分が奇数桁になるのは10000までに何個あるか答える問題。
連分数について授業を受けたことがないのでページとずっとにらめっこしてルールを理解しさらにそれをコードに立ち上げるのに２時間もかかった。
なぜうまく動くのかは不明なので私にとっては教育効果0の問題。
人生の無駄使いだな。
まあ何故これで平方根がもとまるかよく考えてみることにしようと思う。
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<map>
int gcd (int a,int b )
{
int c;
while ( a != 0 ) {
c = a; a = b%a; b = c;
}
return b;
}
struct S{
int a,b;
bool operator<(const S& s)const{
if(a!=s.a)return a<s.a;
return b<s.b;
}
};
std::map<S,int> memo;
int saiki(int n,int a,int b,int up,int deep){
//1/(√23+4) b/(√n+a);
int b2=n-a*a,k,t,a2;
if(b2==0)return 0;
S s;
s.a=a;
s.b=b;
if(memo.find(s)!=memo.end()){
return deep-memo[s];
}
memo[s]=deep;
k=gcd(b,b2);
b2/=k;
t=(a+up)/b2;
a2=abs(t*b2-a);
return saiki(n,a2,b2,up,deep+1);
}
int main(){
int k,t,ans=0;
for(int i=2;i<=10000;i++){
k=sqrt(i);
memo.clear();
t=saiki(i,k,1,k,0);
ans+=(t&1);
}
printf("%d\n",ans);
}
*問い65
http://projecteuler.net/problem=65
eについての連分数である近似分数の100項目の分子の桁の合計を求めよ。
定義通りlispで実装します。
(defun t(n)
(if (= (mod (- n 1) 3) 0)
(+ (* 2 (/ (- n 1) 3)) 2)
1))
(defun calc (deep n)
(if (= (+ 2 deep) n)
(/ 1 (t deep))
(/ 1 (+ (t deep) (calc (+ deep 1) n)))))
calc
(defun wa (n sum)
(if (= n 0)
sum
(wa (floor (/ n 10)) (+ sum (mod n 10)))))
wa
(wa (numerator (+ 2 (calc 0 100))) 0)
*問い67
http://projecteuler.net/problem=67
三角形に並んだ数字を上から下へ向かいながら途中の経路の計が最高になるルートの合計値を見つけよという問題。
問い18のコードのサイズを少し変更するだけで作成可能。
#include<stdio.h>
#include<algorithm>
#include<string.h>
int main(){
int memo[2][101],a,now,next;
sizeof(memo,0,sizeof(memo));
scanf("%d",&memo[0][0]);
for(int i=1;i<100;i++){
now =(i+1)%2;
next=i%2;
for(int j=0;j<=i;j++){
scanf("%d",&a);
if(j==i){
memo[next][j]=memo[now][j-1]+a;
}else if(j>0&&j<i){
memo[next][j]=std::max(memo[now][j-1],memo[now][j])+a;
}else{
memo[next][j]=memo[now][j]+a;
}
}
}
int ans=0;
for(int i=0;i<100;i++)ans=std::max(ans,memo[next][i]);
printf("%d\n",ans);
}
*問い68
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2068
問題文をきちんと読んでないために少し苦戦した問題です。
5角系の魔法陣リングに1～10までの数字を入れて魔法陣として成立させる問題です。
魔法陣を満たすかつ列を文字列として繋げるとき、始まりの数字が一番小さな列を出発点として時計回りに繋げるという条件のもとで繋げるという問題です。
この一番小さい列というのを最初見落としていました。
#include<stdio.h>
#include<iostream>
#include<string.h>
int moto[]={1,2,3,4,5,6,7,8,9,10};
int ps[]={0,1,2,3,2,4,5,4,6,7,6,8,9,8,1};
int board[15]={0};
__int64 ans=0;
void print(){
for(int i=0;i<15;i++){
printf("%d",board[ps[i]]);
};
}
void changeAns(){
__int64 t=0;
int count=0,num=board[0],base,p;
for(int i=0;i<15;i+=3){
if(num>=board[ps[i]]){
num=board[ps[i]]%10;
base=i;
}
}
printf(" %d\n",base);
for(int i=0;i<15;i++){
p=ps[(i+base)%15];
if(board[p]==10){
if(++count>1)return;
t*=100;
}else{
t*=10;
}
t+=board[p];
}
if(ans<t){
ans=t;
}
}
void saiki(int deep,int sum){
if(deep%3==0){
int p=deep-3;
int wa=board[ps[p]]+board[ps[p+1]]+board[ps[p+2]];
if(deep==15){
if(wa==sum){
print();
changeAns();
}
return;
}else if(sum==0){
sum=wa;
}else if(sum!=wa){
return;
}
}
int p=ps[deep];
if(board[p]==0){
for(int i=0;i<10;i++){
if(moto[i]!=0){
board[p]=moto[i];
moto[i]=0;
saiki(deep+1,sum);
board[p]=0;
moto[i]=i+1;
}
}
}else{
saiki(deep+1,sum);
}
}
int main(){
memset(board,0,sizeof(board));
saiki(0,0);
std::cout<<ans;
}
*問い69
オイラーのトーティエント関数、φ(n)[時々ファイ関数とも呼ばれる]は、nと互いに素なn未満の数の数を定める。たとえば、1、2、4、5、7、そして8はみな9未満で9と互いに素であり、φ(9)=6.
n 互いに素な数 φ(n) n/φ(n)
2 1 1 2
3 1,2 2 1.5
4 1,3 2 2
5 1,2,3,4 4 1.25
6 1,5 2 3
7 1,2,3,4,5,6 6 1.1666...
8 1,3,5,7 4 2
9 1,2,4,5,7,8 6 1.5
10 1,3,7,9 4 2.5
n ≤ 10ではn/φ(n)の最大値はn=6であることがわかる。
n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ。
ファイ関数の結果について２～100万までエラトステネスの篩と同じ要領で計算して記録します。
速度的に早いのかどうかはよくわかりませんがとりあえず試行錯誤の末にたどり着いた自作アルゴリズムによるコードです。
このへんは数論でも基礎的でしょうし車輪の再発明だと思いますが自分で考えつけたというのは嬉しい限りです。
分解を利用した正式なコードの方が多分早いでしょう。
まずコードはa(n+1)はai(i=1...n)全ての数を素でない数として含みます。
これを全てのaで足し合わせていきます。
この時一度倍数で足したものは足さないようにcount[i]==0で条件を満たすものだけ足します。
後は次のループでｎの倍数とｍの倍数が共通になるような部分が重複して足されているのでこれを引いていき、引きすぎた分をcount[i]==0&&dell[i]!=0分岐で足しなおせば答えが出ます。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
const int up=1000000;
int data[up+1],count[up+1],dell[up+1];
void setData(){
int k,add;
memset(data,0,sizeof(data));
memset(count,0,sizeof(count));
memset(dell,0,sizeof(dell));
for(int i=2;i<=up;i++){
//printf("\n%d ",i);
if(count[i]==0){
k=1;
for(int p=i*2;p<=up;p+=i){
data[p]+=k;
//printf("(%d %d %d)",p,k,data[p]);
k++;
count[p]++;
dell[p]++;
}
}
}
//for(int i=2;i<=up;i++){
//printf("%d %d %d\n",i,i-data[i]-1,count[i]);
//}
for(int i=2;i<=up;i++){
if(count[i]>1){
k=count[i]-1;
add=1;
}else if(count[i]==0&&dell[i]!=0){
k=-1;
add=-1;
}else{
continue;
}
//printf("%d %d\n",i,k);
for(int p=i*2;p<=up;p+=i){
data[p]-=k;
k+=add;
count[p]-=add;
}
}
//for(int i=2;i<=up;i++){
//printf("%d %d %d\n",i,i-data[i]-1,count[i]);
//}
//printf("\n");
}
int main(){
setData();
double ans=0,t;
int ansN;
for(int i=2;i<=up;i++){
if(i-1==data[i]){
printf("out%d\n",i);
continue;
}
//printf("%d %d\n",i,i-data[i]-1);
t=((double)i)/(i-1-data[i]);
//printf("%d %lf\n",i,t);
if(t>ans){
ans=t;
ansN=i;
}
//if(i==1000||i==216||i==72)printf("%d %d\n",i,i-1-data[i]);
}
printf("%d %lf",ansN,ans);
}
*問い70
オイラーのトーティエント関数 φ(n) (ファイ関数とも呼ばれる) とは、n 未満の正の整数で n と互いに素なものの個数を表す。例えば、1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので、φ(9) = 6 となる。
1 は全ての正の整数と互いに素であるとみなされる。よってφ(1) = 1 である。
面白いことに、φ(87109)=79180 であり、87109は79180を置換したものとなっている。
1 < n < 10^7 で φ(n) が n を置換したものになっているもののうち、n/φ(n) が最小となる n を求めよ。
速度はまあまあだが大量にメモリを消費する方法でクリア。
100万までを求めて、100万から1000万まではφ(n)=φ(a)φ(b),a,bは素という性質を利用して分解したほうがよかったかな。
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
#include<string.h>
const int up=10000000;
__int64 data[up+1],count[up+1],dell[up+1];
void setData(){
__int64 k,add;
memset(data,0,sizeof(data));
memset(count,0,sizeof(count));
memset(dell,0,sizeof(dell));
for(int i=2;i<=up;i++){
//printf("\n%d ",i);
if(count[i]==0){
k=1;
for(int p=i*2;p<=up;p+=i){
data[p]+=k;
//printf("(%d %d %d)",p,k,data[p]);
k++;
count[p]++;
dell[p]++;
}
}
}
//for(int i=2;i<=up;i++){
//printf("%d %d %d\n",i,i-data[i]-1,count[i]);
//}
for(int i=2;i<=up;i++){
if(count[i]>1){
k=count[i]-1;
add=1;
}else if(count[i]==0&&dell[i]!=0){
k=-1;
add=-1;
}else{
continue;
}
//printf("%d %d\n",i,k);
for(int p=i*2;p<=up;p+=i){
data[p]-=k;
k+=add;
count[p]-=add;
}
}
for(int i=2;i<=up;i++){
//printf("%d %d %d\n",i,i-data[i]-1,count[i]);
}
//printf("\n");
}
bool check(int n){
int count[10]={0};
__int64 m=n-1-data[n];
while(n!=0){
count[n%10]++;
n/=10;
}
while(m!=0){
count[m%10]--;
m/=10;
}
for(int i=0;i<10;i++){
if(count[i]!=0)return false;
}
return true;
}
int main(){
setData();
double ans=up,t;
int ansN;
for(int i=2;i<up;i++){
if(check(i)==false)continue;
t=((double)i)/(i-1-(double)data[i]);
if(ans>t){
printf("(%d %d %lf)",i,i-1-(int)data[i],t);
ans=t;
ansN=i;
}
if(i==87109)printf("%d %d\n",i,i-1-(int)data[i]);
}
printf("\n%d %lf",ansN,ans);
}
*問題ＮＯ書き忘れた問題。
5桁の数 16807 = 7^5は自然数を5乗した数である. 同様に9桁の数 134217728 = 8^9も自然数を9乗した数である.
自然数をn乗して得られるn桁の正整数は何個あるか?
対数を使って式変形すれば簡単に解ける
#include<stdio.h>
#include<math>
int main(){
int ans=1;//1を最初に足す
for(int i=2;i<10;i++){
//10以上は桁数の増加より数字の増加が早いので無視
double d=log(i)/log(10);
printf("%lf\n",1/(1-d));
ans+=(int)(1/(1-d));
}
printf("%d\n",ans);
}
