Problem Statement

Repunits are numbers that consist entirely of repetitions of the digit one (unity). The notation Rn symbolizes the repunit made up of n ones. Every prime p larger than 5, evenly divides the repunit Rp-1.

The repunit R6 is evenly divisible by 7. 111111 / 7 = 15873 The repunit R42 is evenly divisible by 43. 111111111111111111111111111111111111111111 / 43 = 2583979328165374677002583979328165374677 And so on.

There are composite numbers that also have this same property. They are often referred to as deceptive non-primes or deceptive numbers.

The repunit R90 is evenly divisible by the composite number 91 (=7*13).

Let's start with the solution:

let modpow m =
  let rec loop p b e =
    if e land 1 = 0
    then if e = 0 then p else loop p (b * b mod m) (e lsr 1)
    else loop (p * b mod m) (b * b mod m) (e lsr 1)
  in loop 1

let is_deceptive n =
  let rec loop x =
    x * x <= n && (n mod x = 0 || n mod (x + 4) = 0 || loop (x + 6))
  in
  n land 1 <> 0 && n mod 3 <> 0 && n mod 5 <> 0 &&
  modpow n 10 (pred n) = 1 && loop 7

let () =
  Seq.(ints 49 |> filter is_deceptive |> take 100
  |> iter (Printf.printf " %u%!")) |> print_newline