Product of Some Polynomials and Arithmetic Functions

Passawan Noppakaew Department of Mathematics

Faculty of Science Silpakorn University Nakhon Pathom, 73000

Thailand

noppakaew p@silpakorn.edu

Prapanpong Pongsriiam^{1} Department of Mathematics

Faculty of Science Silpakorn University Nakhon Pathom, 73000

Thailand

and

Graduate School of Mathematics Nagoya University Nagoya, 464-8602 Japan

pongsriiam p@silpakorn.edu, prapanpong@gmail.com

1Prapanpong Pongsriiam is the corresponding author.

Abstract

We study the injectivity and noninjectivity of the function fg, where f is a polynomial in a simple form and g is a popular arithmetic function such as the Euler totient function or the sum of divisors function. We also show the connection between our results and Mersenne primes, amicable pairs, and other integer sequences.

1 Introduction

For each n ∈ ℕ, let φ(n) be the number of positive integers that are at most n and relatively prime to n, and let σ(n) be the sum of positive divisors of n. The functions φ and σ are connected with some popular topics such as Lehmer’s problem, Carmichael’s conjecture, perfect numbers, Mersenne primes, amicable pairs, and aliquot sequences. For example, it is easy to see that if n is a prime, then φ(n) = n−1. Lehmer asked whether φ(n) | n−1 implies that n is a prime, but this question is still open. In addition, Carmichael’s long-standing open conjecture on the range of φ states that if φ(x) = n, then there exists y ∈ ℕ distinct from x such that φ(y) = n too. Moreover, whether or not there are infinitely many n ∈ ℕ with σ(n) = 2n and whether or not there exists an odd integer n with σ(n) = 2n have been open for a long time.

Many mathematicians including Ford [2, 3], Ford, Luca, and Pomerance [4], Ford and Pollack [5], and Pomerance [7] have contributed to the progress of this area of research. In particular, Ford [3] solved Sierpiński’s conjecture and partially solved Carmichael’s problem stated above. That is, Ford showed that for each integer k ≥ 2, there exists a positive integer n for which the equation φ(x) = n has exactly k solutions. Furthermore, Ford, Luca, and Pomerance [4] completely answered Erdős’ question on the ranges of φ and σ by showing that φ(x) = σ(y) has infinitely many solutions in x, y ∈ ℕ. We refer the reader to the sequences \underline{A000010} and \underline{A007617} in the On-Line Encyclopedia of Integer Sequences (OEIS)

[9] for more information on the range of φ, the sequences \underline{A000396} and \underline{A000668} for perfect numbers and Mersenne primes, and the sequences \underline{A063990}, \underline{A063900}, \underline{A001065}, \underline{A008888}, and \underline{A098007} for amicable pairs and aliquot sequences.

It is well known that the function φ is not injective but the function f_{0} defined by f_{0}(n) = nφ(n) is injective. Not every function has this property: both σ and the function A(n) = nσ(n) are not injective. Nevertheless, we show in Examples 7 and 8 and Theorem 12 that A is injective on squarefree integers and both A and σ are related to Mersenne primes and amicable pairs. Generally speaking, both injectivity and noninjectivity are interesting; if an arithmetic function f is injective, we can conclude that the equation f(x) = n has at most one solution; if f is not injective, then we may like to count the number of solutions to f(x) = n, and study the relation between f and each solution.

In this article, we study the injectivity and noninjectivity of the product of polynomials and arithmetic functions. We will replace nφ(n) and nσ(n) by g(n)h(n) where g(n) is a polynomial and h(n) is an arithmetic function. For simplicity, we focus our attention to polynomials in a simple form such as g(n) = n^{a} or g(n) = n + c where a, c are any positive integers, while h(n) is a popular arithmetic function such as φ(n), σ(n), d(n), s(n), ω(n), Ω(n), S_{b}(n), ψ(n), and J_{s}(n), where d(n) is the number of positive divisors of n, s(n) = σ(n) − n is the sum of proper divisors of n, ω(n) is the number of distinct prime divisors of n, Ω(n) is the number of prime divisors of n counted with multiplicity, S_{b}(n) is the sum of digits of n when n is written in base b, ψ(n) is the Dedekind function, and J_{s}(n) is Jordan’s totient function. The functions ψ and J_{s} are defined by

ψ(n) = n ∏_{p|n}(1 + \frac{1}{p}) and J_{s}(n) = n^{s} ∏_{p|n}(1 − \frac{1}{p^{s}}),

where s is a positive integer. For more information about injectivity or noninjectivity of arithmetic functions, see for example in Guy’s book [6, Section B], Pongsriiam’s recent article [8], and the online database OEIS [9].

We organize this article as follows. In Section 2, we prove some results on injectivity of the function gh where g is a polynomial in a simple form and h = φ, ψ, and J_{s}. In Section 3, we show the noninjectivity of gh and a connection to other problems when h = σ, s, d, ω, Ω, and S_{b}. In Section 4, we study the injectivity of gh where g and h are restricted to squarefree integers. In fact, in Sections 1–4, the function g is of the form g(n) = n^{a}, but in Section 5, we set g(n) = n + c where c is a positive integer. We obtain in Section 5 that the function n ↦ (n + c)φ(n) is not injective for infinitely many c ∈ ℕ. We also provide some related results in Section 6. Finally, we give a list of open questions in Section 7.

2 Results on injectivity

In this section, we show that the product of φ, ψ, and J_{s} with a polynomial in a simple form are injective. Recall that an arithmetic function f is said to be multiplicative if f(1) = 1 and f(mn) = f(m)f(n) for all m, n ∈ ℕ with (m, n) = 1. It is well known that φ, σ, d, ψ, and J_{s} are multiplicative. The following formulas are also well known and may be used throughout this article:

φ(n) = n ∏_{p|n}(1 − \frac{1}{p}), ψ(n) = n ∏_{p|n}(1 + \frac{1}{p}), J_{s}(n) = n^{s} ∏_{p|n}(1 − \frac{1}{p^{s}}),

d(n) = ∏_{p^{α}||n}(α + 1), σ(n) = ∏_{p^{α}||n}(1 + p + p^{2} + ⋯ + p^{α}) = ∏_{p^{α}||n} (\frac{p^{α+1} − 1}{p − 1}).

We begin our study with φ. Although it is well known that the function n ↦ nφ(n) is injective, we can extend it to the following form.

Theorem 1. For each a, b ∈ ℕ, the arithmetic function F defined by F (n) = n^{a}φ(n)^{b} for all n ∈ ℕ is an injective function. In particular, the function f_{0} is injective.

Proof. To show that F is injective, let m, n ∈ ℕ and F (m) = F (n). If m = 1, then n^{a}φ(n)^{b} = F (n) = F (1) = 1, which implies n = 1. Similarly, if n = 1, then m = 1. Therefore m = 1 if and only if n = 1. So we assume that m, n ≥ 2. Let

m = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{k}^{m_{k}} and n = q_{1}^{n_{1}}q_{2}^{n_{2}} ⋯ q_{ℓ}^{n_{ℓ}},

where p_{1} < p_{2} < ⋯ < p_{k}, q_{1} < q_{2} < ⋯ < q_{ℓ} are primes and m_{i}, n_{j} are positive integers for all i, j. By the well known formula for φ and the fact that F (m) = F (n), we obtain

∏_{i=1}^{k} p_{i}^{am_{i}+b(m_{i}−1)} ∏_{i=1}^{k}(p_{i} − 1)^{b} = ∏_{i=1}^{ℓ} q_{i}^{an_{i}+b(n_{i}−1)} ∏_{i=1}^{ℓ}(q_{i} − 1)^{b}.  (1)

For convenience, we write LHS and RHS to denote the left-hand side and the right-hand side of (1), respectively. Suppose that p_{k} ≥ q_{ℓ}. Since the exponent of p_{k} in LHS is at least 2m_{i} − 1 ≥ 1, we see that p_{k} divides LHS. So p_{k} divides RHS too. Since p_{k} does not divide q_{i}−1 and q_{j} for any i = 1, 2, …, ℓ and j = 1, 2, …, ℓ−1, we see that p_{k} divides q_{ℓ}. So p_{k} = q_{ℓ}. Similarly, if p_{k} ≤ q_{ℓ}, then we start with the fact that q_{ℓ} divides RHS, and so q_{ℓ} divides LHS too, which leads to q_{ℓ} = p_{k}. In any case p_{k} = q_{ℓ}. Furthermore, by the unique factorization, the exponent of p_{k} and q_{ℓ} are the same. Therefore am_{k} + b(m_{k} − 1) = an_{ℓ} + b(n_{ℓ} − 1), which implies m_{k} = n_{ℓ}. Thus (1) reduces to

∏_{i=1}^{k−1} p_{i}^{am_{i}+b(m_{i}−1)} ∏_{i=1}^{k−1}(p_{i} − 1)^{b} = ∏_{i=1}^{ℓ−1} q_{i}^{an_{i}+b(n_{i}−1)} ∏_{i=1}^{ℓ−1}(q_{i} − 1)^{b}.  (2)

We observe that (2) is obtained from (1) by the change of k to k − 1 and ℓ to ℓ − 1. So we can use the same argument to conclude that p_{k−1} = q_{ℓ−1} and m_{k−1} = n_{ℓ−1}. Doing this process repeatedly, it will eventually stop. If k < ℓ, then it leads to the equation 1 = R where R is divisible by q_{1}, which is a contradiction. Similarly, the inequality k > ℓ is not possible. Therefore k = ℓ. So when the process stops, we obtain k = ℓ, p_{i} = q_{i}, and m_{i} = n_{i} for all i. Therefore m = n, as required.

Since ψ(n) and φ(n) are similar, we expect that the function n ↦ nψ(n) should also be injective. Nevertheless, there is a little problem with the primes 2 and 3. So we first prove the following lemma.

Lemma 2. For each a, b ∈ ℕ, let F be the arithmetic function defined by F (n) = n^{a}ψ(n)^{b} for all n ∈ ℕ. Let m ∈ ℕ and r, s ∈ ℕ ∪ {0}. If F (m) = F (2^{r}3^{s}), then m = 2^{r}3^{s}.

Proof. If r = s = 0, then F (m) = F (1) = 1, which implies m = 1 = 2^{r}3^{s}. So assume that r ≠ 0 or s ≠ 0. By the definition of F and the formula for ψ, we observe that each x, y ∈ ℕ, we have

F (2^{x}) = 2^{xa+xb−b}3^{b}, F (3^{y}) = 2^{2b}3^{ya+yb−b}, and F (2^{x}3^{y}) = 2^{xa+xb+b}3^{ya+yb}.  (3)

Therefore if p is a prime factor of m, then p also divides F (m) = F (2^{r}3^{s}), and so p ≤ 3. Thus m = 2^{u}3^{v} for some nonnegative integers u and v.

