Open Question: For natural $n$ with prime decomposition $\prod p_i^{r_i}$, define $f(n)=\sum p_i r_i$. Find all $n$ such that $f(n)-f(n+1)=1$.

109 Views Asked by At

A question I created myself:

For any $n\in \Bbb{N}$, we can get $n = p_1^{r_1}\cdots p_m^{r_m}$, where $p_i$ are primes. Take $$f(n)=p_1r_1+\cdots+p_mr_m$$ Find all $n$ such that $f(n)-f(n+1)=1$

It may be an open question, but could anyone help me to solve it?

EDIT:

for n = 7, n = $1\times7$, so f(7)=7, and n+1 = $2^3$, then f(8)=$2\times 3$=6. Therefore, since f(7)-f(8)=1, then n=7 is a solution.

1

There are 1 best solutions below

0
On

I felt like playing a little, here are some ideas that are too long for a comment. I generalize $f$ to rational numbers and then from this perspective all solutions are related to each other by rational numbers of a certain form described below. I also give a separate approach at the end.


We can rewrite $f$ in terms of the p-adic valuation summing over all primes $p$.

$$f(n)=\sum_ppv_p(n)$$

Since a rational number only ever has finitely many prime factors, there are never more than finitely many nonzero terms. Furthermore, this means we can extend the domain of $f$ to all nonzero rational numbers and it will still be well defined.

Because the p-adic valuation is completely additive, $f$ inherits this property as well, so we have the identities such as $f(xy)=f(x)+f(y)$ and $f(\frac{1}{x})=-f(x)$.


The original problem may now be rewritten as $f\left(1+\frac{1}{n}\right)=-1$ asking for which integer $n$ this is true.

Now suppose we have two solutions $m,n$ such that

$$f\left(1+\frac{1}{n}\right)=f\left(1+\frac{1}{m}\right)=-1$$

This means we have,

$$f\left(1+\frac{1}{n}\right)-f\left(1+\frac{1}{m}\right)=0$$ $$f\left(\frac{1+\frac{1}{n}}{1+\frac{1}{m}}\right)=0$$

So there is a rational $x$ of the form $x=\frac{1+\frac{1}{n}}{1+\frac{1}{m}}$ that is a solution to $f(x)=0$. We can solve for $m$ in terms of $n,x=\frac{a}{b}$ as,

$$m=\frac{bn}{(a-b)n+a}$$ Since we already have a solution $n=7$, we can now focus on finding rational $x$ such that $f(x)=0$, because this is a necessary - although not sufficient - condition to generate another solution $m$ from $n=7$ so that $f\left(1+\frac{1}{m}\right)=-1$.


Now how can we find rational solutions to $f(x)=0$? From this formula, it isn't difficult to generate many,

$$0=\sum_ppv_p(x)$$

To generate all solutions to this, we need two disjoint sets of prime numbers and make positive integer linear combinations that they add to the same number. For instance the sets $\{3,5\}$ and $\{2\}$ we can make $1*3+1*5=4*2$. Since they really correspond to $3v_3(x)+5v_5(x)=2v_2(x)$ with $v_3(x)=1$, $v_5(x)=1$, and $v_2(x)=-4$ we have constructed $x=\frac{15}{16}$ with $f(x)=0$.

Using our formula for $m$ above, we have with $n=7$,

$$m=\frac{bn}{(a-b)n+a}=\frac{16*7}{(15-16)7+15}=14$$

As a reminder, having $x$ satisfy $f(x)=0$ is only a necessary, but not sufficient condition to getting a solution. The sad fact is I cooked this example up using A020700 in Sil's comment above.


As a final separate approach altogether, we can invent this new "promotion" function $g(x)$ which takes the rational number $x$'s prime factorization and "promotes it" by replacing every prime $p$ with $p^p$, $$x=\prod_p p^{v_p(x)}$$ $$g(x)=\prod_p p^{pv_p(x)}$$

Now the original function $f$ may be written in terms of the number of prime factors function $\Omega(x)=\sum_pv_p(x)$ with the promoted $x$ as,

$$f(x)=\Omega(g(x))$$

This means we can think about solutions to the problem,

$$\Omega(g(x))-\Omega(g(x+1))=1$$

Then we care about when the difference in number of prime factors between the promoted $x$ and $x+1$ is $1$.

Maybe that's too cumbersome to be useful, but tying it back into a more well studied function $\Omega$ might lead into other ideas.