semiconvergents.sf

#!/usr/bin/ruby

# Generate the semiconvergents for a given real number, between the first `r` convergents.

# See also:
#   https://en.wikipedia.org/wiki/Continued_fraction
#   https://en.wikipedia.org/wiki/Farey_sequence
#   https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree

func semiconvergents(n, callback, r=10) {

    var cfrac = n.as_cfrac

    for k in (1 .. min(r, cfrac.end-1)) {

        var c1 = cfrac.first(k).flip.reduce{|a,b| b + 1/a }
        var c2 = cfrac.first(k+1).flip.reduce{|a,b| b + 1/a }

        var (a1, b1) = c1.nude
        var (a2, b2) = c2.nude

        for m in (1 .. cfrac[k+1]) {

            var a3 = (a1 + m*a2)
            var b3 = (b1 + m*b2)

            callback(a3 / b3)
        }
    }
}

var r = Num.e       # any real value

semiconvergents(r, {|c|
    printf("%-49s ~ %s\n", c, c.as_frac)
})

__END__
2.5                                               ~ 5/2
2.66666666666666666666666666666666666666666666667 ~ 8/3
2.75                                              ~ 11/4
2.71428571428571428571428571428571428571428571429 ~ 19/7
2.72727272727272727272727272727272727272727272727 ~ 30/11
2.72222222222222222222222222222222222222222222222 ~ 49/18
2.72                                              ~ 68/25
2.71875                                           ~ 87/32
2.71794871794871794871794871794871794871794871795 ~ 106/39
2.71830985915492957746478873239436619718309859155 ~ 193/71
2.71818181818181818181818181818181818181818181818 ~ 299/110
2.71823204419889502762430939226519337016574585635 ~ 492/181
2.71825396825396825396825396825396825396825396825 ~ 685/252
2.71826625386996904024767801857585139318885448916 ~ 878/323
2.71827411167512690355329949238578680203045685279 ~ 1071/394
2.71827956989247311827956989247311827956989247312 ~ 1264/465
2.71828358208955223880597014925373134328358208955 ~ 1457/536
2.71828171828171828171828171828171828171828171828 ~ 2721/1001
2.71828236824983734547820429407937540663630448926 ~ 4178/1537
2.71828211189913317572892040977147360126083530339 ~ 6899/2538
2.7182820005651313930488838654987284543656400113  ~ 9620/3539
2.71828193832599118942731277533039647577092511013 ~ 12341/4540
2.71828189857426457318173614870961920231005233712 ~ 15062/5541
2.71828187098746560684805869764597982268419443595 ~ 17783/6542
2.71828185072252419461752618321622696539838260639 ~ 20504/7543
2.71828183520599250936329588014981273408239700375 ~ 23225/8544