Case 1: r = 0. Then s ≠ 0 and F (m) = F (2^{r}3^{s}) = F (3^{s}) = 2^{2b}3^{sa+sb−b}. Suppose, by way of contradiction, that v = 0. Then 2^{ua+ub−b}3^{b} = 2^{2b}3^{sa+sb−b}, which implies that ua + ub = 3b and sa + sb = 2b. Since sa + sb = 2b, we have s = 1 and a = b. Then 2ub = ua + ub = 3b which is not possible. Thus v ≠ 0. If u ≠ 0, then we have that 2^{ua+ub+b}3^{va+vb} = 2^{2b}3^{sa+sb−b}, which implies b = ua + ub > b, a contradiction. So u = 0 and 2^{2b}3^{va+vb−b} = 2^{2b}3^{sa+sb−b}. This implies that v = s and m = 3^{s} = 2^{r}3^{s}.

Case 2: s = 0. Then r ≠ 0. By using an argument similar to Case 1, one can show that m = 2^{r} = 2^{r}3^{s}.

Case 3: r ≠ 0 and s ≠ 0. Then F (m) = 2^{ra+rb+b}3^{sa+sb}. By considering (3) and the exponents of 2 and 3 in F (m), we see that u ≠ 0 and v ≠ 0. This implies that 2^{ua+ub+b}3^{va+vb} = 2^{ra+rb+b}3^{sa+sb}. Then u = r, v = s, and so m = 2^{r}3^{s}. This completes the proof.

Theorem 3. For each a, b ∈ ℕ, the arithmetic function F defined by F (n) = n^{a}ψ(n)^{b} for all n ∈ ℕ is an injective function.

Proof. To show that F is injective, let m, n ∈ ℕ and F (m) = F (n). It is easy to see that m = 1 if and only if n = 1. So we assume that m, n ≥ 2. Let

m = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{k}^{m_{k}} and n = q_{1}^{n_{1}}q_{2}^{n_{2}} ⋯ q_{ℓ}^{n_{ℓ}},

where p_{1} < p_{2} < ⋯ < p_{k}, q_{1} < q_{2} < ⋯ < q_{ℓ} are primes and m_{i}, n_{j} are positive integers for all i, j. Since F (m) = F (n), we obtain

∏_{i=1}^{k} p_{i}^{am_{i}+b(m_{i}−1)} ∏_{i=1}^{k}(p_{i} + 1)^{b} = ∏_{i=1}^{ℓ} q_{i}^{an_{i}+b(n_{i}−1)} ∏_{i=1}^{ℓ}(q_{i} + 1)^{b}.  (4)

For simplicity, we write LHS and RHS to denote the left-hand side and the right-hand side of (4), respectively. If p_{k} ≤ 3, then Lemma 2 implies that m = n. So assume that p_{k} > 3. Suppose that p_{k} ≥ q_{ℓ}. Since the exponent of p_{k} in LHS is at least 2m_{k} − 1 ≥ 1, we see that p_{k} divides LHS. So p_{k} divides RHS too. Since p_{k} > 3, we see that p_{k} does not divide q_{i} + 1 and q_{j} for any i = 1, 2, …, ℓ and j = 1, 2, …, ℓ − 1. Then p_{k} divides q_{ℓ}, and so p_{k} = q_{ℓ}. Similarly, if p_{k} ≤ q_{ℓ}, then we start with the fact that q_{ℓ} divides RHS, and so q_{ℓ} divides LHS too, which leads to q_{ℓ} = p_{k}. In any case p_{k} = q_{ℓ}. Furthermore, by the unique factorization, the exponent of p_{k} and q_{ℓ} are the same. Therefore am_{k} + b(m_{k} − 1) = an_{ℓ} + b(n_{ℓ} − 1), which implies m_{k} = n_{ℓ}. Thus (4) reduces to

∏_{i=1}^{k−1} p_{i}^{am_{i}+b(m_{i}−1)} ∏_{i=1}^{k−1}(p_{i} + 1)^{b} = ∏_{i=1}^{ℓ−1} q_{i}^{an_{i}+b(n_{i}−1)} ∏_{i=1}^{ℓ−1}(q_{i} + 1)^{b}.  (5)

We observe that (5) is obtained from (4) by the change of k to k − 1 and ℓ to ℓ − 1. If p_{k−1} ≤ 3, then we apply Lemma 2 to obtain m = n. If p_{k−1} > 3, then we repeat the above process and reduce (5) by the change of k − 1 to k − 2 and ℓ − 1 to ℓ − 2. By repeating this process, we eventually obtain m = n. This completes the proof.

Similar result also holds when the function φ is replaced by J_{2} as shown below.

Lemma 4. For each a, b ∈ ℕ, let F be the arithmetic function defined by F (n) = n^{a}J_{2}(n)^{b} for all n ∈ ℕ. Let m ∈ ℕ and r, s ∈ ℕ ∪ {0}. If F (m) = F (2^{r}3^{s}), then m = 2^{r}3^{s}.

Proof. Since this lemma can be proved in the same way as Lemma 2, we skip some details. If r = s = 0, then m = 2^{r}3^{s}. So assume that r ≠ 0 or s ≠ 0. If p is a prime factor of m, then p also divides F (m) = F (2^{r}3^{s}), and so p ≤ 3. Thus m = 2^{u}3^{v} for some nonnegative integers u and v.

First, assume that r = 0. Then s ≠ 0 and F (m) = 2^{3b}3^{sa+2sb−2b}. If v = 0, then 2^{ua+2ub−2b}3^{b} = F (m) = 2^{3b}3^{sa+2sb−2b}, which implies that ua + 2ub = 5b and sa + 2sb = 3b. Since sa+2sb = 3b, we have that s = 1 and a = b. Then 3ub = ua+2ub = 5b, a contradiction. Thus v ≠ 0. From this point, we can still consider the exponents of 2 and 3 like the proof of Lemma 2 to obtain m = n. For the cases s = 0 or (r ≠ 0 and s ≠ 0), we can also compare the exponents of 2 and 3 to obtain the desired result. So the proof is completed.

Next, we show that for certain a, b ∈ ℕ, the function n ↦ n^{a}J_{s}(n)^{b} is injective. When s = 2, we can use any positive integers a, b as follows.

Theorem 5. For each a, b ∈ ℕ, the arithmetic function F defined by F (n) = n^{a}J_{2}(n)^{b} for all n ∈ ℕ is injective.

Proof. Since the proof of this theorem follows the same argument as in Theorem 3, we skip some details. Let m, n ∈ ℕ and F (m) = F (n). It is easy to see that m = 1 if and only if n = 1. So we assume that m, n ≥ 2. Let

m = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{k}^{m_{k}} and n = q_{1}^{n_{1}}q_{2}^{n_{2}} ⋯ q_{ℓ}^{n_{ℓ}},

where p_{1} < p_{2} < ⋯ < p_{k}, q_{1} < q_{2} < ⋯ < q_{ℓ} are primes and m_{i}, n_{j} are positive integers for all i, j. Then

∏_{i=1}^{k} p_{i}^{am_{i}+2b(m_{i}−1)} ∏_{i=1}^{k}(p_{i}^{2} − 1)^{b} = ∏_{i=1}^{ℓ} q_{i}^{an_{i}+2b(n_{i}−1)} ∏_{i=1}^{ℓ}(q_{i}^{2} − 1)^{b}.  (6)

For convenience, we write LHS and RHS to denote the left-hand side and the right-hand side of (6), respectively. If p_{k} ≤ 3, then Lemma 4 implies that m = n. So assume that p_{k} > 3. Suppose that p_{k} ≥ q_{ℓ}. Since the exponent of p_{k} in LHS is at least 3m_{i} − 2 ≥ 1, we see that p_{k} divides LHS. So p_{k} divides RHS too. Since p_{k} does not divide q_{i} − 1, q_{i} + 1, and q_{j} for any i = 1, 2, …, ℓ and j = 1, 2, …, ℓ − 1, we see that p_{k} divides q_{ℓ}. So p_{k} = q_{ℓ}. Similarly, if p_{k} ≤ q_{ℓ}, then this leads to p_{k} = q_{ℓ} and m_{k} = n_{ℓ}. Thus (6) reduces to

∏_{i=1}^{k−1} p_{i}^{am_{i}+2b(m_{i}−1)} ∏_{i=1}^{k−1}(p_{i}^{2} − 1)^{b} = ∏_{i=1}^{ℓ−1} q_{i}^{an_{i}+2b(n_{i}−1)} ∏_{i=1}^{ℓ−1}(q_{i}^{2} − 1)^{b}.  (7)

We observe that (7) is obtained from (6) by the change of k to k − 1 and ℓ to ℓ − 1. So we can repeat this process like the proof of Theorem 3 to obtain m = n, as required.

When s ≥ 3, it seems that the function n ↦ n^{a}J_{s}(n)^{b} is injective for any a, b ∈ ℕ, but we do not have a proof. In the following theorem, we need to restrict ourselves to the case a ≥ sb, but we hope to solve the case a < sb in the future. Please see also our comments and the list of other problems in Section 7.

Theorem 6. For each a, b, s ∈ ℕ, if a ≥ sb, then the arithmetic function F defined by F (n) = n^{a}J_{s}(n)^{b} for all n ∈ ℕ is injective.

Proof. For each n ∈ ℕ, let P_{n} be the set of all prime factors of n. Let a, b, s ∈ ℕ and a ≥ sb. We remark that we do not need to use the inequality a ≥ sb until the calculation in (10). To show that F is injective, let m, n ∈ ℕ and F (m) = F (n). It is easy to see that m = 1 if and only if n = 1. So we assume that m, n ≥ 2. We will first show that P_{m} = P_{n}. So suppose, by way of contradiction, that P_{m} ≠ P_{n}.

Case 1: P_{m} ⊆ P_{n} and P_{n} ⊈ P_{m}. Let

m = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{k}^{m_{k}} and n = p_{1}^{n_{1}}p_{2}^{n_{2}} ⋯ p_{k}^{n_{k}}q_{1}^{n_{k+1}}q_{2}^{n_{k+2}} ⋯ q_{ℓ}^{n_{k+ℓ}},

where p_{1} < p_{2} < ⋯ < p_{k} and q_{1} < q_{2} < ⋯ < q_{ℓ} are primes, k, ℓ ≥ 1, p_{i} ≠ q_{j}, and m_{i}, n_{j} are positive integers for all i, j. After dividing both sides of the equation F (m) = F (n) by

∏_{i=1}^{k}(p_{i}^{s} − 1)^{b}, we obtain

