CUSTPRIM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Kevin Atienza
Tester: Jingbo Shang and Pushkar Mishra
Editorialist: Kevin Atienza

CREDITS

Special thanks to the author of the problem for providing a detailed explanation.

DIFFICULTY

hard

PROBLEM

Payton numbers are defined, and prime Payton numbers are defined. Given a Payton number, is it prime or not? (Please see the problem statement for more details)

QUICK EXPLANATION

First, the term “prime” defined in the problem statement actually refers to the abstract-algebraic term “irreducible”, and the term “prime” itself is defined differently. Thankfully, as we shall see below, the primes and irreducibles in Payton numbers coincide.

Let \omega be a symbol such that \omega^2 = \omega - 3. Then there is an isomorphism between the Payton numbers and the Euclidean domain \mathbb{Z}[\omega] given by \phi(a,b,c) = (33-2a-c)+(b-a)\omega. This means that the Payton numbers also form a Euclidean domain (thus primes are the same as irreducibles), and that we have reduced the problem to a primality check in \mathbb{Z}[\omega].

In \mathbb{Z}[\omega], all elements x are of the form x = a + b\omega where a, b \in \mathbb{Z}. If we define the norm of x (denoted as Nx) as a^2 + ab + 3b^2, then we can show the following:

  • If x is an integer (i.e. b = 0), then x is prime if and only if x is a prime integer, and either x = \pm 2 or x \not= \pm 11 and -11 is not a quadratic residue modulo x.
  • If x is not an integer (i.e. b \not= 0), then x is prime if and only if Nx is a prime integer.

This yields an efficient solution to the problem as long as we can quickly check whether an ordinary integer is prime, and we can quickly check whether -11 is a quadratic residue modulo a prime. Primality checking is a standard problem which can be solved using the Miller-Rabin test for example, and checking whether -11 is a quadratic residue modulo a prime can be done with Euler’s criterion.

EXPLANATION

Denote S as the set of Payton numbers.

Primes in S

Let \omega be a symbol such that \omega^2 = \omega - 3. Then we can define addition and multiplication in the set \mathbb{Z}[\omega] = \{a + b\omega : a, b \in \mathbb{Z}\} naturally, and the resulting structure is actually a principal ideal domain (we’ll discuss this below).

In fact, S is isomorphic to \mathbb{Z}[\omega]! This means that the structure of S and \mathbb{Z}[\omega] are identical. In other words, S is just \mathbb{Z}[\omega] with its elements simply relabeled or renamed.

Define \phi as a map from S to \mathbb{Z}[\omega] where \phi(a,b,c) = (33-2a-c)+(b-a)\omega. Then \phi is an isomorphism, i.e. a bijective map that satisfies:

\phi(a+b) = \phi(a) + \phi(b)
\phi(ab) = \phi(a)\phi(b)

The inverse of \phi can be written as the following:

\phi^{-1}(a+b\omega) = \begin{cases} (11-k,11-k+b,11) & \text{if $a$ is even and $a = 2k$} \\\ (4-k,4-k+b,24) & \text{if $a$ is odd and $a = 2k+1$} \end{cases}

This is great, because this means that the properties of S are exactly the same with \mathbb{Z}[\omega]. For instance, an element x of S is prime in S if and only if \phi(x) is prime in \mathbb{Z}[\omega]. Therefore, we can study the primes in \mathbb{Z}[\omega] instead.

How to find this isomorphism

Now, you might be wondering: how does one discover this isomorphism? To be honest, I don’t know of any surefire way to do this. Even inspecting the accepted solutions doesn’t help much, because we can’t see the process of discovery there. But a possible line of attack might be:

  • Play around with multiplication and realize it is commutative, and also associative if you’re lucky. This suggests that it might be isomorphic to some well-known ring.
  • Realize that multiplication is symmetric in a and b, and that the Payton “zero” and “unity” both satisfy a = b. This suggests studying the Payton numbers where a = b would be fruitful. If you’re lucky enough, you might notice that this subring is isomorphic to the ring of ordinary integers ((a,a,c) pairs with the integer 33-2a-c).
  • Realize that Payton numbers are really just two-dimensional, and (using the knowledge of a subring isomorphic to the integers) guess that they must be isomorphic to a quadratic integer ring. Discovering which ring it is might take some experimentation, but I would guess that the worst is behind at this point.

