(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)