1
$\begingroup$

Suppose we're given an infinite stream of integers, $x_1, x_2, \dots$.

a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log N)$ bits of memory.

b) Let $N$ be an arbitrary number, and suppose we're given $N$'s prime factorization: $N = p_1 ^{k_1} p_2 ^{k_2} \dots p_r ^{k_r}$. How would you check whether $N$ divides the product of all integers $x_i$ seen so far, using as few bits of memory as possible? Write down the number of bits used in terms of $k_1, ..., k_r$.

For part a), we know that for any prime $p \ne 2, 5$, there is an integer $r$ such that in order to see if $p$ divides a decimal number $n$, we break $n$ into $r$-tuples of decimal digits, add up these $r$-tuples, and check if the sum is divisible by $p$. But $N$ is a fixed integer, and not necessarily a prime. Is there some way to connect the theorem above to any arbitrary integer?

For part b), for the product of $x_i$ (call it $y$) is divisible by $N$, then $y$ must be divisible by each $p_i ^{k_i}$ (call it $a_i$. Since we're given the prime factorization, we can just check if $y$ is divisible by $N$ by dividing $y$ by each $a_i$ and halting when it fails, right? Would this result in using $k_1 \times \dots \times k_r$ bits?

Am I at least on the right track, or am I completely wrong? Any help understanding this problem would be tremendously helpful.

$\endgroup$
  • 1
    $\begingroup$ Please credit the original source in the question. Whenever you quote from another source, you are supposed to provide proper attribution. That helps people answer your question as well. $\endgroup$ – Apass.Jack Nov 19 '18 at 0:18
  • $\begingroup$ There's nothing special about the primes $2,5$. The integers are not given as decimals, they're given as bits. $\endgroup$ – Yuval Filmus Nov 19 '18 at 1:15
1
$\begingroup$

For part (a), the idea is that it suffices to store the sum of all integers seen so far modulo $N$. Since this is an integer between $0$ and $N-1$, storing it requires only $\lceil \log_2 N \rceil$ bits.

For part (b), let $x_i = p_1^{a_1(i)} \cdots p_r^{a_r(i)} q$, where $q$ is relatively prime to $p_1,\ldots,p_r$. Then $x_1 \cdots x_m$ is divisible by $N$ iff $a_j(1) + \cdots + a_j(m)\geq k_j$ for $j=1,\ldots,r$. Hence it suffices to store $\min(a_j(1)+\cdots+a_j(m),k_j)$ for $j=1,\ldots,r$. The $j$th number is between $0$ to $k_j+1$, and so requires $\lceil \log_2 (k_j+1) \rceil$ bits, for a total of $$ \sum_{j=1}^r \lceil \log_2(k_j+1) \rceil \text{ bits}. $$ (In fact, we can be a little bit smarter and use only $\left\lceil \sum_{j=1}^r \log_2(k_j+1)\right\rceil$ bits, but it's not such a big difference.)

In both cases, it is possible to show that the amount of bits stated is also required. For example, in part (a), at any given point in time you need to distinguish between $N$ different states, correspond to the current sum modulo $N$. Indeed, all sequences $0;1;\cdots;N-1$ must lead to different memory states, since if $i$ and $j$ led to the same state, then we would not be able to distinguish between the sequences $i,N-i$ and $j,N-i$, although one of them satisfies the divisibility property and the other doesn't.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.