2
$\begingroup$

In the work on another question in MSE I have a formula $f(n)$ whose pattern depending on $n \in \Bbb N$ I want decode into an algebraical formula (see a short rationale of $f(n) at the end).

Beginning with the most simple $n$ - namely that which consist of pairs of primes $p,q$ with $n=pq$ - it seems (for the first dozen primes $q,p$) that the following does correctly reproduce the found pattern of $f(n)$ $$x_{p,q}={(p-1)(q-1) \over \gcd(q-1,p-1)} \cdot \text{div}(p-1,q,1/q,1) \cdot \text{div}(q-1,p,1/p,1) \tag 1$$ I thought that it might be a better handling of the formula not to write a case{} clause but a function instead: $$\text{div}(n,m,w_\text{true},w_\text{false} ) = \left\{ \begin{matrix} w_\text{true} & \text{if } m \mid n \\ w_\text{false} & \text{if } m \not \mid n \\ \end{matrix} \right. $$ which, in words, means, that the left fraction in $x_{p,q}$ is additionally divided by $p$ if $p$ divides $q-1$ or divided by $q$ if $q$ divides $p-1$ (it cannot happen that both conditions are true).
As mentioned, for some small $p,q$ this formula works, but because it is an ungly one and difficult to handle, I hope there is a way to express it more concisely/to remove possible redundancy or what.


(Update) This is another notation: Let $$ w_{p,q} = {(p-1)(q-1) \over \gcd(q-1,p-1)} \qquad $$ then $$ f(n) \underset{\text{hypothesis}}= x_{p,q} =\left\{ \begin{array} {} & w_{p,q} / p &\text{ if } p \mid q-1 \\ & w_{p,q} / q &\text{ if } q \mid p-1 \\ & w_{p,q} &\text{ else } \\ \end{array} \right. \tag 2 $$
Update 2 It seems an equivalent formula to (1) in a more algebraic form is

$$ f(n)\underset{\text{hypothesis}}=x_{p,q}={(p-1)(q-1) \over \gcd(q-1,p-1)\gcd(q-1,p)\gcd(q,p-1)} \tag 3$$

It seems even to be a generalization of (1) because it fits the pattern of my function even when $p^A \mid q-1$ with some $A>1$ .

(I have not yet the analoguous pattern when more primefactors are involved, but I think it shall be helpful to have already some reduction in this version of exactly $2$ primefactors)

Q: Can the formula (3) for $x_{p,q}$ be compactified even more?


Here is a small table (I've tested this also with a $48 \times 48$-table).

Let $n=p \cdot q$ where $p,q \in \Bbb P$ then my function $f(n)$ gives the values:

   p\q |   2   3    5    7   11   13   17   19   23   29   31   37  |
   -   +   -   -    -    -    -    -    -    -    -    -    -    -  +
   2   |   1   1    2    3    5    6    8    9   11   14   15   18  |
   3   |   1   2    4    2   10    4   16    6   22   28   10   12  |
   5   |   2   4    4   12    4   12   16   36   44   28   12   36  |
   7   |   3   2   12    6   30   12   48   18   66   12   30   36  |
  11   |   5  10    4   30   10   60   80   90   10  140   30  180  |
  13   |   6   4   12   12   60   12   48   36  132   84   60   36  |
  17   |   8  16   16   48   80   48   16  144  176  112  240  144  |
  19   |   9   6   36   18   90   36  144   18  198  252   90   36  |
  23   |  11  22   44   66   10  132  176  198   22  308  330  396  |
  29   |  14  28   28   12  140   84  112  252  308   28  420  252  |
  31   |  15  10   12   30   30   60  240   90  330  420   30  180  |
  37   |  18  12   36   36  180   36  144   36  396  252  180   36  |
   -   +   -   -    -    -    -    -    -    -    -    -    -    -  +

That values $f(pq)$ are nicely reproduced by $x_{p,q}$ according to the formula (3) up to $p,q \le 223$ and $p,q \in \Bbb P$


(Numbertheoretical) background
The function $f(n)$ stems from the problem to determine periodicity in the sequence $ S_n =\{k^k \}_{ k \gt 0} \pmod n$ depending on $n$. It is relatively easy to find that we'll have a period of length $L=\varphi(n^2)$ . But in many cases $n$ we find that there is a smaller period length, however it is always a divisor of $L$. The function $f(n)$ is that minimal period length (I determine that by analyzing the sequence $S_n$ empirically (only using Euler's totient function to simplify computation)). This is an analogon to the Carmichael function and to the "order of multiplicative cyclic subgroups".

For the basic problem see the MSE-question which I've linked already in the beginning of the post (they used "m" where I use "n" here).

$\endgroup$
  • $\begingroup$ Impossible to understand. $div(a,b,c,d) = c \, 1_{a | b} + d (1- 1_{a | b})$. So what is it supposed to correspond to ? What is supposed to be multiplicative ? $\endgroup$ – reuns Jul 25 '17 at 7:57
  • $\begingroup$ @reuns : tried to make the formula more transparent, see "update" $\endgroup$ – Gottfried Helms Jul 25 '17 at 8:44
  • $\begingroup$ @reuns: the question is as stated: "can this function be expressed in a simpler form?" The combination of $p-1$,$q-1$ and $\gcd()$ might have a simpler expression for instance using the totient function. Possibly the divide - clauses can be inserted by some algebraic term. Sometimes one does not see the obvious - and this might be the case here $\endgroup$ – Gottfried Helms Jul 25 '17 at 9:16
  • $\begingroup$ There seems to be some connection with the Carmichael function, en.wikipedia.org/wiki/Carmichael_function. At least, they coincide for the product of two odd primes. $\endgroup$ – Professor Vector Jul 25 '17 at 9:32
  • $\begingroup$ It is obvious there is no simple formula for $\frac{(p-1)(q-1)}{gcd(p-1,q-1)} = lcm(p-1,q-1)$. If $p,q$ are arbitrary integers then.. If you'd state a real number theory problem, it would help. $\endgroup$ – reuns Jul 25 '17 at 9:53
0
$\begingroup$

The idea of @reuns to introduce the $\text{lcm}()$ instead of the first fraction in (1) plus a bit rewriting seems to give the best answer, even generalizable to more primefactors.


For two different primefactors $p,q \in \Bbb P$ and $n=pq$ the value of $f(n)$ is now (and also better matching) decoded into $$ \begin{array} {rll} x_{p,q} &=& \displaystyle { \text{lcm}(p-1,q-1) \over \text{lcm}\left(\gcd(p-1,n / p),\gcd(q-1,n / q)\right) } \\[4ex] &\underset{\text{hypo}\\ \text{these}}{=\qquad} & f (n) \end{array} \tag 4$$ For some small $p,q \le 131 $ this is correct.

(Update 25.7.17) It seems, that even for powers of the primefactors $p,q$ the same formula can be used with small restrictions. Actually it seems that the formula needs restriction of the exponents in $p^e$ to $e \le p$.

On the other hand, according to heuristics for larger sets of primes (and their powers) we can simply generalize the formula.
Let's denote the number of primefactors $\omega$ and the involved primefactors $p_1,p_2,...,p_\omega$ and let's generalize the notion of the $\text{lcm}()$-function allowing a vector $A=[a_1,a_2,...,a_z]$ of a length $z$ as argument writing $\text{lcm}_{k=1}^z(a_k)$ then the formula must be rewritten: $$ \begin{array} {rll} \text{with } \quad n &= & \prod_{k=1}^\omega p_k^{e_k} &&\text{where } e_k \le p_k\\[4ex] x_{p_1,p_2,...p_\omega} &=& \displaystyle{ \text{lcm}_{k=1}^\omega(p_k-1) \over \text{lcm}_{k=1}^\omega \left( \gcd(p_k-1, n) \right) } \\[4ex] &\underset{\text{hypo}\\ \text{these}}{=\qquad} & f (n) \end{array} \tag 5$$ (for the larger $n$ which occur by this I have a probabilistic version of $f(n)$ which can handle $n$ with thirty or forty digits in-a-moment to test correctness of that formula for more complex compositions of primefactors.)


So it seems, the formula in version $(5)$ should be the best compactification of formula $(3)$ in the OP so far ...
... and the best candidate to proceed. Unfortunately for cases where $e_k>p_k$ I have not yet a simple correction.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.