G. Modular Tetration — a Number Theory Solution

Preliminary Comments

I deleted the first post and am publishing a new one with preliminary comments. This problem turned out to be problematic and spoiled the contest for strong participants, since some cheaters copied it, but it didn’t seem difficult to me, except for deriving the final formula and a bit of implementation. During the contest, I managed to work out the implementation on paper, but I couldn’t handle the coding.

I am a junior in mathematics, focusing on number theory and algebra (at the last JBMO I managed to solve both of these topics), but I still have many gaps in CP and implementation. In number theory I solve or make substantial progress on many problems from IMO shortlists. If you assign a CF-like rating to those problems, I solve problems steadily up to 2000, sometimes up to 2500, and there have been harder ones.

Now I want to use number theory and mathematical implementation of programming problems as a boost for CP. I noticed that the mathematical part of some problems (above my current rating) is easy for me, which gives me hope to raise both implementation and CP methods to the same level. For example, in the summer I solved the “Faculty” (2400) number theory problem on my own within an hour. I implemented the mathematical part and managed to write the code.

On paper I analyze CP problems rated 2000 and higher, where I can use my mathematical skills. I started publishing some materials on my blog. Most often I fail to write code for these problems, but if I have a solution on paper, everything else is psychologically easier to study, learn new things and thus grow. The main thing is not the solution itself, but the path. I also use this tactic — if I have a solution, I write a naive TLE code, then improve it; even if the code passes, I try to improve the time further to understand all the techniques.

That was the introduction. Below is my write-up for problem 2147G, which I was able to solve on paper in 30 minutes (though there are still unclear points), but I still can’t implement the code. Such a solution is natural for mathematicians; all steps are clear to anyone who has studied olympiad number theory even at a basic level. But the official editorial is not very clear to me — that is, it is clear, but unfamiliar. It is more suitable for experienced CP programmers. Perhaps I am wrong.

Write-up

Let $$$m\ge 2$$$ be given, and define the sequence $$${b_n}$$$ by

Call $$$a$$$ $$$m$$$-tetrated if there exists $$$N$$$ such that

We need the density of such $$$a$$$.

1) Euler

By Euler’s theorem:

By the requirement, $$$a^{b_n}\equiv1\pmod m$$$ for all $$$n\ge N$$$. It is then obvious that $$$(a,m)=1$$$; otherwise the residue $$$1$$$ won’t appear.

2) $$$\gcd$$$ trick (Euclid)

Classical fact: if $$$a^r\equiv1\pmod m$$$ and $$$a^s\equiv1\pmod m$$$, then

(Proof via Bézout: $$$\gcd(r,s)=ur+vs$$$.)

Hence,

This is a classical trick for this type of problems.

3) Order $$$d=\mathrm{ord}_m(a)$$$

Introduce

Then

Also $$$b_{n+1}=a^{b_n}$$$, hence every prime divisor of $$$d$$$ must divide $$$a$$$. I think these are necessary and sufficient conditions for $$$b_n\equiv1\pmod m$$$ starting from some $$$N$$$. We have reformulated the problem in a convenient way without losing equivalence. Introducing $$$\mathrm{ord}$$$ here plays the same role as, for example, considering the least prime divisor or introducing $$$\gcd$$$. That is, we introduce an extra variable, but the constraints become very tight.

4) Chinese Remainder Theorem (reduction to prime powers)

Divide and conquer. Write $$$m=\prod p^{\alpha}$$$. The condition modulo $$$m$$$ is equivalent to the system modulo all $$$p^{\alpha}$$$. If $$$p^{\alpha}\mid m$$$, repeat the reasoning from items 1–3 for $$$p^{\alpha}$$$. Similarly we get that every prime divisor of $$$d_p$$$ must divide $$$a$$$. Note that

but $$$(a,p)=1 \Rightarrow d_p \mid (p-1)$$$. Thus, every prime divisor of $$$d_p$$$ (which, in turn, divides $$$p$$$) must be a divisor of $$$a$$$.

5) Density over primes

For example, when $$$p=2$$$: $$$d_2=1 \Rightarrow a\equiv1\pmod{2^{\,\alpha}}$$$ $$$\Rightarrow$$$ we get a contribution $$$1/2^{\,\alpha}$$$.

Similarly, for $$$p \gt 2$$$ we get the contribution $$$\varphi(d_p)/p^{\alpha}$$$, where $$$d_p$$$ is taken among divisors of $$$p-1$$$. There are a couple more nuances needed to derive the exact final formula.

6) Implementation

Implementation in progress :-))