Timeline for powers in strings
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 13, 2014 at 6:32 | answer | added | Bjørn Kjos-Hanssen | timeline score: 6 | |
| Mar 13, 2014 at 5:05 | answer | added | Jan Kyncl | timeline score: 7 | |
| Mar 13, 2014 at 5:05 | answer | added | The Masked Avenger | timeline score: 2 | |
| Mar 13, 2014 at 4:49 | comment | added | Anthony Quas | Presumably for random strings, the powers you are most likely to see are repetitions of short words. If you want a 17 repetition, it's much easier to see 1^17 rather than (001)^{17}. Of course there are more possible blocks to repeat of length 3, but this doesn't come close to compensating for how hard it is to see a repetition of each one. Hence the expected maximum repetition length should be of length roughly k where n^{k-1}=N. | |
| Mar 13, 2014 at 3:49 | comment | added | Jan Kyncl | For question 2, there is a straightforward $O(N^3)$-time algorithm: for each of the ${N \choose 2}$ substrings $T$, check whether the following $|T|^{k-1}$ letters form the string $T^{k-1}$. | |
| Mar 13, 2014 at 3:10 | comment | added | Igor Rivin | @ARupinski (and Jan Kyncl) Thanks! This leaves the second and third questions :) | |
| Mar 13, 2014 at 3:06 | comment | added | Jan Kyncl | continuing ARupinski's comment: Since there exist arbitrarily long square-free words over ternary alphabet (en.wikipedia.org/wiki/Square-free_word), then $P(n,N)=1$ for every $n\ge 3$. | |
| Mar 13, 2014 at 2:05 | comment | added | Fei Gao | @IgorRivin Sorry, I misunderstood $S_i$ for single char. | |
| Mar 13, 2014 at 2:03 | comment | added | ARupinski | If I understand your definition of $P(n,N)$ then since there exist infinite cubefree words over a binary alphabet (see for example the Thue-Morse sequence), one should have $P(2,N) = 2$ when $N\geq 4$. And since the Thue-Morse sequence could be viewed as a word over any $n$-ary alphabet but only using 2 symbols, shouldn't this mean $P(n,N)\leq 2 \forall n\geq 2,N$? Or did I misread what you are asking? | |
| Mar 13, 2014 at 2:01 | history | edited | Igor Rivin | CC BY-SA 3.0 |
fixed typesetting
|
| Mar 13, 2014 at 1:59 | comment | added | Igor Rivin | @FeiGao Linear Scan? How do you detect powers, and where do you store them? | |
| Mar 13, 2014 at 1:58 | comment | added | Igor Rivin | @FeiGao 1. No. Suppose $n=2,$ for simplicity, with $A=\{a, b\}.$ Then if the string contains no square, then it contains no $aa$ or $bb,$ so must have the form (wlog) $S=ababab\dots,$ which means that it contains a very high power of $ab.$ | |
| Mar 13, 2014 at 1:50 | comment | added | Fei Gao | 1. Would $P(n,N)=1$ for all $n>1$, if you say every string. 2. Can do it through a linear scan, so $O(N)$. | |
| Mar 13, 2014 at 1:41 | history | asked | Igor Rivin | CC BY-SA 3.0 |