∏_{i=1}^{k} p_{i}^{am_{i}+sb(m_{i}−1)} = ∏_{i=1}^{k} p_{i}^{an_{i}+sb(n_{i}−1)} ∏_{i=1}^{ℓ} q_{i}^{an_{k+i}+sb(n_{k+i}−1)} ∏_{i=1}^{ℓ}(q_{i}^{s} − 1)^{b}.  (8)

Then q_{1} divides the right-hand side of (8) but does not divide the left-hand side. So this case leads to a contradiction.

Case 2: P_{n} ⊆ P_{m} and P_{m} ⊈ P_{n}. Similar to Case 1, this leads to a contradiction.

Case 3: P_{m} ⊈ P_{n} and P_{n} ⊈ P_{m}. Let

m = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{k}^{m_{k}} (∏_{i=1}^{t} w_{i}^{u_{i}}) and n = q_{1}^{n_{1}}q_{2}^{n_{2}} ⋯ q_{ℓ}^{n_{ℓ}} (∏_{i=1}^{t} w_{i}^{v_{i}}),

where p_{1} < p_{2} < ⋯ < p_{k}, q_{1} < q_{2} < ⋯ < q_{ℓ}, and w_{1} < w_{2} < ⋯ < w_{t} are primes, p_{i}, q_{j}, w_{x} are distinct for all i, j, x, and m_{i}, n_{j}, u_{x}, v_{y} are positive integers for all i, j, x, y. In addition, if P_{m} ∩ P_{n} = ∅, then we take t = 0 and define the empty product to be 1 as usual; if P_{m} ∩ P_{n} ≠ ∅, then t ≥ 1. By the fact that F (m) = F (n), we obtain

∏_{i=1}^{t} w_{i}^{au_{i}+sb(u_{i}−1)} ∏_{i=1}^{k} p_{i}^{am_{i}+sb(m_{i}−1)} ∏_{i=1}^{k}(p_{i}^{s} − 1)^{b} = ∏_{i=1}^{t} w_{i}^{av_{i}+sb(v_{i}−1)} ∏_{i=1}^{ℓ} q_{i}^{an_{i}+sb(n_{i}−1)} ∏_{i=1}^{ℓ}(q_{i}^{s} − 1)^{b}.

(9)

Let L_{1} = ∏_{i=1}^{k} p_{i}^{am_{i}+sb(m_{i}−1)}, L_{2} = ∏_{i=1}^{k}(p_{i}^{s} − 1)^{b}, R_{1} = ∏_{i=1}^{ℓ} q_{i}^{an_{i}+sb(n_{i}−1)}, and R_{2} = ∏_{i=1}^{ℓ}(q_{i}^{s} − 1)^{b}. Since p_{i}, q_{j}, and w_{x} are all distinct, (9) implies that L_{1}|R_{2} and R_{1}|L_{2}. Recall that a ≥ sb. Then

L_{1} ≤ R_{2} < ∏_{i=1}^{ℓ} q_{i}^{sb} ≤ R_{1} ≤ L_{2} < ∏_{i=1}^{k} p_{i}^{sb} ≤ L_{1},  (10)

which is a contradiction.

Therefore we can conclude that P_{m} = P_{n}. Let

m = p_{1}^{m_{1}}p_{2}^{m_{2}} ⋯ p_{k}^{m_{k}} and n = p_{1}^{n_{1}}p_{2}^{n_{2}} ⋯ p_{k}^{n_{k}},

where p_{1} < p_{2} < ⋯ < p_{k} are primes and m_{i}, n_{j} are positive integers for all i, j. By the fact that F (m) = F (n), we obtain

∏_{i=1}^{k} p_{i}^{am_{i}+sb(m_{i}−1)} = ∏_{i=1}^{k} p_{i}^{an_{i}+sb(n_{i}−1)}.

By the unique factorization, we obtain m_{i} = n_{i} for all i, and so m = n, as required.

3 Noninjectivity and a connection with other concepts

Not every arithmetic function has the property like φ, ψ, and J_{s}. In this section, we give various examples to show that if we replace φ by other arithmetic functions f, the function n ↦ nf(n) may not be injective. We also give some connections to other problems such as the existence or nonexistence of infinitely many Mersenne primes, amicable pairs, and primitive solutions to certain equations.

Example 7. Let A(n) = nσ(n) for all n ∈ ℕ. A straightforward calculation shows that A(12) = A(14) = 2^{4} · 3 · 7, and so A is not injective. In fact, we can generate infinitely many x, y ∈ ℕ such that A(x) = A(y) using the equality A(12) = A(14). Let x = 12d and y = 14d where (d, 42) = 1. It is easy to see that A is multiplicative and (d, 14) = (d, 12) = 1, and so A(x) = A(12d) = A(12)A(d) = A(14)A(d) = A(14d) = A(y). Since there are infinitely many d ∈ ℕ with (d, 42) = 1, we obtain infinitely many x, y ∈ ℕ such that A(x) = A(y) too. From this, it is easy to see that if we can find another pair of integers x_{0}, y_{0} such that A(x_{0}) = A(y_{0}), then we can generate infinitely many such pairs by following the above method.

Moser [6, p. 102] asked whether there is an infinite number of primitive solutions to the equation A(x) = A(y), that is, the integers x, y ≥ 1 such that A(x) = A(y) and A(x/d) ≠ A(y/d) for any common divisor d > 1 of x and y. A conditional answer is known: if 2^{p} − 1 and 2^{q} − 1 are distinct Mersenne primes, then x = 2^{p−1}(2^{q} − 1) and y = 2^{q−1}(2^{p} − 1) is a primitive solution to A(x) = A(y). To see this, recall that if 2^{n} − 1 is a prime, then n is a prime too. Therefore we have p, q, 2^{p} − 1, 2^{q} − 1 are primes. Without loss of generality, assume that p > q. Then

A(x) = 2^{p−1}(2^{q} − 1)σ(2^{p−1})σ(2^{q} − 1)
= 2^{p−1}(2^{q} − 1)(2^{p} − 1)(2^{q})
= 2^{p+q−1}(2^{p} − 1)(2^{q} − 1).

By a similar calculation, we see that A(y) = A(x). Since 2^{p} − 1 and 2^{q} − 1 are distinct odd primes, the greatest common divisor of x and y is 2^{q−1}. So if d > 1, d | x, and d | y, then d = 2^{ℓ} for some ℓ = 1, 2, …, q − 1. By a similar calculation, we obtain

A (\frac{x}{d}) = 2^{p+q−ℓ−1}(2^{p−ℓ} − 1)(2^{q} − 1) and A (\frac{y}{d}) = 2^{p+q−ℓ−1}(2^{q−ℓ} − 1)(2^{p} − 1).

From this, we see that 2^{p} − 1 divides A(\frac{y}{d}) but does not divide A(\frac{x}{d}). So A(\frac{x}{d}) ≠ A(\frac{y}{d}). This shows that x, y is indeed a primitive solution to the equation A(x) = A(y). Nevertheless, since we do not know whether or not there are infinitely many Mersenne primes, this is only a conditional solution to Moser’s problem. Without restricting to primitive solutions, Erdős [1] showed that the number of m, n ∈ ℕ satisfying m < n < x and mσ(m) = nσ(n) is asymptotic to cx as x → ∞, where c is a positive constant. For more information on the equation A(x) = A(y), we refer the reader to Guy’s book [6, Section B11]. The sequence (A(n))_{n≥1} is registered in the OEIS as the sequence \underline{A064987}. Moreover, the sequence of n ∈ ℕ such that A(x) = n has more than one solution is \underline{A337873} in the OEIS. Some such integers n and distinct x_{1}, x_{2} such that A(x_{1}) = A(x_{2}) = n are shown in Table 2. We remark that n and x_{2} in our table are not listed in an increasing order, but the integer x_{1} is listed in an increasing order. The reader can also find more related information in the sequence \underline{A212490} and our comments in Section 7.

Example 8. Let s(n) = σ(n) − n be the sum of proper positive divisors of n and let B(n) = ns(n) for all n ∈ ℕ. It is not difficult to check that s(6) = 6 and s(9) = 4, and so B(6) = B(9). So B is not injective. In general, if x, y ∈ ℕ, s(x) = y, and s(y) = x, then we have B(x) = B(y). For example, since s(220) = 284 and s(284) = 220, we have that B(220) = 220 · 284 = B(284). A pair (x, y) satisfying s(x) = y and s(y) = x is called an amicable pair, and mathematicians have found millions such pairs. It is not known whether there are infinitely many amicable pairs, but it is believed that there are. If this is true, then B(x) = B(y) for an infinite number of x, y. For more information on amicable pairs and related concept, we refer the reader to Guy’s book [6, Sections B4–B8] and the sequences \underline{A063990}, \underline{A002025}, and \underline{A002046} in the OEIS [9]. We remark that \underline{A063990} gives the list of amicable numbers in an increasing order, but the adjacent numbers are not necessarily the amicable pairs (x, y). The sequences \underline{A002025} and \underline{A002046} give the list of x and y in the amicable pairs, respectively. The sequence that gives amicable pairs in an increasing order is \underline{A259180} in the OEIS. Moreover, the sequence of n ∈ ℕ such that B(x) = n has more than one solution is also registered in the OEIS as the sequence \underline{A212327}. Some values of such n and distinct x_{1}, x_{2} ∈ ℕ such that B(x_{1}) = B(x_{2}) = n are shown in Table 1.

Example 9. Let D(n) = nd(n) for all n ∈ ℕ, where d(n) is the number of positive divisors of n. Let x = 18a and y = 27a where a ∈ ℕ and (a, 6) = 1. Since D(18) = 108 = D(27) and D is multiplicative, we obtain D(x) = D(18)D(a) = D(27)D(a) = D(y). So it may be more interesting to consider only the primitive solutions to the equation D(x) = D(y) where the primitive solutions are defined in a similar way as in Example 7. We leave this problem to the interested reader. The sequence (D(n))_{n≥1} is \underline{A038040} in the OEIS. The sequence of n ∈ ℕ such that D(x) = n has more than one solution is the sequence \underline{A338382} in the OEIS. Some values of such integers n, and x_{1}, x_{2} such that D(x_{1}) = D(x_{2}) = n are shown in Table 3.

Example 10. Let W_{1}(n) = nω(n) and W_{2}(n) = nΩ(n) for all n ∈ ℕ. Let x = 30 · 5^{k} and y = 45·5^{k} where k ∈ ℕ. Then W_{1}(x) = 30·5^{k} ·3 = 45·5^{k} ·2 = W_{1}(y). So W_{1} is not injective. In general, if W_{1}(m) = W_{1}(n) and (m, n) > 1, then we can generate infinitely many x, y ∈ ℕ such that W_{1}(x) = W_{1}(y), namely, x = m · p^{k} and y = n · p^{k} where k is any positive integer and p is any prime divisor of (m, n). For W_{2}, we observe that if p is any odd prime, then W_{2}(16p) = (16p)(5) = (20p)(4) = W_{2}(20p). So W_{2} is not injective and there are infinitely many m, n ∈ ℕ such that W_{2}(m) = W_{2}(n). Some values of n ∈ ℕ such that W_{1}(x) = n or W_{2}(y) = n have more than one solution are shown in Table 4 and Table 5, respectively.

