8
$\begingroup$

Following is an experimental math claim.

We denote $(a,b)=\gcd(a,b)$.

Let $$G(a)=\sum_{i=1}^{a-1}(-1)^i(a,i).$$

Note:

$$ G(a) = \begin{cases} 0, & \text{if $a\equiv 1\pmod4$} \\ \text{odd}, & \text{if $a\equiv 2\pmod4$} \\ 0, & \text{if $a\equiv 3\pmod4$} \\ \text{even}, & \text{if $a\equiv 0\pmod4$.} \end{cases}$$

Can it be shown that for every $a\in\mathbb{Z}_{\ge2}$, $G(a)\ge-1$?

Table

$$\begin{array}{|c |c |} \hline a & G(a) \\ \hline 2 & -1 \\ \hline 3 & 0 \\ \hline 4 &0 \\ \hline 5 &0 \\ \hline 6 &-1 \\ \hline 7 &0 \\ \hline 8 &4 \\ \hline 9 &0 \\ \hline \vdots &\vdots \\ \hline \end{array}$$

source code PARI/GP

for(a=1,10000,if(sum(i=1,a-1, (-1)^i*gcd(a, i))<-1,print([a])))
$\endgroup$
4
  • $\begingroup$ This is somewhat like oeis.org/A106475 "An alternating sum of greatest common divisors". $\endgroup$ May 16 at 0:56
  • 2
    $\begingroup$ Also, $-(G(a) + (-1)^aa)$ gives oeis.org/A199084 $\endgroup$ May 16 at 14:23
  • 1
    $\begingroup$ Added this sequence as oeis.org/A344373 along with two related sequences. $\endgroup$ May 16 at 15:06
  • 1
    $\begingroup$ This question raises several further questions about iterates (which are probably very hard). For example, is 12 the unique $a$ with $G(G(G(a)))=0$, $G(G(a))\ne0$? Or, there seem to be many $a$ with $G(a)$, $G(G(a))$, $G(G(G(a)))$, ... never stabilizing. Can one actually prove that there is some such? In fact, it seems that $-1$, $0$ and $16$ are the only sinks. Is this so? Are there any periodic orbits of iterates? There also seem to be many $x$ with $G^{-1}(x)$ empty. Can one characterize those? $\endgroup$ May 16 at 16:02
14
$\begingroup$

Yes, it is true. Further we suppose that $a=2b$ is even, as for odd $a$ the sum $G(a)$ equals 0 due to pairing $\{i,a-i\}$.

We start with $$(a,i)=\sum_{d|(a,i)}\varphi(d)=\sum_{d|a} \varphi(d)\cdot \mathbf{1}_{d|i}.$$ Therefore $$ G(a)=\sum_{i=1}^{a-1}(-1)^i(a,i)=\sum_{d|a}\varphi(d)\sum_{i=1}^{a-1}(-1)^i \mathbf{1}_{d|i}. $$ The inner sum $\sum_{i=1}^{a-1}(-1)^i \mathbf{1}_{d|i}$ equals $a/d-1$ if $d$ is even and equals $-1$ if $d$ is odd (since it is a sum of $a/d-1=2b/d-1$ alternating $\pm 1$'s). Thus $$G(a)=\sum_{d|a,d\,\text{is even}} \varphi(d)(a/d-1)-\sum_{d|a,d\,\text{is odd}}\varphi(d).$$ Denote $b=2^sc$ for non-negative integer $s$ and odd $c$. Then odd divisors of $a$ are exactly divisors of $c$, and we have $$ \sum_{d|a,d\,\text{is odd}}\varphi(d)=\sum_{d|c}\varphi(d)=c. $$ If 4 divides $a$, then $a/(2d)-1\geqslant 1$ for each divisor $d$ of $c$, and we get $$ \sum_{d|a,d\,\text{is even}} \varphi(d)(a/d-1)\geqslant \sum_{d|c} \varphi(2d)(a/(2d)-1)\geqslant \sum_{d|c} \varphi(2d)=\sum_{d|c} \varphi(d)=c, $$ thus $G(a)\geqslant 0$. Finally, it remains to consider the case when $b=c$ is odd. Then we have $$ \sum_{d|a,d\,\text{is even}} \varphi(d)(a/d-1)=\sum_{d|c} \varphi(2d)(a/(2d)-1)= \sum_{d|c}\varphi(d)(c/d-1)=-c+c\sum_{d|c} \varphi(d)/d, $$ and $G(a)\geqslant -1$ reads as $$c\sum_{d|c} \varphi(d)/d\geqslant 2c-1.$$ This may be proved by $$ \sum_{d|c} \varphi(d)/d=1+\sum_{d|c,d>1} \varphi(d)/d\geqslant 1+ \sum_{d|c,d>1} \varphi(d)/c=1+(c-1)/c=(2c-1)/c. $$

$\endgroup$
2
  • $\begingroup$ Thanks for answer. please explain, what this ${\bf 1}_{d|i}$ represent ? $\endgroup$
    – Pruthviraj
    May 16 at 4:11
  • 2
    $\begingroup$ That is the indicator function: 1 if $d$ divides $i$ and 0 otherwise. $\endgroup$ May 16 at 4:35
5
$\begingroup$

$$G(a)+(-1)^aa=\sum_{i=1}^{a} (-1)^i (a,i)=\sum_{d|a} d \sum_{\substack{ l \\ (l, a/d)=1}} (-1)^{dl}=T(a).$$

When, $a$ is odd, $d, a/d$ is also odd. Hence, $$\sum_{\substack{l, \\ (l,a/d)=1 \\ d<a}} (-1)^l =0.$$ So, $T(a)=(-1)^aa \rightarrow G(a)=0$.

Now, for $a=2^{r_0}m, m=\prod_{i=1}^s p_i^{r_i}$ odd, $$ T(a)=\sum_{\text{$d$ even}} d\phi(a/d) - \sum_{\text{$d$ odd}} d\phi(a/d) $$ (because, for $d$ even $(-1)^d=1$, and for $d$ odd, $a/d$ even, so $l, dl$ is odd). \begin{align*} & {}=a\sum_{l\mid\frac{a}{2}} \frac{\phi(l)}{l}-\sum_{l \mid m}\frac{\phi(2^rl)}{2^rl} \\ & {}=a(\sum_{l\mid\frac{a}{2}} \frac{\phi(l)}{l}-\frac{1}{2}\sum_{l|m}\frac{\phi(l)}{l}). \end{align*} Now, $\sum_{d\mid n} \frac{\phi(d)}{d}=\prod_{i} (1+(1-\frac{1}{p_i})r_i)$, where $n=\prod_i p_i^{r_i}$.

Using this to the sum we get, the explicit formula for $G(a)$: $$ G(a)=\frac{ar_0}{2p_1p_2\dotsm p_s}\prod_{i=1}^{s} (p_i(r_i+1)-r_i) -a. $$

It's easy to see from the formula that $G(a)$ is odd when $r_0=1$ and even when $r_0>1$, because all $p_i$ are odd, hence each $p_i(r_i+1)-r_i$ is odd, and $a$ is even.

More compactly, $G(a)=a[\frac{r_0}{2}\prod_{i=1}^{s} (r_i+1-\frac{r_i}{p_i})-1]$.

Surely, $G(a) \geq -1$. It's $-1$, for $a=2p$ types, e.g. $a=6$.

$\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.