laver-table.rb

require "pp"
require "set"
require "prime"

def generator?(p, g)
    gg = 1
    (1..p-2).all? do
        gg = (gg * g) % p
        gg != 1
    end
end

def find_generator(p)
    (1..p-1).find{|g| generator?(p, g) }
end

def find_q_and_r(p)
    q = nil
    r = Prime.find {|r| r > p
        q = Prime.take_while {|q| q < r}.find {|q|
            p < q && (q * r + 1) % p == 0
        }
    }
    [q, r]
end

def make_table(p, q)
    n = p * q
    table = Array.new(n) { Array.new(n) }
    n.times do |i|
        n.times do |j|
            table[i][j] = (p * i + (q - p + 1) * j) % n
        end
    end
    table
end

def make_laver_table(n)
    nn = 2**n
    table = Array.new(nn) { Array.new(nn) }
    nn.times do |i|
        table[i][0] = (i + 1) % (2**n)
    end
    begin
        updated = false
        nn.times do |i|
            nn.times do |j|
                k = table[i][j]
                l = table[i][0]
                if k && l && table[k][l] && !table[i][table[j][0]]
                    table[i][table[j][0]] = table[k][l]
                    updated = true
                end
            end
        end
    end while updated
    table
end

def generated_set(table, x)
    generated = Set.new
    generated.add x
    begin
        updated = false
        generated.dup.each do |y|
            generated.dup.each do |z|
                if !generated.include?(table[y][z])
                    generated.add table[y][z]
                    updated = true
                end
            end
        end
    end while updated
    generated.to_a
end

def calculate_cyclic_number(table, x)
    n = table.size
    gen = generated_set(table, x)
    appeared = Set.new
    gen.each do |y|
        gen.each do |z|
            appeared.add [y, table[y][z]]
        end
    end
    k = 1
    n.times do
        break if appeared.any?{|(a, b)|  a == b }
        appeared.dup.each do |y|
            gen.each do |z|
                appeared.add [y, table[y][z]]
            end
        end
        k += 1
    end
    k
end


p = 5
q, r = find_q_and_r(5)
table = make_table(p, q * r)

table.size.times do |i|
    p([i, generated_set(table, i), calculate_cyclic_number(table, i)])
end