Aperiodic Binary Strings

Note that there are $2^{23} = 8388608$ binary strings of length $23$ . We will count the number of periodic binary strings of length $23$ and subtract from this number.

If a string of length $n$ is periodic with a string of length $m$ as its building block (the one that is repeated several times), then $m|n$ . Since the only proper divisor of $23$ is $1$ , the only periodic binary strings of length $23$ are those whose building block is a binary string of length $1$ . There are only two binary strings of length $1$ ( $0$ and $1$ ), so the only periodic binary strings of length $23$ are $000\ldots 0$ and $111\ldots 1$ . There are $8388608 - 2 = \boxed{8388606}$ strings remaining, which are necessarily aperiodic.

Tip to OP: If you want to force a program to compute it, put some massive, composite number, like $23!^{23}$ , instead of a simple prime number.

Our first clue is that there are at-most $2^n$ strings of length $n$ .

Now, notice two more things.

Every periodic string of length $n$ has been made up by repetition of strings of lengths that divide $n$ . However, we should only count the aperiodic smaller strings because the periodic strings already consist of them.

This will be clear in the program.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

periodic :: Integer -> Integer
aperiodic :: Integer -> Integer

aperiodic 1 = 2
aperiodic n = 2^n - (periodic n)

periodic 1 = 0
periodic n = sum $ map aperiodic [i | i<-[1..n-1], n `mod` i == 0]

main = putStrLn $ show (aperiodic 23)