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(p)
    Prime.find {|q| q > p && (q + 1) % p == 0 }
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|
        appeared.add table[x][y]
    end
    p appeared
    k = 1
    n.times do
        break if appeared.include?(x)
        appeared.dup.each do |y|
            gen.each do |z|
                appeared.add table[y][z]
            end
        end
        k += 1
    end
    k == n + 1 ? Float::INFINITY : k
end

#m = 3
#n = 2**m
#table = make_laver_table(n)

p find_q(5)
table = make_table(5, find_q(5))

table.each do |row|
    #puts row.map{|x|"%3d" % x}.join(" ")
end
table.size.times do |i|
    p [i, generated_set(table, i)]
    p calculate_cyclic_number(table, i)
end