number2expression.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 01 May 2022
# https://github.com/trizen

# Compress a number into a polynomial expression in a given base.

func number2expr(n, base=10) {

    if (!n.is_int && n.is_rat) {     # rational support
        var (nu, de) = n.nude
        return (__FUNC__(nu, base) / __FUNC__(de, base))
    }

    var D = n.digits(base).flip
    var t = D.len

    D.run_length.sum_2d {|d,l|
        t -= l
        (l == 1) ? d*Poly(t) : (((Poly(l) - 1)/(base-1) * d) * Poly(t))
    }
}

func number2expr_alt(n, base=10) {   # returns: n * (base-1)

    if (!n.is_int && n.is_rat) {     # rational support
        var (nu, de) = n.nude
        return (__FUNC__(nu, base) / __FUNC__(de, base) * (base-1))
    }

    var D = n.digits(base).flip
    var t = D.len

    D.run_length.sum_2d {|d,l|
        t -= l
        ((Poly(l) - 1) * d) * Poly(t)
    }
}

var tests = [
    [0b100000100000111111101, 2],
    [(7**911 - 4*(7**455) - 1), 7],
    [11113338888999999999, 10],
    [43/97, 10],
]

for n,b in (tests) {
    say ("base #{'%2d'%b}: ", number2expr(n,b).pretty)
    say ("base #{'%2d'%b}: (", number2expr_alt(n,b).pretty, ")/#{b-1}")
    say ''
    assert_eq(number2expr(n,b) -> eval(b), n)
    assert_eq(number2expr_alt(n,b)/(b-1) -> eval(b), n)
}

__END__
base  2: x^20 + x^14 + x^9 - x^2 + 1
base  2: (x^21 - x^20 + x^15 - x^14 + x^9 - x^2 + x - 1)/1

base  7: x^911 - x^456 + 3*x^455 - 1
base  7: (6*x^911 - 4*x^456 + 4*x^455 - 6)/6

base 10: 1/9*x^20 + 2/9*x^16 + 5/9*x^13 + 1/9*x^9 - 1
base 10: (x^20 + 2*x^16 + 5*x^13 + x^9 - 9)/9

base 10: (4*x + 3)/(9*x + 7)
base 10: ((36*x^2 - 9*x - 27)/(9*x^2 - 2*x - 7))/9