A novice here, so please go easy on me.
I am struggling with a problem that involves a sequence of numbers. So here is what I am looking for. Let's say x is a 100-tuple (1,2,3...,100) and y is a 50-tuple (2,4,6...,100). I want to define an operator O, such that z = x O y is a 50-tuple with all the elements of x after removing all the elements of y from it.
z = (1,3,5,...,99) or a 50-tuple of odd numbers.
Is such an operation known and studied before? Any direction will be much appreciated.
This sounds like the set-theoretic difference: $A \setminus B = \{x \in A \mid x \not \in B\}$.
OP has clarified that the actual question is not the question asked. From comments on the other answer (at the time of this writing) "My inquiry comes from trying to solve this problem: One hundred people are sitting in a circle each of who is numbered by their position. First person touches the second and the second walks out, third touches the fourth and fourth walks out and so on. This process is repeated until only one is left. What is the number of that person. The answer is 73. I was trying to solve it for a general case."
Break the operation into "loops": passes around the circle where a person with a lower numbered position dismisses a person with a higher numbered position. A new loop starts when the person with the highest number has just been dismissed or the person with the highest number has just dismissed the person with the lowest number.
Observe that on each loop, the "gap", the difference between consecutive survivor position numbers, doubles. It is initially $1$, then on the first pass every alternating person is dismissed leaving gaps of $2$, then on the second pass every alternating person is dismissed leaving gaps of $4$, and so on.
If the total number of survivors at the beginning of a loop is even, the lowest numbered position survives and the highest numbered position is dismissed at the end of the loop. If the total number of survivors at the beginning of a loop is odd, the highest numbered position survives and the lowest numbered position is dismissed at the end of the loop.
Algorithm: Let $... b_3 b_2 b_1 b_0$ be the binary representation of the number of people initially in the circle, $N$. I.e., $N = \sum_k b_k 2^k$. We construct a table, a sequence of tuples, iteratively according to the following prescription:
(loop, N shifted down by loop bits, gap, first survivor, last survivor)
The first tuple is
(0, N, 1, 1, N)
As long as the second entry is $> 1$, we construct the next tuple as follows:
If the least significant bit of $N$ shifted down by loop is $0$,
(loop+1, N shifted down by loop+1 bits, 2 gap, first survivor, last survivor - gap)
otherwise
(loop+1, N shifted down by loop+1 bits, 2 gap, first survivor + 2 gap, last survivor)
For the example of $n = 100 = 1100100_2$, (using "->" to mean "dismisses")
(0, 1100100, 1, 1, 100)
1 -> 2, 3 -> 4, ..., 99 -> 100
(1, 110010, 2, 1, 99)
1 -> 3, 5 -> 9, ..., 97 -> 99
(2, 11001, 4, 1, 97)
1 -> 5, 9 -> 13, ..., 89 -> 93, odd: 97 -> 1
(3, 1100, 8, 9, 97)
9 -> 17, 25 -> 33, ..., 89 -> 97
(4, 110, 16, 9, 89)
9 -> 25, 41 -> 57, ..., 73 -> 89
(5, 11, 32, 9, 73)
9 -> 41, odd: 73 -> 9
(6, 1, 64, 73, 73)
It is, in fact, clearer what's going on if we write the firsts and lasts in binary and keep track of how many of the least significant bits of first and last are being required equal in all the survivors (enforced by the gap, which is always a power of $2$).
(0, 1100100, 1, 1, 1100100)
(1, 110010, 2, 1, 110001 1)
(2, 11001, 4, 01, 11000 01)
(3, 1100, 8, 1 001, 1100 001)
(4, 110, 16, 1001, 101 1001)
(5, 11, 32, 01001, 10 01001)
(6, 1, 64, 1 001001, 1 001001)
Repeating with $N=63$:
(0, 111111, 1, 1, 111111)
1 -> 2, 3 -> 4, ..., 61 -> 62, odd: 63 -> 1
(1, 11111, 2, 1 1, 11111 1)
3 -> 5, 7 -> 9, ..., 59 -> 61, odd: 63 -> 3
(2, 1111, 4, 1 11, 1111 11)
7 -> 11, 15 -> 19, ..., 55 -> 59, odd: 63 -> 7
(3, 111, 8, 1 111, 111 111)
15 -> 23, 31 -> 39, ..., 47 -> 55, odd: 63 -> 15
(4, 11, 16, 1 1111, 11 1111)
31 -> 47, odd: 63 -> 31
(5, 1, 32, 1 11111, 1 11111)
But from this it's easy enough to see what the sequence of bits in the firsts is. It's the sequence of bits in $N$ with the most significant deleted and a trailing $1$ appended. I.e., $100 = 1100100_2 \rightarrow 1001001_2 = 73$. This is shown as: Initially, first = 1. A $0$ bit is prepended to first when the least significant bit of $N$ shifted down by loop bits is $0$. Alternatively, a $1$ bit is prepended to first when the least significant bit of $N$ shifted down by loop bits is $1$. Finally, no bit is prepended to first corresponding to the most significant bit of $N$ since the sequence of tuples stops when that is the only surviving bit in the second position of the tuple. (This is because there is only one survivor in the circle and it is both the first and the last in the final tuple.)
So a table of $N$ and survivors:
N -> survivor number
99 = 1100011_2 -> 1000111_2 = 71
100 = 1100100_2 -> 1001001_2 = 73
101 = 1100101_2 -> 1001011_2 = 75
102 = 1100110_2 -> 1001101_2 = 77
...
127 = 1111111_2 -> 1111111_2 = 127
128 = 10000000_2 -> 00000001_2 = 1
129 = 10000001_2 -> 00000011_2 = 3
If one wants a formula, the shift up by a bit and append $1$ are easy ($2x+1$), but the drop the leading bit is hard. One way to go is $$ 2(N - 2^{\lfloor \log_2 N \rfloor})+1 $$
We have that $x \; \mathrm{O} \; y=z$ for $x=(x_1 , \ldots , x_{100})$ and $y=(y_1 , \ldots , y_{50})$ is such that $z=(z_1 , \ldots , z_{50})$ where $z_i$, $i \in [1,50]$ satisfies the condition that $z_i \neq y_i \, \forall i$.
As Eric Towers mentions, this is analogous to the set difference:
$$A -B = \{x \in A : x \notin B\}$$
However, here we have the property of ordering, as you correctly point out. This matters rather little, though, for we must simply ensure that $x_{n_1}=z_{n_2}$ and $x_{m_1}=z_{m_2}$ is such that $n_2 < m_2$ if and only if $n_1 < m_1$.
So, this operation is well defined. Give me two $n$-tuples, $x$ and $y$ where the number of elements of $x$ is greater than or equal to that of $y$, and I can uniquely determine $x\; \mathrm{O} \;y$.
Whether or not this is particularly interesting is up to you. In my opinion, it is no more interesting than the set-theoretical difference; however, it does help to emphasize that an $n$-tuple is distinct from a set, which is, in general, not even ordered.
I am certain this operation is known, but it is not very noteworthy.
As far as I know, it has not really been studied extensively. I am also not aware of any name for this operation. Might I suggest "$n$-tuple subtraction", or "tuple subtraction" for short?
That may be somewhat confusing, though, as it seems to imply that there are two $n$-tuples involved where you subtract the $j$th element of the first tuple from the $j$th element of the second.
(I'm pretty tired. So, I apologize if I have made a mistake. Please, let me know if that is the case.)
