Count the number of binary string of length n that repeats

Question

The challenge is to find the number of duplicate binary strings of length n. A binary string is repeated if it can be obtained by any substring of a binary string that is repeated to form the original binary string.

Example "1010" is a repeatable string as it can be obtained from "10" by repeating 2 number of times "1001" is not a repeatable string as it cannot be obtained from any sub string of "1001" by repeating them any number of times 

The solution I was thinking about is to generate all possible binary string of length n and check if it is repeatable or not using the KMP algorithm, but this solution is impossible even for small n such as n = 40.

The second approach that I thought

• for the divisor k of n will find all substrings of length k that repeat themselves n / k times

Example for n = 6 has a divisor 1,2,3

for length 1 we have 2 substrings "1" and "0" that are repeated 6 times so "111111" and "000000" are repeatable strings

for length 2 we have 4 substrings "00" "01" "10" "11", so "000000" "010101" "101010" and "111111" are repeatable strings

similarly for length 3 we have 8 lines that are repeatable.

2. Count all lines generated by the divider and subtract duplicates.

In the above example, the line "111111" and "000000" was counted 3 times for each of the dividers. Obviously I'm re-reading. I need to subtract duplicates, but I can’t think of subtracting duplicates from my actual account. How can I do this?

Am I heading in the right direction or do I need some other approach?

Answer 1

When you use the second scheme, remove the substrings that are made from duplicate binaries. For example, 00 and 11 are made from repeating 0 and 1, respectively. Thus, for length 2, we consider only "01" and "10", for length 3, only "001", "010", "011", "100", "101", "110", ... are taken into account ... in general , for odd length n, delete 0 and (2 ^ n) -1, for even length n, delete 0, (2 ^ (n / 2) +1), (2 ^ (n / 2) +1) 2 ,. .., (2 ^ n) -1 and if n is divisible by 3, (1 + 2 ^ (n / 2) + 2 ^ (n-2)), (1 + 2 ^ (n / 2) + 2 ^ (n-2)) 2, .., continue this for all delimiters.

Answer 2

One idea is that if we only count ways to make lines with sizes of divisors from non-repeated substrings, counts from divisors of divisors will consider ways to make dividers from repeating substrings.

 f(1) = 0 f(n) = sum(2^d - f(d)), where 1 <= d < n and d divides n 

... means the sum of only the paths along which the divisors of n can be made of non-repeating substrings.

 f(2) = 2^1-0 f(3) = 2^1-0 f(4) = 2^1-0 + 2^2-2 f(6) = 2^1-0 + 2^2-2 + 2^3-2 ...