Primes in \mathbb{Z}[\omega]

Notice that one can write \omega = \frac{1+\sqrt{-11}}{2}. First, we show that \mathbb{Z}[\omega] is a Euclidean domain. A Euclidean domain R is an integral domain endowed with a Euclidean function, which is a function f from R to \mathbb{N} satisfying the following property:

If a and b are in R and b \not= 0, then there exists q and r in R such that a = bq + r and either r = 0 or f(r) < f(b).

In the case of \mathbb{Z}[\omega], the Euclidean function we will use is f(a+b\omega) = a^2+ab+3b^2. Notice that if one writes \omega = \frac{1+\sqrt{-11}}{2} = \frac{1}{2}+\frac{\sqrt{11}}{2}i, then f(x+yi) is just x^2+y^2, which is just the square of the distance to the origin 0+0i of the complex plane.

Our proof requires a property of the field \mathbb{Q}[\omega] = \{a + b\omega : a, b \in \mathbb{Q}\}. Notice that f can be naturally generalized to include \mathbb{Q}[\omega] in its domain, though the codomain of f becomes \mathbb{Q}.

Claim

For every element x of \mathbb{Q}[\omega], there exists an element n in \mathbb{Z}[\omega] such that f(x-n) < 1.

Proof

Let’s call x good if there exists an n in \mathbb{Z}[\omega] such that f(x-n) < 1, so we are trying to prove that all elements of \mathbb{Q}[\omega] are good. The following are facts about goodness (simple to show):

  • Let m\in \mathbb{Z}[\omega]. Then x\in \mathbb{Q}[\omega] is good if and only if x-m is good.
  • x\in \mathbb{Q}[\omega] is good if and only if -x is good.

Therefore, if a+b\omega is an element of \mathbb{Q}[\omega], then the element \lfloor a \rfloor + \lfloor b \rfloor \omega is an element of \mathbb{Z}[\omega]. So a+b\omega is good if and only if (a+b\omega) - (\lfloor a \rfloor + \lfloor b \rfloor \omega) = (a-\lfloor a \rfloor) + (b - \lfloor b \rfloor \omega) is good. Thus we have reduced the general case to the case where 0 \le a < 1 and 0 \le b < 1. Also, note that if a + b > 1, then a+b\omega is good if and only if -a-b\omega is good, if and only if -a-b\omega+(1+\omega) = (1-a)+(1-b)\omega is good. Thus we have further reduced the case to the case where a \ge 0, b \ge 0 and a + b \le 1.

Finally, assume a \ge 0, b \ge 0 and a + b \le 1. Then, considering a+b\omega as a point in the complex plane with \omega = \frac{1+\sqrt{11}i}{2}, we have that a + b\omega is inside the triangle bounded by vertices 0+0\omega = 0+0i, 1+0\omega = 1+0i and 0+1\omega = \frac{1}{2} + \frac{\sqrt{11}}{2}i. The vertices are elements of \mathbb{Z}[\omega]. Inside this triangle, the point farthest from any vertex is the circumcenter of the triangle, which can be easily calculated as \frac{1}{2}+\frac{5}{2\sqrt{11}}i. The norm of this number minus each of the vertices is 9/11 < 1, so the claim is proven for a+b\omega (take the nearest vertex).

End proof

We can now show that \mathbb{Z}[\omega] is a Euclidean domain. Note that division is defined in \mathbb{Q}[\omega], and that f(ab) = f(a)f(b) for any a and b (Hint: consider a and b as complex numbers).

Claim

\mathbb{Z}[\omega] is a Euclidean domain with the Euclidean function f(a+b\omega) = a^2+ab+3b^2.

Proof

Let a and b be in \mathbb{Z}[\omega], and b \not= 0. Note that a/b is an element of \mathbb{Q}[\omega]. By the claim above, there exists a q in \mathbb{Z}[\omega] such that f(a/b-q) < 1. Let r = a - qb. Then f(r/b) < 1, so

f(r) = f(r/b\cdot b) = f(r/b)f(b) < 1f(b) = f(b)

and the Euclidean property is satisfied, QED.

End proof

Being a Euclidean domain is very nice. For instance, greatest common divisors are well-defined and always exist. Also, every Euclidean domain is a principal ideal domain (PID). It is a well-known fact that every PID is a unique factorization domain (UFD), which means that every number can be written uniquely as a product of primes and a unit.