Example 11. For each positive integer b ≥ 2, let S_{b}(n) be the sum of digits of n when n is written in base b, and let H_{b}(n) = nS_{b}(n) for all n ∈ ℕ. If b = 2, then it is easy to see that H_{2}(22) = 66 = H_{2}(33). For b > 2, we have

H_{b}(b^{3} + 1) = 2(b^{3} + 1) = (b^{2} + (b − 2)b + 2)(b + 1) = H_{b}(b^{2} + (b − 2)b + 2) = H_{b}(2(b^{2} − b + 1)),

and b^{3} + 1 ≠ 2(b^{2} − b + 1). So H_{b} is not injective for any b ≥ 2. In general, if H_{b}(m) = H_{b}(n), then there are infinitely many x, y ∈ ℕ satisfying the equation H_{b}(x) = H_{b}(y), namely, x = b^{t}m and y = b^{t}n where t is an arbitrary positive integer. Some values of n ∈ ℕ such that H_{10}(x) = n has more than one solution are shown in Table 6.

4 Restricted injectivity

Since the functions defined in Example 7 to Example 11 are not injective on ℕ, it is natural to consider the injectivity of these functions on other infinite proper subsets of ℕ. In 1959, Erdős [1] observed that although the function n ↦ nσ(n) is not injective on ℕ, it is injective on the set of squarefree integers. In fact, Erdős’ observation is a special case of the next theorem.

Theorem 12. For each a, b ∈ ℕ, let F be defined by F (n) = n^{a}σ(n)^{b} for all n ∈ ℕ. Then F is injective on squarefree integers. That is, if m, n ∈ ℕ are squarefree and m^{a}σ(m)^{b} = n^{a}σ(n)^{b}, then m = n. In particular, the function A in Example 7 is injective on squarefree integers.

Proof. If m and n are squarefree, then m^{a}σ(m)^{b} = m^{a}ψ(m)^{b} and n^{a}σ(n)^{b} = n^{a}ψ(n)^{b}. So the assumption that m^{a}σ(m)^{b} = n^{a}σ(n)^{b} implies m^{a}ψ(m)^{b} = n^{a}ψ(n)^{b}, and so m = n by Theorem 3.

We remark that the integer a in Theorem 12 cannot be zero since σ is not injective on squarefree integers. For instance, we have σ(6) = σ(11) and 6, 11 are squarefree. However, if we replace σ by d in Theorem 12, the resulting function is also injective on squarefree integers.

Theorem 13. For each a, b ∈ ℕ, let F be defined by F (n) = n^{a}d(n)^{b} for all n ∈ ℕ. Then F is injective on squarefree integers. In particular, the function D, defined in Example 9, is injective on the set of squarefree integers.

Proof. Let m, n ∈ ℕ be squarefree and F (m) = F (n). It is easy to see that m = 1 if and

only if n = 1, so we assume that m, n > 1. Let m = ∏_{i=1}^{k} p_{i} and n = ∏_{i=1}^{ℓ} q_{i}, where p_{1}, p_{2}, …, p_{k}

and q_{1}, q_{2}, …, q_{ℓ} are distinct primes. Then we have

2^{kb} ∏_{i=1}^{k} p_{i}^{a} = 2^{ℓb} ∏_{i=1}^{ℓ} q_{i}^{a}.  (11)

We denote the left-hand side and the right-hand side of (11) by LHS and RHS, respectively. If k ≥ ℓ + 1, then after dividing both sides of (11) by 2^{ℓb}, LHS has at least k distinct prime factors while RHS has ℓ ≤ k − 1 distinct prime factors, a contradiction. Similarly, the inequality ℓ > k leads to a contradiction. So k = ℓ, and (11) reduces to m = n, as required.

Not every arithmetic function has the property like σ and d in Theorems 12 and 13. This is shown in the following examples.

Example 14. Let B, W_{1}, W_{2}, and H_{b} be the functions defined in Example 8, 10, and 11. We show that these functions are not injective on the set of squarefree integers. For the function B, we have 1955 and 2093 are squarefree, but

B(1955) = 1955s(1955) = 1955 · 637 = 2093 · 595 = 2093s(2093) = B(2093).

For W_{1} and W_{2}, let p_{1}, p_{2}, …, p_{9} be distinct primes and (2, p_{i}) = (5, p_{i}) = (11, p_{i}) = 1 for all 1 ≤ i ≤ 9. Let

a = 11 ∏_{i=1}^{9} p_{i} and b = 10 ∏_{i=1}^{9} p_{i}.

Then W_{1}(a) = W_{1}(b) = W_{2}(a) = W_{2}(b). Therefore W_{1} and W_{2} are not injective on the set of squarefree integers.

It is shown in Example 11 that H_{2} is not injective on the set of squarefree integers. Moreover, we have

H_{3}(51) = 255 = H_{3}(85), H_{4}(26) = 130 = H_{4}(65), H_{5}(21) = 105 = H_{5}(35),
H_{6}(26) = 156 = H_{6}(39), H_{7}(55) = 385 = H_{7}(77), H_{8}(26) = 130 = H_{8}(65),
H_{9}(15) = 105 = H_{9}(21), and H_{10}(15) = 90 = H_{10}(30).

So H_{b} is not injective on squarefree integers for 2 ≤ b ≤ 10. One can use a computer to verify that H_{b} is not injective for other values of b too. We believe that H_{b} is not injective for any b ≥ 11 but we do not have a proof.

Some products of a polynomial and two arithmetic functions are also injective on the set of squarefree integers. This can be proved by applying our theorems as follows.

Corollary 15. For each a, b ∈ ℕ, the functions F_{1} and F_{2} defined by

F_{1}(n) = n^{a}σ(n)^{b}φ(n)^{b} and F_{2}(n) = n^{a}σ(n)^{b}ψ(n)^{b} for all n ∈ ℕ

are injective on the set of squarefree integers.

Proof. Let n ∈ ℕ be squarefree. We observe that σ(n) = ψ(n) and it is easy to see that ψ(n)φ(n) = J_{2}(n). So F_{1}(n) = n^{a}J_{2}(n)^{b} and F_{2}(n) = n^{a}ψ(n)^{2b}. Therefore F_{1} and F_{2} are injective on the set of squarefree integers by Theorems 5 and 3, respectively.

We remark that F_{1} and F_{2} are not injective on ℕ. For example, when a = b = 1, we have F_{1}(56) = F_{1}(60) and F_{2}(12) = F_{2}(14).

5 Other results on noninjectivity

In this section, we study the product of a different simple polynomial and φ. So for each nonnegative integer c, let f_{c} be the arithmetic function given by

f_{c}(n) = (n + c)φ(n) for all n ∈ ℕ.

Although f_{0} is injective, we believe that f_{c} is not injective for any c ≥ 1, and we will provide some supporting evidence. If c is fixed and is given explicitly, we can always use a computer to search for distinct positive integers a, b such that f_{c}(a) = f_{c}(b). For each c = 1, 2, 3, Tables 7, 8 and 9 show distinct positive integers x_{1}, x_{2} ≤ 2000 such that f_{c}(x_{1}) = f_{c}(x_{2}). Therefore we immediately see that f_{1}, f_{2}, f_{3} are not injective. However, this only gives us a small number of c for which f_{c} is not injective.

In what follows, we will develop a tool and use it together with Table 7 to generate an infinite number of c such that f_{c} is not injective, and then use the results that we obtain to show that f_{c} is not injective for any positive integer c ≤ 1000, and that there are at least 98 percent of c ≤ N such that f_{c} is not injective when N is any large positive integer. To do so, we define for each c, n ∈ ℕ, the product

α(c, n) = ∏_{p|c and p∤n} (1 − \frac{1}{p})

where the product is taken over all primes p that are a factor of c and do not divide n. As usual, the empty product is defined to be 1. So if c = 1 or every prime divisor of c is a divisor of n, then α(c, n) = 1.

The following lemmas are simple but they are the key to the construction of an infinite number of c ∈ ℕ such that f_{c} is not injective.

Lemma 16. Let c and n be positive integers. Then the following statements hold.

(i) φ(cn) = cφ(n)α(c, n).

(ii) φ(cn) = cφ(n) if and only if c = 1 or every prime divisor of c is a divisor of n.

Proof. For (i), we apply the well known formula to obtain

\frac{φ(cn)}{φ(n)} = \frac{cn ∏_{p|cn}(1 − \frac{1}{p})}{n ∏_{p|n}(1 − \frac{1}{p})} = cα(c, n),

which implies (i). Then (ii) follows immediately from (i).

Lemma 17. The value of the finite product of the form ∏_{p}(1 − \frac{1}{p})^{a_{p}} uniquely determines the

set of primes in the product. More precisely, if p_{1} < p_{2} < ⋯ < p_{m} and q_{1} < q_{2} < ⋯ < q_{k} are primes, a_{1}, a_{2}, …, a_{m}, b_{1}, b_{2}, …, b_{k} are positive integers, and

∏_{i=1}^{m} (1 − \frac{1}{p_{i}} )^{a_{i}} = ∏_{i=1}^{k} (1 − \frac{1}{q_{i}} )^{b_{i}} ,  (12)

then m = k, p_{i} = q_{i}, and a_{i} = b_{i} for every i = 1, 2, …, m.

Proof. The idea of proof is the same as that of Theorem 1. The equality (12) leads to

∏_{i=1}^{k} q_{i}^{b_{i}} ∏_{i=1}^{m}(p_{i} − 1)^{a_{i}} = ∏_{i=1}^{m} p_{i}^{a_{i}} ∏_{i=1}^{k}(q_{i} − 1)^{b_{i}}.  (13)

Let LHS and RHS denote the left-hand side and the right-hand side of (13). If q_{k} ≥ p_{m}, then we start with LHS, which is divisible by q_{k}, and so q_{k} | RHS, which implies q_{k} = p_{m}. Similarly, if p_{m} ≥ q_{k}, then we start with p_{m} | RHS, which eventually leads to p_{m} = q_{k}. By the unique factorization, the exponents of p_{m} and q_{k} are also equal, that is, a_{m} = b_{k}. Therefore (13) reduces to an equation that is similar to (13) but k becomes k − 1 and m becomes m − 1. So we can repeat this process like the proof of Theorem 1 to obtain the desired result.

Lemma 18. Let a, b, c be positive integers and φ(a) = φ(b). Then the following statements are equivalent.

(i) φ(ca) = φ(cb).

