Prime words

A given word w is called “prime” if it cannot be written in the form of the concatenation of several copies of some shorter word. So, for example the words ‘100′, ‘1100′, and ‘001100′ are prime, while the words ‘0101′, ‘100100′, ‘1111′, and ‘101010′ are not prime.
How will you calculate the number of prime words which can be built from exactly a ones and b zeros?
What if you have to display them?

For Information on Common wealth Games See Here!

http://common-wealth-games-2010.blogspot.com/

Answer1:
one possible solution can be like this:
find the common factor of a and b.suppose they are p,q ,r,…. and 1
then the number of prime words which can be formed from them are
permutation of (a/p + b/p) where a/p are alike and b/p alike + permutation of (a/q + b/q) where a/q are alike and b/q alike + permutation of (a/r + b/r) where a/r are alike and b/r alike …..excluding the 1 term.

Answer2:
Will 10101 be a prime word??

If not, then, I suppose, the only prime words of odd length would be those that have all 1s or all 0s !!

Answer3:
To count the number of words that are prime…

assume a>b for division.. if b is greater than a, we can swap the value.

a = number of 1’s
b = number of 0’s

if(a%b==0) shorter pattern possible.
repeat zero after (a/b) 1’s

example..

a=4
b=2

so only prime word possible would be
110110 //this we have generated..

101101
011011

Translate all the zero bit by 1 bit position. this can be done by swapping the adjacent bit.

Now i hope you can calculate how many total numbers that are not prime for a N 1bit and M 0 bit.
subtract this count from total count of numbers that can be generated.
i.e 4!*2!.

To display you can check whether its prime or not.!!
Check whether all the zero have separation of (a/b) bits.

Which is Correct?