project-euler/Sidef/064 Odd period square roots.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 31 August 2016
# License: GPLv3
# https://github.com/trizen

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

# Algorithm from:
#   https://web.math.princeton.edu/mathlab/jr02fall/Periodicity/mariusjp.pdf

# Runtime: 5.127 (previously: 6.002s)

func period_length(n) {

    var x = n.isqrt
    var y = x
    var z = 1

    var period = 0

    do {
        y = (((x + y) // z) * z - y)
        z = ((n - y*y) // z)
        ++period
    } while (z > 1)

    return period
}

say (1..10000 -> count_by { |n|
    n.is_sqr ? false : period_length(n).is_odd
})