a^*b^*c^* – {a^n b^n c^n | n ≥ 0} is not regular using pumping lemma

$ L=a^*b^*c^* \setminus \{a^n b^n c^n \mid n \geq 0\}$ can be proved as context-free by partitioning it as $ L = \{a^nb^mc^* \mid n \neq m\} \cup \{a^*b^nc^m \mid n \neq m\}$ and further dividing each $ \neq$ into smaller and larger. You will have four sets. You can give CFG’s for each. Then since CFGs are closed under union, you have your proof.

Now how can I go around proving that $ L$ is not regular? If you prove that the each of these four sets are not regular, you still can not prove that the union is not regular, can you?

Decide whether two strings $x, y$ can be split into substrings $a,b,c$ such that $x=abc$ and $y=cba$

What is the fastest algorithm for the following problem?

Given two strings $ x, y \in \Sigma^*$ as input, decide whether there exists strings $ a, b, c \in \Sigma^*$ , such that $ x=abc$ and $ y=cba$ .

By calculating all the length of the longest common prefix of $ s = x$ y$ and all suffixes of $ s$ , we can compute all candidates for $ a$ in $ O(n)$ time.

For each candidate of $ a$ with length $ k$ , we now just need to check whether $ x_k, x_{k + 1}, \ldots, x_{n}$ is a rotation of $ y_0, y_1, \ldots, y_{n – k}$ . This can of course be done in $ O(n)$ .

However checking the rotations naively results in a worst-case $ O(n^2)$ algorithm.

It seems that using the result from either https://arxiv.org/pdf/1601.08051.pdf or https://arxiv.org/pdf/1311.6235.pdf would make the algorithm run in expected $ O(n)$ time.

Is there a simpler way of speeding up the rotation checking, where it is still faster than $ O(n^2)$ ? Is there a way of making it deterministic, so that it still runs in $ O(n)$ time?

Check which numbers satisfy the condition [A*B*C = A! + B! + C!]

#include <iostream> #include <cmath> using namespace std; int s = 1; //Serial No. 

Should I use recursion for the factorials function?

int Factorial(int n) {     int k=1;     for(int i=1;i<=n;++i)     {         k=k*i;     }     return k; } 

How I can go about doing this in a single for loop instead of the 3 while loops?

int main() {     int a = 1;     int b = 1;     int c = 1;     int Fact1;     int Fact2;     int Fact3;     while (a < 11)     {         Fact1 = Factorial(a);         while (b < 11)         {             Fact2 = Factorial(b);             while (c < 11)             {                 Fact3 = Factorial(c);                 cout << s << " : ";                 int LHS = Fact1 + Fact2 + Fact3;                 if (LHS == a * b * c)                 {                     cout << "Pass:" <<"    "<< a << " & " << b << " & " << c << endl;                 }                 else                 {                     cout << "Fail" /*<<"   "<< Fact1 <<"   "<< Fact2 <<"   "<<Fact3*/<<endl;                 }                     c++;                     s++;             }             c = 1;             b++;         }         b = 1;         a++;     }     return 0; } 

Also I would love some variable naming tips.

Algebraic inequality for positive reals $a,b,c$

The problem is from a previous maths olympiad and the last step is to prove the inequality

$ $ 4a^4bc + a^4c + 9a^3bc^2 + a^2b^4 + 9ab^2c^3 + 4ab^4c + 4b^3c^3 + b^2c^4 +4abc^4 \geq 24a^2b^2c^2 + 10a^3b^2c + 10a^2bc^3 + 10ab^3c^2$ $ for all $ a,b,c > 0$ .

I would very much appreciate if you could help me with how I can proceed from this step and finally solving the problem. Thank you

Is this $abc’$ conjecture true of the natural numbers?

Here, the notation $ abc’$ is identical to $ (abc)’$ and is a name of a conjecture which is (so to speak) a reduction of the familiar $ abc$ conjecture. This $ abc’$ conjecture would be described as below.

Let $ P’$ be the set of primes defined per the following:

  1. If there exists an even number $ e$ greater than two and is not a sum of two primes, then the prime $ p$ which is the greatest prime less than $ e$ is called a prime$ ‘$ number. For instance, if $ 10$ were not a sum of two primes then the prime $ 7$ would be a prime$ ‘$ number.

  2. $ P’ = \{p | \text{$ p$ is a prime but not a prime$ ‘$ number}\}$

    Naturally $ P’$ isn’t empty since, for example, $ 2, 3, 5, 7 \in$ $ P’$ .

The $ abc’$ conjecture is then defined to be the familiar $ abc$ conjecture except that all the relevant primes must necessarily be in $ P’$ .

Is this $ abc’$ conjecture true of the natural numbers?