It is also true in UFDs that irreducible elements are the same as prime elements. Note that irreducible and primes are actually distinct, although we are used to the idea that these are the same, because they are the same in the domain of integers. Also, note that the definition given in the problem statement is actually that of irreducible elements, not prime elements, but since these are the same in a UFD, there’s no problem.

In number theory, we say that a divides b in R, denoted as a \mid b, if there is a c in R such that ac = b. We say that x \in R is a unit if x \mid 1 in R (in the ring of integers, the units are precisely -1 and 1, and in the Payton numbers, (4,4,24) and (5,5,24)). A non-unit p is irreducible if p cannot be factorized into non-units (i.e. if p = ab, then either a or b is a unit), and a non-unit p is prime in R if p \mid ab implies p \mid a or p \mid b.

We now define greatest common divisors. We say that g is a greatest common divisor, or gcd, of a and b if every common divisor of a and b divides g. Note that we say a gcd instead of the gcd because there can be many greatest common divisors of a and b. For example, if g is a gcd of a and b, then -g is also a gcd. However, it is also true that if g_1 and g_2 are gcd’s of a and b, then g_1 = ug_2 for some unit u (this follows from the easily provable fact that x \mid y and y \mid x implies x = uy for some unit u).

We now show that gcd is well-defined:

Claim

Every pair (a,b) of values in a Euclidean domain R has a gcd.

Proof

If b is zero, then a is a gcd, because every element r in R divides 0 (because r0 = 0). Therefore, the common divisors of a and 0 are simply the divisors of a. If b is nonzero, then we prove the claim by induction on f(b) (which makes sense because \mathbb{N} is well-ordered). Let a = bq + r with r = 0 or f(r) < f(b).

If r = 0, then b is a gcd of a and b, because every divisor of b is also a divisor of bq = a. If f(r) < f(b), then by induction, b and r has a gcd, say g. We claim that g is also a gcd of a and b. This is because every common divisor of a and b also divides a-bq = r, so by definition of gcd, it also divides g, thus proving that g is a gcd of a and b. QED.

End proof

Note that this proof is analogous to the Euclidean gcd algorithm. In fact, this is why R is called a Euclidean domain.

We now prove Bezout’s identity in Euclidean domains.

Claim

If g is a gcd of a and b in R, then there exists x and y in R such that ax + by = g.

Proof

If b = 0, then a is a common divisor of a and b, and since g is a gcd, a \mid g, therefore, g = ac for some c. This means that ca + 0b = g (i.e. (x,y) = (c,0)). If b is nonzero, then we prove the claim by induction on f(b). let a = bq + r with r = 0 or f(r) < f(b).

If r = 0, then b is a common divisor of a and b, and since g is a gcd, b \mid g, therefore g = bc for some c. This means that 0a + cb = g (i.e. (x,y) = (0,c). If f(r) < f(b), then g is also a gcd of b and r, so by induction there exists x' and y' such that x'b + y'r = g. Then y'a + (x' - qy')b = g (i.e. (x,y) = (y', x' - qy')). QED.

End proof

Note that this is analogous to the extended Euclidean gcd algorithm.

Define the conjugate of a + b\omega as a + b - b\omega, and denote it as (a + b\omega)'. The conjugate has the following nice properties (which are easy to prove and are left as exercises):

  • x'' = x
  • (x + y)' = x' + y'
  • (xy)' = x'y'
  • x is prime if and only if x' is prime.
  • If x \mid y, then x' \mid y'
  • If g is a gcd of a and b, then g' is a gcd of a' and b'
  • x is an integer if and only if x' = x
  • x + x' is an integer. This quantity is called the trace of x. The trace of a + b\omega is 2a + b.
  • xx' is an integer. This quantity is called the norm of x.

