## Binary Concatenation

### July 14, 2020

This isn’t hard:

(define (f n) (let loop ((i 1) (s 0) (p 1)) (when (= i p) (set! p (+ p p))) (if (< n i) s (loop (+ i 1) (modulo (+ (* s p) i) 1000000007) p))))

Here are some examples:

> (f 4) 220 > (f 10) 462911642

You can run the program at https://ideone.com/fPiIxa. You might also look at A047778.

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.