Sum of product with primes

350 Views Asked by At

Let $b=e_1e_2,\ldots,e_n$ and $b'=e'_1e'_2,\ldots,e'_n$ be two distinct bit strings of equal length $n$ with same number of occurrences of zeros and ones. The bit string $b$ and $b'$ also must have $e_1 \neq e'_1$ and $e_n \neq e'_n$, that is, first and last bits must be distinct.

Examples of such pairs of bit strings:

100 and 001 --> bits in positions 1 and 3 mismatch, # of zeros is 2 and # of ones is 1

0101 and 1100 --> mismatch in positions 1 and 4, freq(0)=2 and freq(1)=2

0101 and 1010 --> all positions mismatch, freq(0)=2 and freq(1)=2

0100101 and 1110000 --> mismatch in positions 1, 3, 5 and 7, freq(0)=4 and freq(1)=3

Not that the number of positions with bit mismatches must be even.

Now let $p_0 p_1, q_0$ and $q_1$ be four distinct primes. For any pair of bit strings define:

$$S_b=\sum_{i=1}^n \left( q_{e_i} \prod_{j=i+1}^n p_{e_j}\right) \mbox{ and } \ S_b'=\sum_{i=1}^n \left( q_{e'_i} \prod_{j=i+1}^n p_{e'_j}\right)$$

Example: if $b$=100 and $b'$=001 then $S_b=q_1 p_0 p_0 + q_0 p_0 + q_0$ and $S_{b'}=q_0 p_0 p_1 + q_0 p_1 + q_1$.

Can $S_b=S_{b'}$ for $b\neq b'$ as above? If so, is there any condition that can be made on the primes $p_0, p_1, q_0$ and $q_1$ so that $S_b \neq S_{b'}$?


EDIT: let $p_0$ and $p_1$ be distinct primes, and let $q_0$ and $q_1$ be distinct positive integers. The product and type of bit strings are still the same as above.

1

There are 1 best solutions below

0
On BEST ANSWER

The answer to "can $S_b=S_{b'}$ for $b \neq b'$" is in the affirmative. This is checked fairly quickly by brute force. Let $b=100$ and $b'=001$ (as in your example). Then set $p_0=7$, $p_1=5$, $q_0=3$ and $q_1=2$. Now, \begin{equation} S_b=q_1 p_0 p_0 + q_0 p_0 + q_0=2 \cdot 7 \cdot 7 + 3 \cdot 7+3=122 \\ S_{b'}=q_0 p_0 p_1 + q_0 p_1 + q_1=3 \cdot 7 \cdot 5+3 \cdot5 + 2 = 122 \end{equation} In fact, for the given $b$ and $b'$ these primes are not unique in satisfying your criteria. I do not have an answer to the second part of your question.

Edit: Consider the $4$-tuple $(p_0,p_1,q_0,q_1)$, then here is a large list of the $4$-tuples that satisfy $S_{100}=S_{001}$. As you can see, there are many possibilities. I hope this list can serve in answering the second part of your question.
$(7,5,3,2)$
$(19,13,3,2)$
$(23,5,11,2)$
$(31,13,5,2)$
$(41,17,5,2)$
$(43,29,3,2)$
$(42,13,7,2)$
$(47,5,23,2)$
$(59,5,29,2)$
$(61,41,3,2)$
$(67,13,11,2)$
$(61,41,3,2)$
$(79,53,3,2)$
$(83,5,41,2)$
$(5,7,2,3)$
$(11,7,5,3)$
et cetera