The norm is actually important for our purposes. It is denoted as Nx (i.e. Nx = xx'), and has the following properties (which are also easy to prove and are left as exercises):

  • N(a+b\omega) = a^2+ab+3b^2. Note that this coincides with the Euclidean function f we used above.
  • Nx \ge 0.
  • Nx = 0 if and only if x = 0.
  • Nx = N(x')
  • x \mid Nx
  • If x \mid y, then Nx \mid Ny.
  • N(xy) = Nx\cdot Ny. It follows that if x is a unit, then Nx = 1.
  • Nx = 1 if and only if x = 1 or x = -1. It follows that the only units in \mathbb{Z}[\omega] are 1 and -1.

We now begin to uncover exactly which elements of \mathbb{Z}[\omega] are prime. We begin with the following:

Claim

If x is a non-unit in \mathbb{Z}[\omega] and Nx = p for some prime integer p, then x is prime.

Proof

If yz = x, then Ny\cdot Nz = N(yz) = Nx = p. Therefore, either Ny or Nz is 1, so either y or z is a unit. Therefore, x is irreducible, so x is prime, QED.

End proof

Next, we show that the norms of prime elements are actually very limited in form:

Claim

If x is prime in \mathbb{Z}[\omega], then Nx is either a prime integer or a square of a prime integer.

Proof

Factorize the integer Nx as Nx = p_1\cdot p_2\cdots p_k. Now x divides Nx, and since x is prime, x therefore divides some p_i. Therefore, Nx \mid Np_i = p_i^2. So Nx can be 1, p_i or p_i^2. But x is not a unit, so Nx is a prime or a square of a prime, QED.

End proof

Now, a normal composite integer is also composite in \mathbb{Z}[\omega], because its integer factorization is also valid in \mathbb{Z}[\omega]. However, not all prime integers are primes in \mathbb{Z}[\omega]. The following describes a family of prime integers which are not prime in \mathbb{Z}[\omega].

Claim

If p is an odd prime, p \not= \pm 11, and if -11 has a square root mod p, then p is factorable as p = xx', where x and x' are primes in \mathbb{Z}[\omega].

Proof

Let a be a square root of -11 mod p (i.e. a^2 \equiv -11 \pmod{p}). Note that p divides a^2+11.

Now, let x be a gcd of p and a+1-2\omega. By Bezout, there exist A and B such that x = Ap+B(a+1-2\omega). By taking conjugates, and noting that p' = p and (a+1-2\omega)' = (a-1+2\omega), we see that x' is a gcd of p and a-1+2\omega, and x' = Ap + B(a-1+2\omega).

Thus,

xx' = (Ap+B(a+1-2\omega))(Ap+B(a-1+2\omega))
= A^2p^2+ABp(2a)+B^2(a^2+11)
= p[A^2p+AB(2a)+B^2(a^2+11)/p]

So Nx = xx' is divisible by p, and x is not a unit. Thus x' is also not a unit.

Now, let g be a gcd of x and a-1+2\omega. Thus there exists C and D such that Cx + D(a-1+2\omega) = g. Now, since x \mid (a+1-2\omega), we have g \mid (a+1-2\omega). Thus, g \mid (a+1-2w)+(a-1+2w) = 2a. Thus, g is a common factor of 2a and p. But 2a and p are coprime, so g \mid 1, and gh = 1 for some h.

Thus:

Cx + D(a-1+2\omega) = g
Chx + Dh(a-1+2\omega) = gh = 1
Ch(xp) + Dhp(a-1+2\omega) = p

Now, x' divides p, so xx' divides xp. Also, x divides p and x' divides a-1+2\omega, so xx' divides p(a-1+2\omega). Therefore, xx' divides Ch(xp) + Dhp(a-1+2w) = p.

Now, Nx = xx' divides p and is divisible by p, therefore xx' = p. Thus, p is product of non-units x and x'. Furthermore, Nx = N(x') = p, so x and x' are prime, QED.

End proof

The following shows that the converse is also true:

Claim

If p is a prime and p \not= \pm 11, and -11 doesn’t have a square root mod p, then p is irreducible in \mathbb{Z}[\omega].

Proof

We prove the contrapositive.

If p is reducible as xy = p with non-units x and y, then Nx\cdot Ny = Np = p^2. Since x and y are non-units, the only possibility is Nx = Ny = p. Now, let x = a+b\omega. Then:

p = Nx
p = a^2+ab+3b^2
4p = 4a^2+4ab+12b^2
4p = (2a+b)^2+11b^2
0 \equiv (2a+b)^2+11b^2 \pmod{p}
(2a+b)^2 \equiv -11b^2 \pmod{p}
[(2a+b)b^{-1}]^2 \equiv -11 \pmod{p}

This means that (2a+b)b^{-1} \bmod p is a square root of -11 mod p. Note that b is invertible mod p because if p \mid b, then p also divides p - ab - 3b^2 = a^2, so p \mid a. This means that p \mid a + b\omega = x, and p^2 = Np \mid Nx = p, a contradiction, QED.

End proof

These two claims cover most of the primes. The only ones not covered are \pm 2 and \pm 11. Luckily, they can be easily checked by hand: 11 and -11 are not prime because -11 = (1-2\omega)^2 and 11 = -(1-2\omega)^2 = (1-2\omega)(1-2\omega)', and it can easily be shown that 2 and -2 are prime (Hint: Show that there doesn’t exist x such that Nx = 2).

Next, we describe the rest of the prime elements of \mathbb{Z}[\omega]. Let x be a prime. We have shown above that that Nx should be a prime or a square of a prime. If Nx is prime, we have shown above that x is prime. Now, what if Nx is the square of a prime? The following shows that x is an integer:

Claim

If x is prime and Nx = p^2, then x = \pm p.

Proof

First, if p cannot be factored in \mathbb{Z}[\omega], then the only nontrivial factorizations of p^2 are p\cdot p and -p\cdot -p. Since xx' = p^2, then x = \pm p.

If p can be factorized in \mathbb{Z}[\omega] into two primes p = yy', then p^2 = yy'yy' = y^2(y')^2. Thus, the only factors of p^2 whose norm is p^2 are \pm y^2, \pm yy' and \pm (y')^2, and x can only be one of those. But none of those are prime, so this case is impossible.