(ii) α(c, a) = α(c, b).

(iii) {p ∈ ℕ : p is prime, p | c, and p ∤ a}={p ∈ ℕ : p is prime, p | c, and p ∤ b}.

(iv) {p ∈ ℕ : p is prime, p | c, and p | a}={p ∈ ℕ : p is prime, p | c, and p | b}.

Proof. By Lemma 16, we see that (i) and (ii) are equivalent. Lemma 17 implies that (ii) and (iii) are equivalent. Clearly, the sets in (iv) are the complement of the corresponding sets in (iii) with respect to the set of prime divisors of c. So (iii) and (iv) are equivalent. This completes the proof.

Lemma 19. Let a, b, c, d be positive integers. Then the following statements hold.

(i) If d | c and f\frac{c}{d} (a) = f\frac{c}{d} (b), then f_{c}(da) = f_{c}(db) if and only if α(d, a) = α(d, b).

(ii) If f_{1}(a) = f_{1}(b), then f_{c}(ca) = f_{c}(cb) if and only if α(c, a) = α(c, b).

(iii) If f_{1}(a) = f_{1}(b) and (c, ab) = 1, then f_{c}(ca) = f_{c}(cb).

Proof. For (i), suppose that d | c and f\frac{c}{d} (a) = f\frac{c}{d} (b). By Lemma 16, we obtain

f_{c}(da) = (da + c)φ(da) = d^{2} (a + \frac{c}{d}) φ(a)α(d, a) = d^{2}f\frac{c}{d} (a)α(d, a).

Similarly, we have f_{c}(db) = d^{2}f\frac{c}{d} (b)α(d, b). From this, we immediately obtain (i). Then (ii) follows from (i) by the substitution d = c. In addition, if (c, ab) = 1, then α(c, a) = α(c, b), and so (iii) follows from (ii). This completes the proof.

We are now ready to show that there are infinitely many c ∈ ℕ such that f_{c} is not injective.

Theorem 20. Let c be a positive integer. Then the following statements hold.

(i) If (c, 130) = 1, then f_{c} is not injective.

(ii) If the set of prime divisors of c is a subset of {2, 5, 13}, then f_{c} is not injective.

(iii) If c = p^{k} where p is a prime and k is a positive integer, then f_{c} is not injective.

Proof. For (i), let (c, 130) = 1. Let a = 13 and b = 20. From Table 1, we know that f_{1}(a) = f_{1}(b) = 168. Since (c, ab) = 1, we obtain by Lemma 19 that f_{c}(ca) = f_{c}(cb). So f_{c} is not injective, and so (i) is proved.

For (ii), let c = 2^{c_{1}}5^{c_{2}}13^{c_{3}} where c_{1}, c_{2}, c_{3} are nonnegative integers. Let a = 649 and b = 753. We know from Table 1 that f_{1}(a) = f_{1}(b) = 377000 and (c, ab) = 1. By Lemma 19, we obtain f_{c}(ca) = f_{c}(cb), and so f_{c} is not injective.

For (iii), let c = p^{k} where p is a prime and k is a positive integer. If p ∉ {2, 5, 13}, then the result follows from (i). If p ∈ {2, 5, 13}, then the result can be obtained from (ii). So the proof is complete.

By a similar method, we can generate more c ∈ ℕ such that f_{c} is not injective. We give one more similar theorem and then use it to show that f_{c} is not injective for any positive integers c ≤ 1000. We remark that the integers 2, 157, 443, 17, 47, …, 331 appearing in the statement of the next theorem are prime numbers.

Theorem 21. Let c be a positive integer. Then the following statements hold.

(i) If (c, 2) = (c, 157) = (c, 443) = 1, then f_{c} is not injective.

(ii) If (c, 2) = (c, 17) = (c, 47) = 1, then f_{c} is not injective.

(iii) If (c, 13) = (c, 71) = (c, 881) = 1, then f_{c} is not injective.

(iv) If (c, 2) = (c, 23) = 1, then f_{c} is not injective.

(v) If (c, 5) = (c, 61) = (c, 271) = 1, then f_{c} is not injective.

(vi) If (c, 3) = (c, 13) = (c, 31) = 1, then f_{c} is not injective.

(vii) If (c, 5) = (c, 37) = (c, 41) = (c, 331) = 1, then f_{c} is not injective.

Proof. The proof of this theorem is similar to that of Theorem 20. We only need to choose an appropriate choice of a, b ∈ ℕ. For (i), we choose a = 443 and b = 628 to obtain from Table 7 and Lemma 19 that f_{1}(a) = f_{1}(b) = 196248, (c, ab) = 1, and f_{c}(ca) = f_{c}(cb). In the same way, for (ii), (iii), (iv), (v), (vi), and (vii), we choose (a, b) = (47, 68), (881, 923), (23, 32), (271, 305), (31, 39), and (1517, 1655), respectively, to obtain that f_{c}(ca) = f_{c}(cb). This completes the proof.

Corollary 22. For each positive integer c ≤ 1000, the function f_{c} is not injective.

Proof. Let 1 ≤ c ≤ 1000 be a positive integer. If c is odd and is divisible by neither 157 nor 443, then the result follows from Theorem 21(i). Suppose c is odd and is divisible by 157 or 443. Since c ≤ 1000, the possible values of c are c = 157, 157 · 3, 157 · 5, 443. If c ≠ 157 · 5, then (c, 130) = 1 and the result follows from Theorem 20(i). If c = 157·5, we apply Theorem 21(ii) to obtain the desired result.

Therefore it remains to consider the case that c is even. Let c = 2^{k}d where k ≥ 1 and d is odd. If (d, 13) = (d, 71) = d(881) = 1, then the result follows from Theorem 21(iii). So we only need to consider the case that 13 | d, 71 | d, or 881 | d. Since c ≤ 1000, we see that d ≤ 500. So 881 | d is not possible.

Case 1: 71 | d. Then d = 71, 71 · 3, 71 · 5, 71 · 7. If d ≠ 71 · 5, then the result can be obtained from Theorem 21(v). If d = 71 · 5, then we apply Theorem 21(vi) to obtain the desired result.

Case 2: 13 | d. Then d = 13, 13 · 3, 13 · 5, …, 13 · 37. If d ≠ 13 · 5, 13 · 15, 13 · 25, 13 · 35, then we use Theorem 21(v); if d = 13 · 5, 13 · 25, then we apply Theorem 20(ii) to obtain the desired result. So it remains to consider the case d = 13 · 15 or d = 13 · 35.

Suppose d = 13 · 35. Then we use Table 8 to solve it as follows. Let a = 173 and b = 213. Then f_{2}(a) = f_{2}(b). Since d = 13 · 35, we have c = 2^{k} · 5 · 7 · 13. Since c ≤ 1000, we have k = 1 and c = 2 · 5 · 7 · 13. Then (\frac{c}{2}, a) = (\frac{c}{2}, b) = 1 and

f_{c} (\frac{c}{2}a) = (\frac{c}{2}a + c) φ (\frac{c}{2}a) = \frac{c}{2}(a + 2)φ (\frac{c}{2}) φ(a) = \frac{c}{2}φ (\frac{c}{2}) f_{2}(a).

Similarly, we have f_{c} (\frac{c}{2}b) = \frac{c}{2}φ (\frac{c}{2}) f_{2}(b), and so f_{c} (\frac{c}{2}a) = f_{c} (\frac{c}{2}b). This shows that f_{c} is not injective.

Finally, let d = 13 · 15. Then c = 2^{k} · 3 · 5 · 13 where k = 1, 2. We first consider the case k = 1. Let a = 391 = 17·23 and b = 526 = 2·263. From Table 8, we know that f_{2}(a) = f_{2}(b). In addition, we have (\frac{c}{2}, a) = (\frac{c}{2}, b) = 1, and by the same calculation as above, we obtain

f_{c} (\frac{c}{2}a) = f_{c} (\frac{c}{2}b), as desired. Next, let k = 2. Let a = 301 = 7 · 43 and b = 339 = 3 · 113.

By Table 9, we have f_{3}(a) = f_{3}(b). In addition, the equality (\frac{c}{3}, a) = (\frac{c}{3}, b) = 1 also holds. Therefore

f_{c} (\frac{c}{3}a) = \frac{c}{3}φ (\frac{c}{3}) f_{3}(a) = \frac{c}{3}φ (\frac{c}{3}) f_{3}(b) = f_{c} (\frac{c}{3}b) .

Hence f_{c} is not injective, as required. This completes the proof.

Finally, we show that there are at least 98 percent of positive integers c ≤ N such that f_{c} is not injective for every large positive integer N.

Theorem 23. For each N ∈ ℕ, let A = A(N) be the set of all positive integers c ≤ N such that f_{c} is not injective. Then

|A(N)| ≥ (0.981728)N + O(1).

Proof. For each d ∈ ℕ, let A_{d} = A_{d}(N) be the set of all positive integers c ≤ N such that (c, d) = 1. Let

B_{1} = A_{5} ∩ A_{61} ∩ A_{271}, B_{2} = A_{13} ∩ A_{71} ∩ A_{881}, B_{3} = A_{5} ∩ A_{37} ∩ A_{41} ∩ A_{331}.

Therefore B_{1}, B_{2}, and B_{3} are the set of positive integers c ≤ N satisfying conditions (v), (iii), and (vii) in Theorem 21, respectively. Therefore B_{1}∪B_{2}∪B_{3} ⊆ A. By the inclusion-exclusion principle, we obtain

|A| ≥ |B_{1}| + |B_{2}| + |B_{3}| − |B_{1} ∩ B_{2}| − |B_{1} ∩ B_{3}| − |B_{2} ∩ B_{3}| + |B_{1} ∩ B_{2} ∩ B_{3}|.  (14)

Let N be a large positive integer. Each block of integers

[1, d], (d, 2d] , (2d, 3d] , …, ((k − 1)d, kd] ,

where k = ⌊N/d⌋, contains exactly φ(d) integers c such that (c, d) = 1. Therefore

A_{d} = ∑_{\begin{matrix}c≤N \\ (c,d)=1 \end{matrix}} 1 = φ(d) ⌊\frac{N}{d} ⌋ + r_{d},

where 0 ≤ r_{d} < d. Thus

A_{d} ≥ \frac{φ(d)}{d}N + O_{d}(1),  (15)

where the implied constant depends at most on d but not on N.

We also observe that A_{d_{1}} ∩ A_{d_{2}} = A_{d_{1}d_{2}}. Therefore B_{1} = A_{x}, B_{2} = A_{y}, B_{3} = A_{z}, and B_{1} ∩ B_{2} ∩ B_{3} = A_{xyz}, where x = 5 · 61 · 271, y = 13 · 71 · 881, and z = 5 · 37 · 41 · 331. By (14) and (15), we obtain

