## 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.

Pages: 1 2

### 7 Responses to “Binary Concatenation”

1. Daniel said

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.

```def bconcat1(n):
return int(''.join(bin(x)[2:] for x in range(1, n + 1)), 2) % (10 ** 9 + 7)

def bconcat2(n):
s, p, d = 0, 1, 10 ** 9 + 7
for i in range(1, n + 1):
p <<= i == p
s = ((s * p) + i) % d
return s

for x in range(1, 10):
print(f'{x} {bconcat1(x)} {bconcat2(x)}')
```

Output:

```1 1 1
2 6 6
3 27 27
4 220 220
5 1765 1765
6 14126 14126
7 113015 113015
8 1808248 1808248
9 28931977 28931977
```
2. Antonio said

My first post here! I did this in C.

Code:

```#include <stdio.h>
#include <conio.h>
#include <math.h>

int solve(int a){
int ret;
//starting at 0, concatenate each int to the end of ret up to a
for(int i = ret = 0; i <= a; i++) ret = bitcat(ret, i);

return ret % (int)(pow(10, 9) + 7);
}

int main(){
// test numbers 0 - 10
for(int i = 0; i < 10; i++){
printf("%d -> %d\n", i, solve(i));
}
getch(); return 0;
}

int bitcat(int a, int b){
// make room for b at the end of a
for(int i = b; i; i >>= 1) a <<= 1;

// add b to the end
return a | b;
}
```

Output:

```0 -> 0
1 -> 1
2 -> 6
3 -> 27
4 -> 220
5 -> 1765
6 -> 14126
7 -> 113015
8 -> 1808248
9 -> 28931977
```
3. matthew said

@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:

```# Extended Euclidean algorithm
def egcd (a,b):
a0 = a; b0 = b
x,y,z,w = 1,0,0,1
while b != 0:
q,r = divmod(a,b)
a,b =  b,r
x,y,z,w = z,w,x-q*z,y-q*w
return a,x,y

N = 10**9+7
R = 1<<N.bit_length()
(d,R0,N0) = egcd(R,N)
R0 = R0%N
N0 = (-N0)%R
assert(R*R0-N0*N == 1)

def convert(a): return a*R%N
def unconvert(a): return a*R0%N

def mmult(a,b):
T = a*b
m = T%R*N0%R
t = (T + m*N)//R
if (t >= N): t -= N;
return t

def concat(n):
a = 0 # Accumulate result in a
l,x = 0,R%N # Current bit length & converted multiplication factor
k = R%N # convert(i)
for i in range(1,n+1):
if i.bit_length() != l:
l += 1
x += x
if x >= N: x -= N
assert(x == convert(2**i.bit_length()))
assert(k == convert(i))
a = mmult(a,x)
a += k
if a >= N: a -= N
k += R%N
if k >= N: k -= N
return unconvert(a)

print([concat(i) for i in range(16)])
# [0, 1, 6, 27, 220, 1765, 14126, 113015, 1808248, 28931977, 462911642,
#  406586234, 505379714, 86075381, 377206103, 35297621]
```
4. Antonio Leonti said

@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. :-)

5. Daniel said

“@matthew I believe we just interpreted the problem differently.”
-@Antonio

@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).

```#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define DIVISOR 1000000007

int main(int argc, char* argv[]) {
assert(argc == 2);
int n = atoi(argv);
assert(n >= 0);
int result = 0;
for (int i = 1; i <= n; ++i) {
for (int j = i; j; j >>= 1) {
result = (result << 1) % DIVISOR;
}
result = (result + i) % DIVISOR;
}
printf("%d\n", result);
return EXIT_SUCCESS;
}
```

Example usage:

```\$ ./a.out 16777216
602314637
```
6. Daniel said

@Antonio, the same idea applies to your solution by adding a modulus operation to lines 23 and 26, with the bitwise or changed to an addition.

```int bitcat(int a, int b){
for(int i = b; i; i >>= 1) a = (a << 1) % 1000000007;
return (a + b) % 1000000007;
}
```
7. Hakan said
```<?php

function concatenateBinaryNumbers(\$n){
// Prepare an array with integers from 1 to n
\$m = 1;
do {
\$array[] = \$m;
\$m += 1;
} while (\$m <= \$n);

// Prepare a string
\$concatenated = '';

// Loop through the array
foreach (\$array as \$number) {
// Convert each integer to a binary string and concatenate it to the prepared string
\$concatenated .= decbin(\$number);
}

// Convert the concatenated string back to decimal format
\$number = bindec(\$concatenated);
\$number_modulated = \$number % ((10 ** 9) + 7);

echo \$n.'. '.\$number.' mod 10^9 + 7 = '.\$number_modulated.'<br>';

}

for (\$i=1; \$i < 16; \$i++) {
concatenateBinaryNumbers(\$i);
}

?>
```