## Concatenate N N Times

### May 10, 2016

One solution is to treat the number as a string, replicate the characters then convert to a number:

(define (f n) (undigits (flatten (iterate n append (digits n)))))

> (f 12) 121212121212121212121212

That looks simple but is actually fairly complicated, requiring several functions from the Standard Prelude.

Concatenated numbers form one of the Smarandache sequences, and are given by the formula , where *D*(*n*) is the number of digits in *n*:

(define (d n) ; number of digits in n (let loop ((n n) (k 0)) (if (zero? n) k (loop (quotient n 10) (+ k 1)))))

(define (f n) ; concatenate n n times (quotient (* n (- (expt 10 (* n (d n))) 1)) (- (expt 10 (d n)) 1)))

> (d 12) 2 > (f 12) 121212121212121212121212

That’s both simpler and faster than the string solution. You can run the program at http://ideone.com/kwRLZi. Besides the *MathWorld* page referenced above, this exercise is also discussed at A000461.

Tried this in perl – as perl has the built in operator… the concatenation is about 40% faster then the numeric method – and works for larger values of n….

Simple iterative solution O(n):

Notice that it performs n multiplications and n additions that quickly enough are bignum operations.

This is typically an operation that can be reduced to O(logn), by noticing that when n is even:

and when n is odd:

Therefore we can write:

I doubt James tested his perl string version on non-single digit numbers; going thru strings is 6 times slower than the iterative arithmetic solution, and 1000 times slower than the dichotomy arithmetic solution:

I meant the factors for 1234.

Converting the number to a string is O(logn) divisions; concatenating the strings can be made O(n^2) memory accesses (the length of the string is n*n=n^2); reading the result is O(n^2) multiplications+additions. Total, the string version is O(n^2) multiplications, while the simple iterative is only O(n) multiplication and the dichotomic one is O(logn) multiplications.

Here’s a couple of Python solutions, one short and snappy using strings, one using bignum arithmetic. The string solution is faster for smaller n, but with bignums winning for larger (>200) n – by n = 100000, bignums are 15 times faster, probably converting megabyte strings to ints doesn’t scale well.

Here’s a solution in Java that iteratively reads an additional character until the parsed integer times its string length equals the length of the entire string. I assumed inputs are valid (e.g., 333 is valid, 332 is not but my program would also return 3 for that). At return time, I could check for validity but didn’t bother.

Output:

Output:

> “Your task is to write a program that calculates the number that is concatenated to itself the number of times as the number is (that’s hard to say).”

I just looked at the solution and skimmed some other solutions. I think I interpreted the task slightly differently than others. It seems like the typical interpretation is that the input is N, and the output is N concatenated N times. I thought the input was N concatenated N times, and the output was N. I re-read the task and think it can be interpreted either way (its ambiguous, like many natural language sentences).

Building the output in an array of chars is wicked fast. The following – in c# – completes in 1 millisecond with n = 100000:

A math solution requires approximately 40000 milliseconds for the same n = 100000:

I have two solutions both using python and does substring comparison although numeric comparisons are cool.

First version is kind of greedy approach

Second version uses indexes to compare substrings – it resembles to dynamic programming solutions.

Performance comparison, measured by ipython’s timeit builtin function.

First version seems to do better at first glance

But i suspected that second version would do better when repeated substring becomes much larger, and it indeed did perform better