Problem 130

Problem 130 - PukiWiki

(A(n)についてはProblem 129を参照)
5より大きな全ての素数pに対し、A(p)はp-1を割り切る。例えばp=41のとき、A(41)=5であるが、5は40を割り切る。
また、少ないながらもA(n)がn-1を割り切るような合成数も存在する。はじめの5つを示せば、91, 259, 451, 481, 703である。
GCD(n, 10)=1かつn-1がA(n)を割り切るような合成数nのはじめの25個の和を求めよ。

Problem 129のを使い回したら22秒だった。

library(gmp)

A <- function(n){
  if(n %% 2 == 0 || n %% 5 == 0) return(0)
  k <- 1
  m <- 1
  while(m != 0){
    k <- k + 1
    m <- (m * 10 + 1) %% n
  }
  k
}

isdivisible <- function(n){
  if(isprime(n)) return(FALSE)
  if((An <- A(n)) == 0) return(FALSE)
  if(((n-1) %% An) == 0) return(TRUE)
  FALSE
}

limit <- 25
ans.list <- numeric(limit)
count <- 0
n <- 2
while(count < limit){
  if(isdivisible(n)){
    count <- count + 1
    ans.list[count] <- n
  }
  n <- n + 1
}
sum(ans.list)