Divisibility of a binary number by N?

Question

Mathematics

I came across this problem:
It is known that a binary number consists of A units and B zeros.
Is it safe to say that some binary number composed of these numbers is divisible by N without a remainder?
For example, 7 ones and 2 zeros, is it divisible by 25? You can make the number 101110111 (375), it is divisible by 25.
As a solution, I see a search of all possible options and a divisibility check, but I do not fit into the time limit. Tell me, what other options are possible? Some universal divisibility criterion for binary numbers? Or is it just an option to sit down for the Sign of Pascal?

Answer 1

Dynamic Programming:
F(a,b,r) = can a number made up of a ones and b zeros give a remainder r when divided by N.
Base: F(0,0,0) = true, F(0,0,r ) = false.
Recalculation: Iterative recalculation is like this - F(a,b,r) => then F(a+1,b,(2*r+1) % N) and F(a,b+1,(2*r+1 ) % N) Here we know that there is a number that gives the remainder r of a ones and b zeros. If we add 1 to it at the end, then the remainder will be (2 * r + 1)% N, and there will be one more units. You can also almost assign 0.
For recursive, you must first get rid of all powers of 2 in N (just count the power, subtract it from B, divide N by all twos - There must be so many zeros at the end of the number).
Now you can find x such that 2x = 1 (mod N) is the reciprocal of 2 mod N. See Extended Euclid's Algorithm for this.
Then you can calculate like this (N is odd):
F(a,b,r) = F(a-1,b, (r-1)*x % N) || F(a, b-1, r*x % N).
The explanation here is also simple - the number either ends in 0 or 1. Let's try both options and erase the last digit. The remaining number should give the remainder (r-1)*x % N or r*x % N respectively.
Answer: If F(A,B,0) - true, then there is a number divisible by N. To find the number, you must additionally remember which numbers were assigned to the numbers in the calculations above.

Answer 2

Max number for A+B bits = C = 2^(A+B) - 2^B , i.e. for 9 bits it is 2^9-2^2 = 512-4 = 508
You need to find all numbers from N to C inclusive, which are divisible by N without a remainder (in fact, they are the product of N by the cycle index from 1 to (C div N) inclusive), and check if they are sums of non-repeating powers of two, and if they are, then whether the number of numbers in the sum equals the value of A . Those. check if all A bits are enabled.
For this case, at N = 25 , 508 div 25 = 20(iterations). It is necessary to check whether the product of the cycle index by N is the sum of A (7) numbers (not repeating powers of two from 0 to A + B-1 (8)).
Numbers (powers of two) can be pre-calculated and added to an array, and taken from there by index.
So the hardest thing to write is a function that will check if its argument is the sum of A non-repeating powers of 2 from 0 to A+B-1 .
You do not need to check everything, you can interrupt the execution on the first positive result.
You can quickly check for a power of two through the bit comparison operation AND
For example K = 13 (8+4+1), then K & 1 = 1, K & 2 = 0, K & 4 ​​= 4, K & 8 = 8. I.e. it is obvious that if K & 2^i > 0, then the number contains a power of two. Well, it remains to count for each number how many powers of two it contains.
Again, it is necessary to check not with all powers of two, but with the nearest smaller one from K, i.e. for K=28, the maximum power of two for comparison will be 16. For K=50 - 32, for K=100 - 64, etc.
It will be necessary to somehow calculate this degree, best of all lazily. Just by calculating the next K, check if it is greater than the next power of two.
https://codedump.io/share/hMw9j5suUF41/1/doesbinar... here is a fluent solution on JS
PS: the solution needs optimization, but it's already on its own :)

Answer 3

If we swap some 0 and 1 places, then if the criterion exists, the divisor should not change.
Such N must divide any continuous sequence of ones, including one. That is, nothing can be said.