# [seqfan] Symmetric Relations and Self-Inverse Permutations

franktaw at netscape.net franktaw at netscape.net
Tue Apr 7 10:23:38 CEST 2009

```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.)