project-euler/Sidef/129 Repunit divisibility.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# License: GPLv3
# Date: 11 May 2017
# https://github.com/trizen

# https://projecteuler.net/problem=129

# Runtime: 11.569s (previously: 29.843s)

for n in (1e6 .. Inf) {

    n.is_coprime(10) || next

    var k = 1
    var sum = 1

    loop {
        sum = addmod(sum, 10.powmod(k, n), n)
        sum.is_zero && break
        ++k
    }

    if (k+1 > 1e6) {
        say "A(#{n}) = #{k+1}"
        break
    }
}