Problem 73 2回目

あきらめるか。
threadを見ているとファレイ数列(参考:ファレイ数列 - Wikipedia)を利用している人がちらほら居るけど、これをRでやるとスタックが不足して「プロテクションスタックが溢れました><」とか怒られる。

## 1/b,1/d間、分母がlim以下のファレイ数列の個数
## 分子は個数を求めるだけなら省略可能
farey.count <- function(b, d, lim){
  if(b+d >= lim) return(0)
  return(1 +
         farey.count(b, b+d, lim) +
         farey.count(b+d, d, lim)
         )
}
## スタックが足りない!! ><
farey.count(2,3,10000)

ただ同じことをRubyでやると通る。7秒半。

def count_farey(b,d,lim)
  return 0 if b+d > lim
  return 1+count_farey(b+d,d,lim)+count_farey(b,b+d,lim)
end
count_farey(2,3,10000)

末尾再帰が最適化されている？
とはいえ、分母をちょっと増やすとやっぱスタックが足りなくなるのでだめ。
ならbrute forceな方法というわけでこういうことをするとクソ時間がかかる。

is.coprime <- function(a,b){
  while(a != 0){
    temp <- a
    a <- b%%a
    b <- temp
  }
  ifelse(b==1, TRUE, FALSE)
}

count <- 0
for(i in 5:10000){
  for(j in ceiling(i/2):floor(i/3)){
    if(is.coprime(i,j)) count <- count+1
  }
}

時間は測ってないけど分母1000までの探索で9秒かかるので知れている。
しかし同じことをC++でやると3秒半。

#include <iostream>
using namespace std;

bool iscoprime(int a, int b){
	int temp;
	while(a != 0){
		temp = a;
		a = b%a;
		b = temp;
	}
	return(b==1 ? true : false); 
}
int main(){
	int count = 0;
	for(int i=5; i <= 10000; i++){
		for(int j=i/3+1; j<=i/2; j++){
			if(iscoprime(i,j)) count++;
		}
	}
	cout << "answer = " << count << '\n';
}

ものには向き不向きがあるってことですかね。再帰を使わず力ずくでもない方法があればいけるのかもしれないけど思いつかないのでもうパス。