|A| ≥ (\frac{φ(x)}{x} + \frac{φ(y)}{y} + \frac{φ(z)}{z} − \frac{φ(xy)}{xy} − \frac{φ(xz)}{xz} − \frac{φ(yz)}{yz} + \frac{φ(xyz)}{xyz}) N + O(1), (16)

where the implied constant depends at most on x, y, z but not on N. We have

\frac{φ(x)}{x} = ∏_{p|x} (1 − \frac{1}{p}) = (1 − \frac{1}{5}) (1 − \frac{1}{61}) (1 − \frac{1}{271}) ≥ 0.783981,

\frac{φ(y)}{y} = ∏_{p|y} (1 − \frac{1}{p}) = (1 − \frac{1}{13}) (1 − \frac{1}{71}) (1 − \frac{1}{881}) ≥ 0.909042.

Similarly, we also have

\frac{φ(z)}{z} ≥ 0.757099, \frac{φ(xy)}{xy} ≤ 0.712673, \frac{φ(xz)}{xz} ≤ 0.741940,

\frac{φ(yz)}{yz} ≤ 0.688236, and \frac{φ(xyz)}{xyz} ≥ 0.674455.

Applying these estimates in (16), we obtain the desired result. This completes the proof.

6 Notes on some related results

We also obtain a result that looks interesting and seem to be related to the Euler function. We record it here for a possibility of future reference. We observe that

\frac{1}{2} = 1 − \frac{1}{2}, \frac{1}{3} = \frac{1}{2} (1 − \frac{1}{3}) = (1 − \frac{1}{2}) (1 − \frac{1}{3}),

\frac{1}{4} = (\frac{1}{2})^{2} = (1 − \frac{1}{2})^{2}, \frac{1}{5} = \frac{1}{4} (1 − \frac{1}{5}) = (1 − \frac{1}{2})^{2} (1 − \frac{1}{5}), and so on.

In general, we have the following result.

Theorem 24. For each integer n ≥ 2, there exists a unique set of primes p_{1} > p_{2} > ⋯ > p_{k} and positive integers a_{1}, a_{2}, …, a_{k} such that

\frac{1}{n} = ∏_{i=1}^{k} (1 − \frac{1}{p_{i}} )^{a_{i}} .  (17)

Proof. We call the product in the form of the right-hand side of (17) a good form, and we observe that if 1/a and 1/b are written in a good form, then 1/ab = (1/a)(1/b) can also be written in a good form. We use this observation and a strong induction on n to prove this theorem. It is easy to check that the result holds when n = 2. So assume that n ≥ 3 and the result holds for 2, 3, …, n − 1. If n is a prime, then we write

\frac{1}{n} = (1 − \frac{1}{n}) (\frac{1}{n − 1}) ,

and then write 1/(n − 1), by the induction hypothesis, in a good form to obtain a good form for 1/n. So assume that n is a composite. Then we write n = q_{1}^{n_{1}}q_{2}^{n_{2}} ⋯ q_{k}^{n_{k}} where q_{1}, q_{2}, … q_{k} are distinct primes and n_{1}, n_{2}, …, n_{k} are positive integers. Then 2 ≤ q_{i} ≤ n − 1 for every 1 ≤ i ≤ k. By the induction hypothesis, the number 1/q_{i} can be written in a good form, and so 1/q_{i}^{n_{i}} = (1/q_{i})^{n_{i}} can also be written in a good form for every i. This gives a good form for 1/n, as required.

Remark 25. Let a(1) = 0, and for n ≥ 2, let a(n) be the number of factors counted with multiplicity in writing 1/n in the form of (17). Then it is easy to see that a(p) = 1+a(p−1) for every prime p and a(mn) = a(m) + a(n) for every m, n ∈ ℕ. In fact, the sequence (a(n))_{n≥1} is the same as \underline{A064097} in the OEIS. So, perhaps, Theorem 24 is known, but as far as we are aware, it is not widely known. We did not know about this before Ruankong sent us the statement of Theorem 24 sometime ago. He did not give a proof and did not publish the result either, but he allowed us to include it in this paper. So our idea and proof may be different from what he had in mind.

7 Open questions

In this section, we propose some problems related to our results. We do not claim that these problems are difficult or interesting. They are not important and may even be trivial. However, we would merely like to record them for ourselves and to share them among interested readers. We do not plan to solve them soon and we do not mind if the readers solve them. Question 26. We show that the function n ↦ (n+c)φ(n) is not injective for positive integers c ≤ 1000, and also for more than 98 percent of positive integers c ≤ N when N is large. Can one show that the function is not injective for any c ∈ ℕ? Question 27. By Ford’s result [3], we know that if k ≥ 2 is a fixed positive integer, there exists m ∈ ℕ such that the equation φ(x) = m has exactly k solutions. Since n ↦ nφ(n) is injective, the equation xφ(x) = m has at most one solution. What are the answers if we replace φ(n) by σ(n) or other arithmetic functions. For example, if m ∈ ℕ is given, how many solutions in x ∈ ℕ to the equations xσ(x) = m, xψ(x) = m, and xd(x) = m? Makowski [6, p. 102] observed that if M_{1} = 2^{p_{1}} − 1, M_{2} = 2^{p_{2}} − 1, …, M_{k} = 2^{p_{k}} − 1 are distinct Mersenne primes,

M = ∏_{i=1}^{k} M_{i}, and n_{i} = \frac{M}{M_{i}} for each i = 1, 2, …, k,

then n_{i}σ(n_{i}) is a constant. This shows that if k is less than or equal to the number of Mersenne primes, then there exists m ∈ ℕ such that the equation xσ(x) = m has at least k solutions in x ∈ ℕ. What are the answers if we replace σ(x) by other arithmetic functions?

Question 28. For each k ≥ 2, does there exist m ∈ ℕ for which the equation xσ(x) = m has exactly k solutions? For example, xσ(x) = 6, xσ(x) = 336, and xσ(x) = 333312 have exactly one, two, and three solutions, respectively, namely, x = 2 for the first equation, x = 12, 14 for the second equation, and x = 336, 372, 434 for the third equation, respectively. The smallest m such that xσ(x) = m has exactly n solutions is the sequence \underline{A212490} in the OEIS. It should be observed that 6 | 336 and 336 | 333312. If a_{n} is the nth term of the sequence \underline{A212490}, is it true that a_{n+1} is always divisible by a_{n}?

Question 29. Let B be the function defined in Example 8 by B(x) = xs(x). Recall that if (x, y) is an amicable pair, then B(x) = B(y). Nevertheless, if B(x) = B(y), then (x, y) may or may not be an amicable pair. For instance, we know from Table 1 that B(6) = B(9) = 36, B(320) = B(340) = 141440, and B(1280) = B(1504) = 2286080, but they are not amicable pairs. Are there infinitely many x, y ∈ ℕ such that B(x) = B(y)? Are there infinitely many such x, y ∈ ℕ that are not an amicable pair?

Question 30. We show in Examples 11 and 14 that the function H_{b}, which is defined by H_{b}(n) = nS_{b}(n), is not injective on ℕ for any b ≥ 2 and is not injective on squarefree integers for 2 ≤ b ≤ 10. Can one show that H_{b} is not injective on squarefree integers for any b ≥ 11?

Question 31. We show that the function n ↦ n^{a}J_{s}(n)^{b} is injective if s = 2 or a ≥ sb. Is the function n ↦ n^{a}J_{s}(n)^{b} injective if s ≥ 3 and a < sb?

Question 32. It is not difficult to show that an analogue of Lemma 17 where 1− \frac{1}{p} is replaced

by 1 + \frac{1}{p} also holds. That is, the product ∏_{p} (1 + \frac{1}{p})^{a_{p}} uniquely determines the primes p and

the exponents a_{p} in the product. However, it is not clear how an analogue of Theorem 24 should look like. Can one determine the set of all rational numbers q that can be written as

q = ∏_{p} (1 + \frac{1}{p})^{a_{p}}

for some primes p and positive integers a_{p}?

Question 33. Other questions stated in Guy’s book [6] are the following:

(i) Among all m, n ∈ ℕ such that mσ(m) = nσ(n), is m/n bounded?

(ii) Are there relatively prime positive integers m and n satisfying mσ(n) = nσ(m)?

Question 34. Let (a(n))_{n≥1} be the sequence \underline{A064097} in the OEIS. This sequence is related to Theorem 24 and is also mentioned in Remark 25. Some conjectures regarding a(n) stated in the OEIS are as follows.

(i) (Cloitre) log n < a(n) < (5/2) log n for n ≥ 2, and there exists a positive constant c

such that

∑_{1≤k≤n} a(k) ∼ cn log n.

(ii) (Wilson) ⌊log 2n⌋ < a(n) < (5/2) log n for n ≥ 2.

8 Acknowledgment

Prapanpong Pongsriiam’s research project is funded jointly by the Faculty of Science Silpakorn University and the National Research Council of Thailand (NRCT), grant number NRCT5-RSA63021-02. He is also supported by the Tosio Kato Fellowship given by the Mathematical Society of Japan during his visit at Nagoya University in July 2022 to July 2023. We thank Pongpol Ruankong for sending us the statement of Theorem 24 and making us aware of the sequence \underline{A064097} in the OEIS. We are also grateful to the anonymous referee for reading our paper carefully and giving us suggestions which improve the quality of this article.

9 Tables

\begin{matrix}B(x_{1}) = B(x_{2}) & x_{1} & x_{2} \\ 36 & 6 & 9 \\ 62480 & 220 & 284 \\ 141440 & 320 & 340 \\ 1432640 & 1184 & 1210 \\ 2286080 & 1280 & 1504 \\ 1245335 & 1955 & 2093 \\ 6680960 & 2080 & 2288 \\ 7660880 & 2620 & 2924 \\ 27931280 & 5020 & 5564 \\ 39685376 & 6232 & 6368 \end{matrix}

