[seqfan] Message from Marc LeBrun

[Neil Sloane]

Marc sent me this 2 days ago, but I am taking the liberty
of forwarding it to the mailing list since it is very relevant to
the on-going discussion of discriminators.
Neil

========

This discriminator idea is very nice.  We can generalize it to apply to ANY
set of integers S, saying d _discriminates_ S just if all the Sn mod d are
distinct.

Note that S has multiple discriminators; indeed all d > max S discriminate,
(moreover EVERY positive number trivially discriminates any singleton set).

Anyway, since the set of discriminators is unbounded it's natural to
distinguish the _least-discriminator_.

Conversely, we might call every non-discriminator a _confuser_.

Note that 1 confuses every non-singleton set, but a nice thing about this
kind of confusion is that the set of confusers is bounded!

Anyway, analogously we distinguish the _greatest-confuser_.

========

Turning to sequences, we define the _accumulation_ An of an integer sequence
a(n) as the sequence of sets {a0} {a0 a1} {a0 a1 a2} ...

Then what A., B., & McC. defined in 1985 as their "discriminator sequence"
d(n) for a(n) is more precisely the sequence of least-discriminators of An.

Likewise, it would be interesting to see what the "greatest-confuser
sequences" are like.

========

Of course sets of non-negative integers S beg to be binary-encoded as b(S),
where a 1 in the nth bit position denotes the membership of n in the set S.

The sequence Bn of sets encoded 1-to-1 by the integers from 0 begins
  {} {0} {1} {0 1} {2} {0 2} {1 2} {0 1 2} {3} {0 3} {1 3} {0 1 3} ...

The evil/odious numbers simply correspond to the sets with an even/odd
number of members.

If we look at the number of members in the Bn sets we of course get
  0 1 1 2 1 2 2 3 1 2 2 3 ... A000120

I think the sequence of least discriminators begins (pace quibbles re. 0)
  0 1 1 2 1 3 2 3 1 2 3 4 ... Not in OEIS?

And (barring misteaks) the sequence of greatest confusers (ditto, arguably)
  0 0 0 1 0 2 1 1 0 3 2 3 ... Not in OEIS?

Of course we can take any sequence of integers, map them to sets, transform
the sets and conversely map the results back to integers.

========

Side bar: the intersection of two sets corresponds to the bitwise-AND of
their binary encodings, the union to their bitwise-OR and so on.

Multiplying the encoding by 2^k corresponds to adding k to each member.

Addition of the encodings x+y of sets X and Y corresponds to the result of
the following recursive set procedure
  F(X,Y):=
    if Y={}
      then X
      else F(set-difference(X,Y), increment-members(intersection(X,Y)))

Example:
  1 + 1 -->
  F({0},{0}) -->
  F({},{1}) -->
  F({1},{}) -->
  {1} -->
  2

(a handy adder in case you ever are in an obfuscated coding contest!)

The encoding of the set of every pairwise sum of the members of X and Y can
be computed by performing a carryless binary multiplication of x and y using
bitwise-OR in place of regular addition.

What is the encoding of the set of all pairwise ORs of members of X and Y?

========