# Is it possible to find a closed-form expression for $f(n)$?

QUESTİON UPDATED:

Here is my problem:

$$2^x \equiv a \pmod{3^n}.$$

where, $a\not\equiv 0 \pmod{3}$ and $n\in \mathbb{Z^{+}}$

I want to learn that,

If,

$x=\left\{ {{3^n-\binom{n}{2}}-1}\right\}-f(n)$

$a=\sum_{j=0}^{n-1} 3^{n-j-1} 2^{3^j - \binom{j+1}{2} -1}=2^{3^{n-1}-\frac {n(n-1)}{2}-1}+3\cdot2^{{3^{n-2}-\frac {(n-1)(n-2)}{2}-1}}+3^2\cdot2^{{3^{n-3}-\frac {(n-2)(n-3)}{2}-1}}+\cdots+3^{n-1}$

Is it possible to find a general solution that depends on $n$?

I found these values with algorithmic ways:

$f(3)=16,f(4)=50,f(5)=94,f(6)=182,f(7)=400$

The exact form of the problem is:

$$2^{\left\{ {{3^n-\binom{n}{2}}-1}\right\}-f(n)}\equiv \sum_{j=0}^{n-1} 3^{n-j-1} 2^{3^j - \binom{j+1}{2} -1} \pmod{3^n}.$$

Question: For $f(n)$ is it possible to find a closed-form expression depends on $n$ , which that $f:\mathbb{N}\to\mathbb{N}$ such that $f(n)\in\mathbb{N}_{>0}$ ?

Small supplement:

Is it possible to find an algebraic closed form for $n\to\infty$ , can the simpler function $f'(n)$ be found, which gives $\lim_{n\to\infty} \frac{ f(n)}{f'(n)}=1$ ?

I mean, for example, if $f(n)=2^n+n^2+n$

We get, for $f'(n)=2^n.$

Is something like this possible?

• Well, more or less by definition, $x$ is the discrete logarithm (of $a$ to the base $2$ in $\Bbb Z/3^n$). So I guess the question is: Is there a formula/method/algorithm to compute its value, for given $a$ and $n$? – Torsten Schoeneberg Apr 14 '18 at 16:53
• Wow, 29 edits. I think I'll wait until the question settles down. – Gerry Myerson Jul 8 '18 at 3:55
• Now up to 38 edits! Student, if you can go one month without making any more edits, let me know, and I'll come back to have a look at the question. – Gerry Myerson Jul 9 '18 at 7:22
• Which of the 45(!) versions of the question would you like me to comment on? I have already told you, I will refuse to even glance at the question as long as you are changing it every couple of hours. When you can go a month without making any changes in the question, that's when I'll take it seriously. – Gerry Myerson Jul 10 '18 at 12:58
• @Gerry Myerson dear Teacher, I finished one month, as you want. Please tell me what I need to do now.. Best Regards. – Elvin Aug 8 '18 at 4:24

We know that there is a solution, since $2$ is a primitive root for all powers of $3$.

For smallish values of $n$, we could solve this by iterating up the powers of three: solve $\bmod 3$ giving $x_1$, then calculate for the $3$ possible values $\bmod 9$, checking $x_1, x_1{+}2, x_1{+}4$ to find $x_2,$ then the $3$ possible values $\bmod 27$, $x_2, x_2{+}6, x_2{+}12$ to find $x_3$ etc. up to $x_n$.

At each step you have the (smallest) solution $x_k$ to $2^{\large{x_k}}\equiv a \bmod 3^k$. Then $x_k{+}\phi(3^k)$ and $x_k{+}2\phi(3^k)$ also solve this. Larger solutions will be greater than $\phi(3^{k+1})$ so one of these three values will be $x_{k+1}$, solving as the smallest solution to $2^{\large{x_{k+1}}}\equiv a \bmod 3^{k+1}$.

This process is relatively quick when you are using exponentiation by squaring.

For example this can quickly solve $2^x\equiv 4827836 \bmod 3^{17}$ as $x\equiv 16391041 \bmod \phi(3^{17})$. That is to say, $x = 16391041$ is the smallest solution and Euler's theorem means that you can add any multiple of $\phi(3^{17}) = 86093442$ for another valid result.

Your example of $2^x\equiv 8164718 \bmod 3^{15}$ solves to $x\equiv 5032989 \bmod \phi(3^{15})$.

• @Student: There is no unique solution, if that is what you mean. What Joffan writes amounts to: The solutions to your example are $5032989, 5032989+\phi(3^{15}),5032989+2\phi(3^{15}),...$. – Torsten Schoeneberg Apr 14 '18 at 17:11
• @Student A function-like expression? no, that isn't possible. – Joffan Apr 14 '18 at 18:12
• I guess that is a matter of perception. This seems like a simple way to me; certainly better than calculating every value of $2^x$ up to $\phi(3^n)$. It involves (at most) $3n$ calculations of $2^m \bmod 3^k$. – Joffan Apr 14 '18 at 19:25
• I note that this method is Hensel lifting applied to the sequence of polynomials $u^{x_k} - a$, picking the lift that keeps $2$ as a root at each step. – Eric Towers Apr 14 '18 at 20:04
• @Student: Except for "trivial" problems, like $a = 2^y$ for small values of $y$, we only have algorithmic solutions. The one here has the advantage that we get all solutions for $3^1, 3^2, \dots, 3^n$ for the same amount of effort. But we do not know a direct method. There is always hope that, in the future, someone will have insight into the hidden structure of the problem and find a more direct method. – Eric Towers Apr 15 '18 at 20:04