Table 1: Distinct integers x_{1}, x_{2} ∈ (1, 10000] such that B(x_{1}) = B(x_{2}) where B is defined in Example 8 by B(x) = xs(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and B(x_{1}) = B(x_{2}) are not listed in an increasing order.

\begin{matrix}A(x_{1}) = A(x_{2}) & x_{1} & x_{2} \\ 336 & 12 & 14 \\ 5952 & 48 & 62 \\ 10080 & 60 & 70 \\ 27776 & 112 & 124 \\ 44352 & 132 & 154 \\ 61152 & 156 & 182 \\ 60480 & 160 & 189 \\ 97536 & 192 & 254 \\ 102816 & 204 & 238 \\ 127680 & 228 & 266 \\ 178560 & 240 & 310 \\ 185472 & 276 & 322 \\ 260400 & 300 & 350 \\ 196560 & 315 & 351 \\ 333312 & 336 & 372 \\ 333312 & 336 & 434 \\ 292320 & 348 & 406 \\ 333312 & 372 & 434 \\ 472416 & 444 & 518 \\ 455168 & 448 & 508 \\ 578592 & 492 & 574 \\ 635712 & 516 & 602 \\ 785664 & 528 & 682 \\ 833280 & 560 & 620 \\ 758016 & 564 & 658 \\ 1083264 & 624 & 806 \\ 1179360 & 630 & 702 \\ 961632 & 636 & 742 \\ 1330560 & 660 & 770 \\ 1189440 & 708 & 826 \\ 1270752 & 732 & 854 \\ 1530816 & 804 & 938 \\ 1717632 & 852 & 994 \end{matrix}  \begin{matrix}A(x_{1}) = A(x_{2}) & x_{1} & x_{2} \\ 1834560 & 780 & 910 \\ 1821312 & 816 & 1054 \\ 1815072 & 876 & 1022 \\ 2261760 & 912 & 1178 \\ 2123520 & 948 & 1106 \\ 2926080 & 960 & 1270 \\ 2342592 & 996 & 1162 \\ 3249792 & 1008 & 1116 \\ 3084480 & 1020 & 1190 \\ 2691360 & 1068 & 1246 \\ 3285504 & 1104 & 1426 \\ 3830400 & 1140 & 1330 \\ 3194016 & 1164 & 1358 \\ 4612800 & 1200 & 1550 \\ 3461472 & 1212 & 1414 \\ 3666432 & 1232 & 1364 \\ 3599232 & 1236 & 1442 \\ 5503680 & 1260 & 1404 \\ 3882816 & 1284 & 1498 \\ 4028640 & 1308 & 1526 \\ 5462016 & 1344 & 1524 \\ 5462016 & 1344 & 1778 \\ 4328352 & 1356 & 1582 \\ 5564160 & 1380 & 1610 \\ 5178240 & 1392 & 1798 \\ 5407248 & 1452 & 1694 \\ 5055232 & 1456 & 1612 \\ 6552000 & 1500 & 1750 \\ 5462016 & 1524 & 1778 \\ 5810112 & 1572 & 1834 \\ 6352416 & 1644 & 1918 \\ 6538560 & 1668 & 1946 \\ 9999360 & 1680 & 1860 \end{matrix}

Table 2: Distinct integers x_{1}, x_{2} ∈ (1, 2000] such that A(x_{1}) = A(x_{2}) where A is defined in Example 7 by A(x) = xσ(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and A(x_{1}) = A(x_{2}) are not listed in an increasing order.

\begin{matrix}D(x_{1}) = D(x_{2}) & x_{1} & x_{2} \\ 108 & 18 & 27 \\ 192 & 24 & 32 \\ 448 & 56 & 64 \\ 1080 & 90 & 135 \\ 1920 & 120 & 160 \\ 1512 & 126 & 189 \\ 2688 & 168 & 192 \\ 2688 & 168 & 224 \\ 2688 & 192 & 224 \\ 2376 & 198 & 297 \\ 2808 & 234 & 351 \\ 4224 & 264 & 352 \\ 4480 & 280 & 320 \\ 3672 & 306 & 459 \\ 4992 & 312 & 416 \\ 4104 & 342 & 513 \\ 8640 & 360 & 432 \\ 6000 & 400 & 500 \\ 6528 & 408 & 544 \\ 4968 & 414 & 621 \\ 8100 & 450 & 675 \\ 7296 & 456 & 608 \\ 12096 & 504 & 576 \\ 6264 & 522 & 783 \\ 12960 & 540 & 648 \\ 8832 & 552 & 736 \\ 6696 & 558 & 837 \\ 14400 & 600 & 800 \\ 9856 & 616 & 704 \\ 15120 & 630 & 945 \\ 7992 & 666 & 999 \\ 11136 & 696 & 928 \\ 11648 & 728 & 832 \\ 8856 & 738 & 1107 \end{matrix}  \begin{matrix}D(x_{1}) = D(x_{2}) & x_{1} & x_{2} \\ 11904 & 744 & 992 \\ 9288 & 774 & 1161 \\ 26880 & 840 & 960 \\ 26880 & 840 & 1120 \\ 10152 & 846 & 1269 \\ 15876 & 882 & 1323 \\ 14208 & 888 & 1184 \\ 15232 & 952 & 1088 \\ 11448 & 954 & 1431 \\ 26880 & 960 & 1120 \\ 15744 & 984 & 1312 \\ 23760 & 990 & 1485 \\ 16512 & 1032 & 1376 \\ 12744 & 1062 & 1593 \\ 17024 & 1064 & 1216 \\ 13176 & 1098 & 1647 \\ 18048 & 1128 & 1504 \\ 28080 & 1170 & 1755 \\ 28224 & 1176 & 1568 \\ 36000 & 1200 & 1500 \\ 14472 & 1206 & 1809 \\ 20352 & 1272 & 1696 \\ 15336 & 1278 & 1917 \\ 20608 & 1288 & 1472 \\ 32400 & 1296 & 1350 \\ 15768 & 1314 & 1971 \\ 42240 & 1320 & 1760 \\ 33600 & 1400 & 1600 \\ 22656 & 1416 & 1888 \\ 20412 & 1458 & 1701 \\ 23424 & 1464 & 1952 \\ 48384 & 1512 & 1728 \\ 25984 & 1624 & 1856 \\ 27776 & 1736 & 1984 \end{matrix}

Table 3: Distinct integers x_{1}, x_{2} ∈ (1, 2000] such that D(x_{1}) = D(x_{2}) where D is defined in Example 9 by D(x) = xd(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and D(x_{1}) = D(x_{2}) are not listed in an increasing order.

\begin{matrix}W_{1}(x_{1}) = W_{1}(x_{2}) & x_{1} & x_{2} \\ 90 & 30 & 45 \\ 126 & 42 & 63 \\ 198 & 66 & 99 \\ 234 & 78 & 117 \\ 270 & 90 & 135 \\ 306 & 102 & 153 \\ 342 & 114 & 171 \\ 378 & 126 & 189 \\ 414 & 138 & 207 \\ 450 & 150 & 225 \\ 522 & 174 & 261 \\ 558 & 186 & 279 \\ 594 & 198 & 297 \\ 840 & 210 & 280 \\ 666 & 222 & 333 \\ 702 & 234 & 351 \\ 738 & 246 & 369 \\ 774 & 258 & 387 \\ 810 & 270 & 405 \\ 846 & 282 & 423 \\ 882 & 294 & 441 \\ 918 & 306 & 459 \\ 954 & 318 & 477 \\ 1320 & 330 & 440 \\ 1026 & 342 & 513 \\ 1062 & 354 & 531 \\ 1098 & 366 & 549 \end{matrix}  \begin{matrix}W_{1}(x_{1}) = W_{1}(x_{2}) & x_{1} & x_{2} \\ 1134 & 378 & 567 \\ 1560 & 390 & 520 \\ 1206 & 402 & 603 \\ 1242 & 414 & 621 \\ 1680 & 420 & 560 \\ 1278 & 426 & 639 \\ 1314 & 438 & 657 \\ 1350 & 450 & 675 \\ 1848 & 462 & 616 \\ 1422 & 474 & 711 \\ 1494 & 498 & 747 \\ 2040 & 510 & 680 \\ 1566 & 522 & 783 \\ 1602 & 534 & 801 \\ 2184 & 546 & 728 \\ 1674 & 558 & 837 \\ 2280 & 570 & 760 \\ 1746 & 582 & 873 \\ 1782 & 594 & 891 \\ 1818 & 606 & 909 \\ 1854 & 618 & 927 \\ 1926 & 642 & 963 \\ 1962 & 654 & 981 \\ 2640 & 660 & 880 \\ 1998 & 666 & 999 \\ 2760 & 690 & 920 \\ 2856 & 714 & 952 \end{matrix}

Table 4: Distinct integers x_{1}, x_{2} ∈ (1, 1000] such that W_{1}(x_{1}) = W_{1}(x_{2}) where W_{1} is defined in Example 10 by W_{1}(x) = xω(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and W_{1}(x_{1}) = W_{1}(x_{2}) are not listed in an increasing order.

\begin{matrix}W_{2}(x_{1}) = W_{2}(x_{2}) & x_{1} & x_{2} \\ 160 & 32 & 40 \\ 240 & 48 & 60 \\ 360 & 72 & 90 \\ 400 & 80 & 100 \\ 540 & 108 & 135 \\ 560 & 112 & 140 \\ 600 & 120 & 150 \\ 840 & 168 & 210 \\ 880 & 176 & 220 \\ 900 & 180 & 225 \\ 1344 & 192 & 224 \\ 1000 & 200 & 250 \\ 1040 & 208 & 260 \\ 1260 & 252 & 315 \\ 1320 & 264 & 330 \\ 1360 & 272 & 340 \\ 1400 & 280 & 350 \\ 2016 & 288 & 336 \\ 1500 & 300 & 375 \\ 1520 & 304 & 380 \\ 1560 & 312 & 390 \\ 1840 & 368 & 460 \\ 1960 & 392 & 490 \\ 1980 & 396 & 495 \\ 2040 & 408 & 510 \\ 2100 & 420 & 525 \\ 3024 & 432 & 504 \\ 2200 & 440 & 550 \\ 2280 & 456 & 570 \end{matrix}  \begin{matrix}W_{2}(x_{1}) = W_{2}(x_{2}) & x_{1} & x_{2} \\ 2320 & 464 & 580 \\ 2340 & 468 & 585 \\ 3360 & 480 & 560 \\ 2480 & 496 & 620 \\ 2500 & 500 & 625 \\ 4608 & 512 & 576 \\ 2600 & 520 & 650 \\ 2760 & 552 & 690 \\ 2940 & 588 & 735 \\ 2960 & 592 & 740 \\ 3060 & 612 & 765 \\ 3080 & 616 & 770 \\ 4536 & 648 & 756 \\ 3280 & 656 & 820 \\ 3300 & 660 & 825 \\ 4704 & 672 & 784 \\ 3400 & 680 & 850 \\ 3420 & 684 & 855 \\ 3440 & 688 & 860 \\ 3480 & 696 & 870 \\ 3500 & 700 & 875 \\ 5040 & 720 & 840 \\ 3640 & 728 & 910 \\ 3720 & 744 & 930 \\ 3760 & 752 & 940 \\ 3800 & 760 & 950 \\ 6912 & 768 & 864 \\ 3900 & 780 & 975 \end{matrix}

Table 5: Distinct integers x_{1}, x_{2} ∈ (1, 1000] such that W_{2}(x_{1}) = W_{2}(x_{2}) where W_{2} is defined in Example 10 by W_{2}(x) = xΩ(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and W_{2}(x_{1}) = W_{2}(x_{2}) are not listed in an increasing order.

\begin{matrix}H_{10}(x_{1}) = H_{10}(x_{2}) & x_{1} & x_{2} \\ 36 & 6 & 12 \\ 90 & 15 & 30 \\ 160 & 32 & 40 \\ 280 & 28 & 35 \\ 306 & 51 & 102 \\ 684 & 57 & 114 \\ 360 & 60 & 120 \\ 640 & 64 & 80 \\ 792 & 66 & 132 \\ 900 & 75 & 150 \\ 900 & 75 & 300 \\ 1105 & 85 & 221 \\ 1204 & 86 & 301 \\ 1408 & 88 & 128 \\ 1440 & 96 & 240 \\ 520 & 104 & 130 \\ 630 & 105 & 210 \\ 1360 & 136 & 170 \\ 900 & 150 & 300 \\ 1872 & 156 & 312 \\ 1980 & 165 & 330 \\ 2520 & 168 & 420 \\ 1720 & 172 & 215 \\ 2992 & 187 & 272 \\ 2080 & 208 & 260 \\ 2440 & 244 & 305 \end{matrix}  \begin{matrix}H_{10}(x_{1}) = H_{10}(x_{2}) & x_{1} & x_{2} \\ 3060 & 255 & 510 \\ 4140 & 276 & 345 \\ 2800 & 280 & 350 \\ 4576 & 286 & 416 \\ 1600 & 320 & 400 \\ 4732 & 338 & 364 \\ 5220 & 348 & 435 \\ 3520 & 352 & 440 \\ 5760 & 384 & 480 \\ 6160 & 385 & 560 \\ 4240 & 424 & 530 \\ 6370 & 455 & 490 \\ 6840 & 456 & 570 \\ 7744 & 484 & 704 \\ 7380 & 492 & 615 \\ 7920 & 528 & 660 \\ 8460 & 564 & 705 \\ 8008 & 572 & 616 \\ 11305 & 595 & 665 \\ 11920 & 596 & 745 \\ 6400 & 640 & 800 \\ 13360 & 668 & 835 \\ 10080 & 672 & 840 \\ 11160 & 744 & 930 \\ 14212 & 748 & 836 \\ 15520 & 776 & 970 \end{matrix}

Table 6: Distinct integers x_{1}, x_{2} ∈ (1, 1000] such that H_{10}(x_{1}) = H_{10}(x_{2}) where H_{10} is defined in Example 11 by H_{10}(x) = xS_{10}(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and H_{10}(x_{1}) = H_{10}(x_{2}) are not listed in an increasing order.

f_{1}(x_{1}) = f_{1}(x_{2}) x_{1}  x_{2} Factorization of x_{1} Factorization of x_{2}
168  13 20  13  2^{2} · 5
528  23 32  23  2^{5}
960  31 39  31  3 · 13
1368  37 56  37  2^{3} · 7
2208  47 68  47  2^{2} · 17
5040  71 104  71  2^{3} · 13
18720  155 194  5 · 31  2 · 97
73440  271 305  271  5 · 61
78880  289 492  17^{2}  2^{2} · 3 · 41
144072  413 666  7 · 59  2 · 3^{2} · 37
196248  443 628  443  2^{2} · 157
131328  455 512  5 · 7 · 13  2^{9}
212520  461 804  461  2^{2} · 3 · 67
199080  473 710  11 · 43  2 · 5 · 71
210528  515 730  5 · 103  2 · 5 · 73
253440  527 575  17 · 31  5^{2} · 23
256320  533 800  13 · 41  2^{5} · 5^{2}
226800  539 674  7^{2} · 11  2 · 337
218120  573 664  3 · 191  2^{3} · 83
361200  601 902  601  2 · 11 · 41
320544  635 741  5 · 127  3 · 13 · 19
377000  649 753  11 · 59  3 · 251
776160  881 923  881  13 · 71
863040  929 1239  929  3 · 7 · 59
820800  949 1025  13 · 73  5^{2} · 41
1585080  1259 1784  1259  2^{3} · 223
708048  1340 1638  2^{2} · 5 · 67  2 · 3^{2} · 7 · 13
2185920  1517 1655  37 · 41  5 · 331

Table 7: Distinct integers x_{1}, x_{2} ∈ (1, 2000] such that f_{1}(x_{1}) = f_{1}(x_{2}) where f_{1} is the function defined in Section 5 by f_{1}(x) = (x + 1)φ(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and f_{1}(x_{1}) = f_{1}(x_{2}) are not listed in an increasing order.

f_{2}(x_{1}) = f_{2}(x_{2}) x_{1}  x_{2} Factorization of x_{1} Factorization of x_{2}
1920  62 78  2 · 31  2 · 3 · 13
30100  173 213  173  3 · 71
37440  193 310  193  2 · 5 · 31
78480  325 434  5^{2} · 13  2 · 7 · 31
89040  369 422  3^{2} · 41  2 · 211
138336  391 526  17 · 23  2 · 263
126480  525 618  3 · 5^{2} · 7  2 · 3 · 103
146880  542 610  2 · 271  2 · 5 · 61
254016  565 754  5 · 113  2 · 13 · 29
363456  629 1260  17 · 37  2^{2} · 3^{2} · 5 · 7
219120  662 828  2 · 331  2^{2} · 3^{2} · 23
288144  665 826  5 · 7 · 19  2 · 7 · 59
453600  673 1078  673  2 · 7^{2} · 11
294528  765 942  3^{2} · 5 · 17  2 · 3 · 157
290880  806 1008  2 · 13 · 31  2^{4} · 3^{2} · 7
320256  832 1110  2^{6} · 13  2 · 3 · 5 · 37
469440  976 1302  2^{4} · 61  2 · 3 · 7 · 31
506880  1054 1150  2 · 17 · 31  2 · 5^{2} · 23
761376  1131 1234  3 · 13 · 29  2 · 617
796320  1262 1420  2 · 631  2^{2} · 5 · 71
641088  1270 1482  2 · 5 · 127  2 · 3 · 13 · 19
754000  1298 1506  2 · 11 · 59  2 · 3 · 251
907200  1348 1510  2^{2} · 337  2 · 5 · 151
1552320  1762 1846  2 · 881  2 · 13 · 71

Table 8: Distinct integers x_{1}, x_{2} ∈ (1, 2000] such that f_{2}(x_{1}) = f_{2}(x_{2}) where f_{2} is the function defined in Section 5 by f_{2}(x) = (x + 2)φ(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and f_{2}(x_{1}) = f_{2}(x_{2}) are not listed in an increasing order.

f_{3}(x_{1}) = f_{3}(x_{2}) x_{1}  x_{2} Factorization of x_{1} Factorization of x_{2}
60  7 12  7  2^{2} · 3
560  25 32  5^{2}  2^{5}
540  27 42  3^{3}  2 · 3 · 7
1008  39 60  3 · 13  2^{2} · 3 · 5
3168  69 96  3 · 23  2^{5} · 3
7056  95 144  5 · 19  2^{4} · 3^{2}
6120  99 150  3^{2} · 11  2 · 3 · 5^{2}
8208  111 168  3 · 37  2^{3} · 3 · 7
13248  141 204  3 · 47  2^{2} · 3 · 17
21360  175 264  5^{2} · 7  2^{3} · 3 · 11
30240  213 312  3 · 71  2^{3} · 3 · 13
54000  247 297  13 · 19  3^{3} · 11
76608  301 339  7 · 43  3 · 113
112320  465 582  3 · 5 · 31  2 · 3 · 97
186912  469 646  7 · 67  2 · 17 · 19
324896  569 920  569  2^{3} · 5 · 23
376992  613 1068  613  2^{2} · 3 · 89
378000  753 872  3 · 251  2^{3} · 109
396144  783 1176  3^{3} · 29  2^{3} · 3 · 7^{2}
580320  803 933  11 · 73  3 · 311
440640  813 915  3 · 271  3 · 5 · 61
879840  937 1830  937  2 · 3 · 5 · 61
808128  973 1101  7 · 139  3 · 367
822400  1025 1282  5^{2} · 41  2 · 641
1254960  1159 1491  19 · 61  3 · 7 · 71
1177488  1329 1884  3 · 443  2^{2} · 3 · 157
787968  1365 1536  3 · 5 · 7 · 13  2^{9} · 3
1520640  1581 1725  3 · 17 · 31  3 · 5^{2} · 23
2537472  1649 1885  17 · 97  5 · 13 · 29

Table 9: Distinct integers x_{1}, x_{2} ∈ (1, 2000] such that f_{3}(x_{1}) = f_{3}(x_{2}) where f_{3} is the function defined in Section 5 by f_{3}(x) = (x + 3)φ(x) for all x ∈ ℕ. The values of x_{1} are increasing, but x_{2} and f_{3}(x_{1}) = f_{3}(x_{2}) are not listed in an increasing order.

References

[1] P. Erdős, Remarks on number theory II: some problems on the σ function, Acta Arith. 5 (1959), 171–177.

[2] K. Ford, The distribution of totients, Ramanujan J. 2 (1998), 67–151.

[3] K. Ford, The number of solutions of φ(x) = m, Ann. Math. 150 (1999), 1–29.

[4] K. Ford, F. Luca, and C. Pomerance, Common values of the arithmetic functions ϕ and σ, Bull. Lond. Math. Soc. 42 (2010), 478–488.

[5] K. Ford and P. Pollack, On common values of φ(n) and σ(n) II, Algebra Number Theory 6 (2012), 1669–1696.

[6] R. K. Guy, Unsolved Problems in Number Theory, 3rd edition, Springer, 2004.

[7] C. Pomerance, Popular values of Euler’s function, Mathematika 27 (1980), 84–89.

[8] P. Pongsriiam, Quasi-injectivity of some arithmetic functions, J. Integer Sequences 24 (2021), Article 21.10.1.

[9] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2022. Available

    at https://oeis.org/.

2020 Mathematics Subject Classification: Primary 11A25. Secondary 11B83, 11D45. Keywords: arithmetic function, Euler’s totient function, the sum of divisors function, Mersenne prime, amicable pair, Dedekind’s psi function, Jordan’s totient function, prime omega function, sum-of-digits function.

(Concerned with sequences \underline{A000010}, \underline{A000396}, \underline{A000668}, \underline{A001065}, \underline{A002025}, \underline{A002046}, \underline{A007617}, \underline{A008888}, \underline{A038040}, \underline{A063900}, \underline{A063990}, \underline{A064097}, \underline{A064987}, \underline{A098007}, \underline{A212327}, \underline{A212490}, \underline{A259180}, \underline{A337873}, and \underline{A338382}.)

Received December 13 2022; revised version received April 10 2023. Published in Journal of Integer Sequences, November 2 2023.

Return to Journal of Integer Sequences home page.