End proof

We can now combine all of the above to characterize the primes in \mathbb{Z}[\omega]. Let element x be an element of \mathbb{Z}[\omega]. Then:

  • If x is not an integer, then x is prime if and only if Nx is a prime integer.
  • If x is an integer, then x is prime if and only if x is a prime integer, and either x = \pm 2 or x \not= \pm 11 and -11 is not a quadratic residue modulo x.

Checking whether an integer p is prime can be done with Miller-Rabin.

Checking whether -11 is a quadratic residue modulo a prime p can be done using the Legendre symbol \left(\frac{a}{p}\right), which is defined as:

\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if $p \not\mid a$} \\\ 1 & \text{if $p\mid a$ and $a$ is a quadratic residue modulo $p$} \\\ -1 & \text{if $p \mid a$ and $a$ is not a quadratic residue modulo $p$} \end{cases}

By Euler’s criterion, this can be calculated in O(\log p) time as:

\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod{p}

Note that you could also use the law of quadratic reciprocity to more quickly check whether -11 is a quadratic residue: -11 is quadratic modulo an odd prime p if and only if p \equiv 0, 1, 3, 4, 5, \text{ or } 9 \pmod{11} (i.e. those odd p's which are quadratic residues modulo 11).

SUMMARY

We now summarize the algorithm.

def is_prime_integer(k) {
   // returns whether k is a prime integer.
   // you can use something like Miller-Rabin for this.
}
   
def is_prime(a,b,c) {
    A := 33 - 2*a - c
    B := b - a
    if (B = 0) {
        return |A| = 2 or (
            is_prime_integer(|A|) and
            modpow(-11,(|A|-1)/2,|A|) = |A|-1
        );
    } else {
        return is_prime_integer(A*A + A*B + 3*B*B);
    }
}
6 Likes

It looks like an amazing problem, but the problem statement is repulsive. I(and probably others too) didn’t care to try this problem because of that reason. It would have been much better if the problem had been cleaner.

2 Likes

Oh man. In high school I was very passionate about mathematics and number theory, now I’m on a third year of bachelor mathematical studies and I attended Algebra I and Algebra II, so as you can see, I’m also a huge fan of stuff like quadratic residues, quadratic fields and algebrical thingies like PID’s, UFD’s and so on, so everything from “Primes in Z[w]” on looks amazing for me, but you have just made a terrible thing. From a beatiful problem from a mathematical point of view you created litterally the biggest shit I have ever seen. If I had been told to check whether something is prime in some quadratic ring I would have probably delved into it and have much fun, but those rules of multiplications were so incredibly ugly that I haven’t even read them properly. What was your goal when expressing problem in such repulsive way!? Main goal of problems creators should be to provide fun for competitors (because what are other goals?) and problems should be adjusted to achieve this. I learned that the hard way when I gave one nice problem for PolishOI. It contained some tricky divide-and-conquer algorithm with sweeping line, but nobody even approached it, because I included a little bit of geometry there. That geometry was really not a big obstacle, but people just got scared and nobody even wondered how to solve the main part of the problem (you can view it here: http://main.edu.pl/en/archive/oi/21/lam). Here is even more severe case, because that geometry wasn’t that bad either way and here we are given something incredibly tedious and we can’t see the beauty of Z[w] behind those ugly formulas.

I’ll let you know that I registered in CodeChef while ago just to express my sorrow that such nice problem was wasted in such a stupid way… I like your math problems very much, but, but… Never do that again. Don’t hide core of the problem behind something which might get people scared.

4 Likes

It rarely happens that authors provide detailed explanations for a problem. And when they do, they are met with such criticism as ‘Question being repulsive’. I believe there is a better way to criticize the work of some one. And also while we do it, let’s not forget that the author took his precious time to actually explain the solution in details. So while we criticize the problem, we shouldn’t forget to commend the author on putting such an amazing editorial.

Honestly, this will be the same author who will probably create a different problem in some other contest and don’t even bother to write a single line of explanation for the solution, especially when people treat someone’s hard work this way.

To the author: You did an amazing job on the editorial. Thank you. Please understand, it is these kind of editorials that help beginners like us to learn and progress. I and I am sure many others owe you for the hard work on the editorial.

5 Likes

Criticism of a problem (a specific, but relevant part of the problem) is not criticism of its editorial.

There’s no better way to criticise than by directly saying what’s wrong. It was repulsive because of the lengthy way multiplication was defined: true. It’s not good: true. Are you saying that’s wrong, or is this just an Appeal to Emotion?

1 Like

who will probably create a different problem in some other contest and don’t even bother to write a single line of explanation for the solution

In other words, there’s no way the author could actually listen to others and try to improve the part that’s being (validly) complained about. Right?

Have you ever heard the term “constructive criticism”?

2 Likes

Something I have learned on the job, good leaders who have to criticize the employees reporting to them, manage to do it in an encouraging way. I am sure what’s being said here is constructive criticism. But where is the appreciation for the editorial? At the end of the day, whether it is constructive criticism or pure bashing. If you deliver it in a way that discourages the person concerned, then you have failed at your attempt and simply vented out your frustration, that’s all.

Personal experience: I work for Microsoft and in one project I was working with a veteran(23 years). I worked hard to come up with a pattern that was usable for intrusion detection using ML but this person started challenging me.He made me realize, the pattern generates lot of false positives. Now he could have bashed me saying I didn’t validate. Instead he thanked me for my hard work but asked me to write emails using softer words like ‘I Propose’ rather than ‘must be’. That is also constructive criticism my friend, delivered well. Not discouraging but making me learn and self reflect!

1 Like

If it discourages the author from adding extremely technical parts to his problems, then it’s good.

There’s a huge difference between “on the job” and “programming contests over the Internet” talks: the former needs to build a good relationship between people who meet each other daily, the latter needs being heard and remembered. Saying absolutely nothing in a nice tone isn’t a good way to have your point remembered.

You should get used to some answers to editorial posts to be on the problems themselves, not the editorials. There’s just no other place to post them. And it’s not like an answer posted here has to talk about the editorial.

These can be considered “editorial appreciation”, though: “It looks like an amazing problem” and “everything from “Primes in Z[w]” on looks amazing for me”. If the statement is repulsive, where else would that come from than from the editorial?

In my opinion, “problem statement is repulsive” kind of arguments can be considered valid if the contest is of very small duration. In my opinion, problem statement was quite concise and clear. Some people have said that it would have been great if he would have directly asked to check primes in Z[w] without making us find what is Z[w] for the current case (i.e. isomorphism from S to Z(w)). I humbly disagree with them, cracking the actual representation was a crucial part of the problem. It might be dependent on person to person, I think figuring out the actual isomorphism for the current case is certainly interesting. The problem was quite non-standard for codechef, but codechef had a lot of amazing nice number theory problems which deal with very advanced subjects. But in my view, I consider this problem one of the my favorite problems in codechef. This problem clears a lot of fundamental concepts in number theory.

It would be really interesting to see opinions of people who have solved it.

3 Likes

The problem seems to become approachable once one makes the reduction from the given multiplication algorithm to Z[w]. I looked at most of the accepted solutions and it seems that they all noticed this reduction (to something similar to Z[w]). I, for one, didn’t notice any such reduction. Not that I didn’t look for one, but the fact that the multiplication algorithm made use of floor(s/2) discouraged me (I didn’t think that the effects of the floor function could be achieved by normal multiplication). Thus, my solution is very different from anything written in this editorial (but it took me way longer to solve the problem than I would have liked). One important difference between my solution and the one in the editorial is that in my solution I actually factorize each given Payton number (i.e. I decide that (A,B,C) is not prime if I find a pair of Payton numbers (X,Y,Z) and (U,V,W) such that (X,Y,Z) x (U,V,W) = (A,B,C)). The trick, of course, was to limit the amount of candidates I had to test.

It turns out that these candidates (which are very few in number) could be derived from the solutions of two separate two-variable quadratic equations: F(x,y)=0 and G(v,w)=0. One of them has an easy form: f1 * x * y + f2 * x + f3 * y + f4 = 0 (the solutions can be found by considering the divisors of some combination of the coefficients). The other one is tougher: w^2 + 11 * v^2 = N, where N is a 64-bit composite number (and depends on the given Payton number (A,B,C)). I used the results from a paper to solve the second equation. It requires factorizing N into prime powers, finding quadratic residues modulo those powers and combining the results using Chinese remainder theorem (CRT). For each of the numbers obtained through CRT (there are around 2^r such numbers, where r is the number of different prime divisors of N) one can use something similar to Euclid’s algorithm to find a valid solution (v,w) (in general there are very few such solutions, which is what helped in having a very small number of candidates to test). Out of all these steps, factorizing N was the slowest part, because there could be cases where N had two large prime factors. In general, not all the test cases lead to Ns which were hard to decompose. In the end I remained with 2 test files which had many such Ns and for which I was getting TLEs (I was about 5 times slower than needed on these 2 files, while all the others tests passed within the time limit). I needed between half a day and a day (including sleep) to optimize my solution enough to squeeze it into the time limit (in the end I had a test which ran in 9.9 seconds out of the 10 seconds time limit for Java).

By the way, I have a question for the author. Why was the time limit set to 5 seconds (for C/C++) ? I think that the solution described in the editorial takes much less time. Not that I’m complaining about this :slight_smile:

11 Likes

@dpraveen: I think the problem was fine as it was - though much more difficult than it would have been if Z[w] had been explicitly mentioned in the problem statement. Cracking the isomorphism was one of the toughest parts of this problem. I actually solved the problem without noticing the isomorphism :slight_smile: Though I probably benefited from some of its properties, without really knowing it.

4 Likes

First of all, I really enjoyed the problem, and I think it is totally OK to obfuscate the problem in a 10-day long contest.

Here is how I solved the problem.
I first used a brute force way to verify the test cases given in the problem, and then I found out that

(4, 5, 24) = (5, 5, 24) x (5, 4, 24)

Which means that one of the (5, 5, 24) and (5, 4, 24) must be unit, and sure it can be verified that (5, 5, 24) divides unity. This gave me the impression that probably (4, 4, 24) corresponds to 1, and (5, 5, 24) corresponds to -1. Also, it seems like that the 1 and -1 have the center (9/2, 9/2, 24) between them, which probably could be another zero, had we allowed a and b to be half integers.

Anyway, I decided to explore the multiplication of the numbers (a, b, c), where a = b.

(a, a, 11) x (b, b, 11) → (11 - 2 (a - 11) (b - 11), 11 - 2 (a - 11) (b - 11), 11)
(a, a, 11) x (b, b, 24) → (11 - 2 (a - 11) (b - 9/2), 11 - 2 (a - 11) (b - 9/2), 11)
(a, a, 24) x (b, b, 24) → (9/2 - 2 (a - 9/2) (b - 9/2), 9/2 - 2 (a - 9/2) (b - 9/2), 24)

From the above expression it seems like that if we do the following transformation
(a, b, 11) → (11 - a, 11 - b)
(a, b, 24) → (9/2 - a, 9/2 - b)

then probably the multiplication could be expressed in a more uniform way, i.e., after the above transformation, we should be able to find a nice functions F() and G() such that

(A1, B1) x (A2, B2) = (F(A1, B1, A2, B2), G(A1, B1, A2, B2))

and sure enough, we can find such function F() and G(), except that they are not that pretty either.

(A, B) = (A1, B1) x (A2, B2), then

2A = 3 (A1 B2 + A2 B1 - B1 B2) + A1 A2
2B = 9 (A1 B2 + A2 B1 - A1 A2) - 5 B1 B2

I thought that maybe we can take a linear combination of the two equations in such a way that the RHS can be factored nicely, i.e.,

x (2A) + y (2B) = (x1 A1 + y1 B1) x (x2 A2 + y2 B2)

because, then we could find all divisors of LHS, and match them with the RHS, and solve the two linear diophantine equations (using euclidean gcd algorithm) independently.
Let us say z = y/x, then

2A + z (2B) = A1 ((3 + 9z) B2 + (1 - 9z) A2) + B1 ((-3 - 5z) B2 + (3 + 9z) A2)

In order for the RHS to be factorable, we need

(3 + 9z) / (1 - 9z) = (-3 - 5z) / (3 + 9z)

This gives us a quadratic equation in z, whose roots are imaginary numbers,

z = (4 + i sqrt(11)) / 9, and its conjugate

which means we won’t get nice factors on the RHS, but we will get some factors. After using this value of z to compute the linear combination, we get the following.

2 (A + zB) = (1 - 9z) (A1 + zB) (A2 + zB)

we can take the norm of both sides, so we get

9 ((9A - 4B)^2 + 11 B^2) = ((9A1 - 4B1)^2 + 11B1^2) ((9A2 - 4B2)^2 + 11B2^2)

So, if we can find all factors of LHS, we can match them with the two terms on RHS, and try to compute the possible values of A1, B1, A2, B2, i.e., if P is a factor of LHS, then find all integer solutions of

P = x^2 + 11y^2, and then solve

9A1 - 4B1 = x,
B1 = y,

and check if this is a valid factor. Unfortunately, 11 is not an Idoneal number, so we don’t have any nice characterization of number of the number (x^2 + 11y^2). This is the point where my number theory skills gave up, and I decided to just factorize the LHS, and solve the diophantine (x^2 + 11 y^2 = P) using a combination of precomputed solutions and and O (sqrt§) time brute force method.

However, solving the quadratic diophantine was not the bottleneck in my approach. The factorization of LHS was taking 85% of total time (as mugurelionut@ already noted). Luckily, I found Shank’s factorization method which is quite fast, if you implement it properly (I didn’t, I copied the code from somewhere in web, which I cannot find again, so I cannot acknowledge the person who wrote it). It takes around 100 usec to factor a number as large as (2 * 10^15) on a moderate machine.

Anyway, looking at author’s solution I think time limit of 5s was very liberal to allow me to fit the factorization of large numbers into time limit, of course, during the contest I had different opinion about the time limit.

6 Likes

It’s really a nice problem! I took the form ϕ(a,b,c)=(33-a-b-c)+(a−b)ω and ω^2+3ω+5=0. The other parts were similar. Most properties I used in this problem were reached by analogy with Gaussian integers and Eisenstein integer without any proof. During solving the problem, I also read something about Euclidean domain or UFD, which help a lot to discovering or guessing some conclusions.

2 Likes

@djdolls: I will look for Shank’s factorization method. It seems like it could have also made my life easier :slight_smile: In my solution I used a combination of brute force for small primes + Brent-Pollard. But the final optimizations that I made (and which made a huge difference) were to optimize the function which multiplies two 64-bit numbers modulo another 64-bit number (which was used in many places in the code, particularly in the Brent-Pollard algorithm). With this I got from a solution 5 times slower than needed (on a “bad” test) to one only 1.2 times slower (which I later tweaked further).

In Shank’s method almost all operations are done on n-bit integers, when factoring a 2n-bit integer, which makes it significantly faster.

I set the time limit to 5 seconds because I thought the most important part of this problem is to find the isomorphism and fast primality testing is only secondary. I even had my Python code accepted.

Plus I wasn’t really aware that it could be cracked with advanced factorization, but to me, your solutions are still good as accepted, because of the huge amount of effort involved :slight_smile:

1 Like