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.
Programming Praxis 
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:
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:
@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]@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
nby preventing overflow, since(A + B) mod C = (A mod C + B mod C) mod Cand(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:
@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; }<?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); } ?>