## Binary Concatenation

### July 14, 2020

We have an interview question today:

The concatenation of the first four integers, written in binary, is 11011100; that is, 1 followed by 10 followed by 11 followed by 100. That concatenated number resolves to 220. A similar process can convert the concatenation of the first

nbinary numbers to a normal decimal number.

Your task is to compute the *n*th binary concatenation in the manner described above; report the result modulo 10^{9}+7, because the result grows so quickly. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here are two solutions in Python, the first relying on string concatenation and the standard library’s binary/decimal conversion functions, and the second using @programmingpraxis’ numerical approach.

Output:

My first post here! I did this in C.

Code:

Output:

@Antonio: nice solutiion, but you have to take the modulus each time around the loop rather than just at the end, to avoid overflow with intermediate values.

A nice way of avoiding all those divisions is to use Montgomery multiplication, https://en.wikipedia.org/wiki/Montgomery_modular_multiplication:

@matthew I believe we just interpreted the problem differently. I read it as, find the result, “whatever that may be,” then finally report it modulo 10^9+7. Thus I am doing “raw” binary concatenation then only taking the modulus once I have my final number. Perhaps my interpretation is wrong, though, in a “common sense” kind of way.

Montgomery multiplication is going a bit over my head at the moment. Seems like the kind of thing I enjoy learning about, nonetheless, so thank you for sharing. :-)

@Antonio, I believe that @matthew’s comment does not arise from a different interpretation, but is rather a suggestion that the modulus operation can be applied more frequently to get the desired answer for large

`n`

by preventing overflow, since`(A + B) mod C = (A mod C + B mod C) mod C`

and`(A * B) mod C = (A mod C * B mod C) mod C`

. For the bit shifting, the latter equation would apply since the operation is equivalent to multiplying by 2.Here’s an example in C, followed by usage with a large

`n`

(much larger than would be required for overflow without the intermediate modulus operations).Example usage:

@Antonio, the same idea applies to your solution by adding a modulus operation to lines 23 and 26, with the

bitwise orchanged to an addition.