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.

Posted by programmingpraxis

Filed in Exercises

7 Comments »

7 Responses to “Binary Concatenation”

Daniel said

July 14, 2020 at 7:53 PM

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

Antonio said

July 14, 2020 at 8:42 PM

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

matthew said

July 20, 2020 at 8:24 AM

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

Antonio Leonti said
July 22, 2020 at 11:45 PM
@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. :-)
Daniel said
August 4, 2020 at 2:02 AM
“@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[1]);
  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
```
Daniel said
August 4, 2020 at 2:16 AM
@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;
}
```

Hakan said

August 11, 2020 at 10:34 PM

<?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);
}


?>

Programming Praxis