The Yellowstone sequence, also called the Yellowstone permutation, is defined as:

For n <= 3,

   a(n) = n

For n >= 4,

   a(n) = the smallest number not already in sequence such that a(n) is relatively prime to a(n-1) and 
          is not relatively prime to a(n-2).



The sequence is a permutation of the natural numbers, and gets its name from what its authors felt was a spiking, geyser like appearance of a plot of the sequence.



Example

a(4) is 4 because 4 is the smallest number following 1, 2, 3 in the sequence that is relatively prime to the entry before it (3), and is not relatively prime to the number two entries before it (2).



Task
 Find and show as output the first  30  Yellowstone numbers.


Extra
 Demonstrate how to plot, with x = n and y coordinate a(n), the first 100 Yellowstone numbers.


Related tasks

   Greatest common divisor.
   Plot coordinate pairs.


See also

   The OEIS entry:   A098550 The Yellowstone permutation.
   Applegate et al, 2015: The Yellowstone Permutation [1].


function gcd(a, b)
    if b == 0 then
        return a
    end
    return gcd(b, a % b)
end
 
function printArray(a)
    io.write('[')
    for i,v in pairs(a) do
        if i > 1 then
            io.write(', ')
        end
        io.write(v)
    end
    io.write(']')
    return nil
end
 
function removeAt(a, i)
    local na = {}
    for j,v in pairs(a) do
        if j ~= i then
            table.insert(na, v)
        end
    end
    return na
end
 
function yellowstone(sequenceCount)
    local yellow = {1, 2, 3}
    local num = 4
    local notYellow = {}
    local yellowSize = 3
    while yellowSize < sequenceCount do
        local found = -1
        for i,test in pairs(notYellow) do
            if gcd(yellow[yellowSize - 1], test) > 1 and gcd(yellow[yellowSize - 0], test) == 1 then
                found = i
                break
            end
        end
        if found >= 0 then
            table.insert(yellow, notYellow[found])
            notYellow = removeAt(notYellow, found)
            yellowSize = yellowSize + 1
        else
            while true do
                if gcd(yellow[yellowSize - 1], num) > 1 and gcd(yellow[yellowSize - 0], num) == 1 then
                    table.insert(yellow, num)
                    yellowSize = yellowSize + 1
                    num = num + 1
                    break
                end
                table.insert(notYellow, num)
                num = num + 1
            end
        end
    end
    return yellow
end
 
function main()
    print("First 30 values in the yellowstone sequence:")
    printArray(yellowstone(30))
    print()
end
 
main()