# [seqfan] Re: Symmetric Relations and Self-Inverse Permutations

David Wilson davidwwilson at comcast.net
Wed Apr 8 00:55:37 CEST 2009

```Yes, that's a very nice generalization.

Worth a paper.

----- Original Message -----
From: <franktaw at netscape.net>
To: <seqfan at seqfan.eu>
Sent: Tuesday, April 07, 2009 4:23 AM
Subject: [seqfan] Symmetric Relations and Self-Inverse Permutations

>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.)
>
>
> (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.)
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/

--------------------------------------------------------------------------------

No virus found in this incoming message.
Checked by AVG - www.avg.com
Version: 8.0.238 / Virus Database: 270.11.45/2045 - Release Date: 04/07/09
06:41:00

```