[seqfan] Vertices, edges, primes and non-primes

[Eric Angelini]

Hello SeqFans,
Let's build a "graph" step by step.

General rules:

(1) an edge links two integers "a" and "b" if 
    ("a" is prime and "b" is non-prime) or if
    ("a" is non-prime and "b" is prime);

    EXAMPLE: 1--2 or 7--4 are ok. 13--37 is not.

(2) from vertex "n" always leave "n" edges;

                   w...
                   |
    EXAMPLE: 1--2--4--3--y...
                  /    \
                 x...   z...

    "w" and "x" are primes, "y" and "z" are 
    non-primes.

    We see above that from vertex "1" leaves only
    1 link; from vertex "2" leave 2 links, from
    vertex "3" leave 3 links, from vertex "4" leave
    4 links, etc.

(3) always try to link a vertex "n" with a vertex < "n"
    (this is the "maximum compactness" condition)

----------

If we start to draw the graph step by step, we'll get:

1--2

1--2--4

        3
       /
1--2--4--5
       \
        7

        3--6
       / \
1--2--4-5-8
       \ 
        7
etc.
We see above that "5" is linked to 4 and 8; it will be
linked to "6" later and to 9 and 10 which are not yet
present. In the end, "5" will be linked 5 times to
non-prime integers that build the set [4,6,8,9,10]

The first line of the hereunder array is "n".
The vertical line under "n" is the list of the vertices
it is linked to:

n = 1   2   3   4   5   6   7   8   9  10  11   ...
    2   1   4   2   4   3   4   3   5   5   6   ...
        4   6   3   6   5   6   5   7   7   8   ...
            8   5   8   7   8   7  11  11   9   ...
                7   9  11   9  11  13  13  10   ...
                   10  13  10  13  17  17  12   ...
                       17  12  17  19  19  14   ...
                           14  19  23  23  15   ...
                               23  29  29  16   ...
                                   31  31  18   ...
                                       37  20   ...
                                           21   ...
     
The descending diagonal is not in the OEIS (2,4,8,7,10,...)

Best,
É.