原始数列システムでε_0までの順序数を扱う

=begin
1: (0)
2: (0,0)
ω: (0,1)
ω*2: (0,1,0,1)
ω^2: (0,1,1)
ω^ω: (0,1,2)
ω^(ω*2): (0,1,2,1,2)
ω^ω^2: (0,1,2,2)
ω^ω^ω: (0,1,2,3)

ja: http://ja.googology.wikia.com/wiki/%E5%8E%9F%E5%A7%8B%E6%95%B0%E5%88%97%E6%95%B0
en: http://googology.wikia.com/wiki/User_blog:Kyodaisuu/A_program_of_Kirby-Paris_hydra
=end

class Priseq
    def self.[] *m;new *m end
    attr_reader :m
    def initialize *m;@m = m end
    def succ;Primat[*@m,0] end
    def succ?;@m.last===@m.min end
    def zero?;@m.size===0 end
    def === x;min=@m.min;return @m===x.m.map{|a|a-min} if x.is_a? Priseq;false end
    def pred;return Priseq[*@m[0..-2]] if succ?;self end
    def < x
        if x.is_a? Priseq
            min = @m.min
            m = x.m.map{|c|c-min}
            r = @m.each_with_index do |a,i|
                b = m[i]
                return false unless b
                return true if a<b
            end
            return false if r==@m
            return r
        end
        false
    end
    def > x
        if x.is_a? Priseq
            min = @m.min
            m = x.m.map{|c|c-min}
            r = m.each_with_index do |a,i|
                b = @m[i]
                return false unless b
                return true if a<b
            end
            return false if r==m
            return r
        end
        true
    end
    def >= x;!(self<x) end
    def <= x;!(self>x) end
    def + x
        return Priseq[*(self<x ? x.m+@m : @m+x.m)] if x.is_a?
        Priseq[*@m, *([0]*x.to_i)]
    end
    def to_s;'('+@m.join(',')+')' end
    def [] n
        min = @m.min
        i = @m.rindex{|a|a>min}
        a = @m[i]
        r = Priseq[*@m]; m = r.m
        j = m[0,i].rindex{|b|b<a}
        m.delete_at i
        m.insert j, *(m.slice!(j,i-j) * n)
        return m.size if m.all?{|c|min===c}
        r
    end
end
def Priseq *m;Priseq.new *m end
class Integer;def succ?;self>0 end end

#Slow-growing hierarchy
def g(a,n)
    return 0 if a.zero?
    return g(a.pred,n)+1 if a.succ?
    g(a[n],n)
end

#Hardy hierarchy
def H(a,n)
    return n if a.zero?
    return g(a.pred,n+1) if a.succ?
    H(a[n],n)
end

#Fast-growing hierarchy
def f(a,n)
    return n+1 if a.zero?
    if a.succ?
        r = n; b = a.pred
        n.to_i.times{ r = f(b,r) }
        return r
    end
    f(a[n],n)
end