Deduce patterns of divisibility in bit strings

52 Views Asked by At

This is partially a computer science question, but belongs here as well.

The question has to do with the bit representation of integers. For simplicity, assume only non-negative integers. Can we find a general pattern for multiples of a positive integer in its bit representation?

That is, given $n \in \mathbb{N}$, define $S = \{s \mid s = kn, \space k \in \mathbb{N}\}$, the set of multiples of n. Represent $S$ in binary, call it $B$. Can we find a general pattern/function for $B$ that exhaustively test every element of a set and see if it equals to $B$? If so, is there an algorithm for finding the pattern/function?