Project Euler Problem 26 - 最も長い順環節を持つ循環小数

d < 1000について、1/dの順環節が最長となるdを求めよ。

以下解答

ncycle <- function(num, den){
  rems <- numeric(0)
  idx <- 1L
  rem <- num
  repeat{
    quo <- rem %/% den
    rem <- rem %% den
    if(rem %in% rems) break
    rems <- c(rems, rem)
    rem <- rem * 10L
    idx <- idx + 1L
  }
  if(rem == 0L) return(0L)
  if(idx == limit) return(NA_integer_)
  length(rems) - which(rem==rems) + 1L
}


slimit <- 999L
cyclelen <- sapply(1L:slimit, ncycle, num=1L)

余りを調べていけばいい。0.5秒（明示的に整数型にしないと1秒弱かかる）。

ところで、この方法だと順環節の長さの分だけのベクトルが必要になる。また、途中でベクトルを伸ばすので速度的にも不利である。

順環を検出するためのアルゴリズムとして、フロイドの循環検出法というものがある(cf. フロイドの循環検出法 - Wikipedia)。このアルゴリズムでは最新の余りだけを保持しておけばよく、単に順環節の長さを求めるだけであれば、順環節の長さにかかわらず必要なベクトルのサイズが増大しない。

ncycle <- function(num, den){
  rabbit <- (((num * 10L) %% den) * 10L) %% den
  turtle <- ((num * 10L) %% den)
  
  while(rabbit != turtle){
    rabbit <- (((rabbit * 10L) %% den) * 10L) %% den 
    turtle <- (turtle * 10L) %% den
  }

  rabbit <- num
  while(rabbit != turtle){
    rabbit <- (rabbit * 10L) %% den 
    turtle <- (turtle * 10L) %% den
  }
  
  cnt <- 1L
  rabbit <- (((rabbit * 10L) %% den) * 10L) %% den
  turtle <- (turtle * 10L) %% den
  while(rabbit != turtle){
    rabbit <- (((rabbit * 10L) %% den) * 10L) %% den 
    turtle <- (turtle * 10L) %% den
    cnt <- cnt + 1L
  }
  return(cnt)
}


slimit <- 999L
cyclelen <- sapply(1L:slimit, ncycle, num=1L)
which(max(cyclelen) == cyclelen)