[seqfan] Symmetric Relations and Self-Inverse Permutations

[franktaw at netscape.net]

I recently posted an email noting the following theorem:

Let R be a symmetric relation on the positive (or nonnegative) 
integers.  Define a(n) to be the smallest number (in the specified 
range) not yet in the sequence such that R(n,m) is true; leave a(n) 
undefined if none such exists.  Then, whenever a(n) is defined, a(a(n)) 
is also defined and equals n.

In particular, if a(n) is always defined (as when there are always 
infinitely many m such that R(n,m)), then a will be a self-inverse 
permutation.

In fact, every self-inverse permutation of the positive (or 
nonnegative) integers can be generated in this way: just take R(n,m) to 
be a(n) = m.

Here are some interesting examples in the OEIS:

A000027 (or A001477) n = m (or any other reflexive relation)
A004442 n != m (0 based)
A011262 m and n have the same set of prime factors, but with all 
different exponents
A014681 n != m
A020703 n + m = 2k^2 + 2k + 2 for some k
A038722 n + m = k^2 + 1 for some k
A061579 n + m = k^2 - 1 for some k (0 based)
A065190 gcd(n,m) = 1
A071065 n + m is an odd prime
A073675 n|m or m|n but n != m
A073842 n = m^k or m = n^k but n != m
A073843 n = m^r, r rational != 1
A083569 n + m is prime
A094510 A000120(n) = A000120(m) but n != m [sum of binary digits]
A094681 omega(n) = omega(m) but n != m, a(1) = 1 (*)
A100527 bigomega(n) = bigomega(m) but n != m, a(1) = 1
A100830 n = m (mod 9) but n != m

(*) At this writing, the description of A094681 is wrong; it states 
that n and a(n) have no prime factors in common, but that does not 
match the values.  I have sent in a correction.  I may submit versions 
of A094681 and A100527 with the condition gcd(n,m) = 1 instead of n != 
m.

And two new ones I just submitted:

A159193 gcd(n,m) > 1 but n != m, with a(1) = 1
A159253 n * m is a cube

A011262 and A159253 are interesting in that they are also 
multiplicative.  (Of course, A000027 is also multiplicative.)

Franklin T. Adams-Watters

(This came up in the context of numbers that have no digit in common, a 
discussion that I'm sure a number of you stopped reading.)