On the Solution of the Equation n = ak + bp_{k} by Means of an Iterative Method

Juan Luis Varona^{1} Departamento de Matemáticas y Computación Universidad de La Rioja Logroño Spain

                  jvarona@unirioja.es

Abstract

For fixed positive integers n, we study the solution of the equation n = k + p_{k}, where p_{k} denotes the kth prime number, by means of the iterative method

k_{j+1} = π(n − k_{j}), k_{0} = π(n),

which converges to the solution of the equation, if it exists. We also analyze the equation n = ak + bp_{k} for fixed integer values a ≠ 0 and b > 0, and its solution by means of a corresponding iterative method. The case a > 0 is somewhat similar to the case a = b = 1, while for a < 0 the convergence and usefulness of the method are less satisfactory. The paper also includes a study of the dynamics of the iterative methods.

1 Introduction and main results

Let us imagine that we want to know if a Fibonacci number, a pentagonal number, one of a pair of amicable numbers or a Pythagorean triple, the terms in a sequence in the On-line Encyclopedia of Integer Sequences (OEIS, [8]), or any other positive integer can be written as

n = k + p_{k},  (1)

1The work of the author is supported by the spanish Ministerio de Ciencia, Innovación y Universidades under Grant PGC2018-096504-B-C32.

where (p_{k})_{k≥1} is the sequence of the prime numbers. (Let us note that neither Mathematica, Maple nor SageMath are able to solve the equation (1) even in simple cases with small numbers; for instance, when n = 39 = 10 + p_{10}.)

Of course, one can look at the sequence (k + p_{k})_{k≥1} (which is sequence \underline{A014688} in the OEIS) and check if n occurs in the sequence; but this can be a hard task. Instead, we give here an iterative process which, given n, tells whether the equation (1) has a solution or not, and, in the affirmative case, provides the solution k.

It is worth noting that there exist a large number of iterative methods for solving equations of the form f(x) = 0 where f is a function defined on ℝ, ℂ, ℝ^{d}, ℂ^{d} or a Banach space. However, there are very few iterative methods for solving equations in the theory of numbers. Perhaps the best example of an iterative method for solving an equation in this area is [6], where the authors show how classical rootfinding methods from numerical analysis can be used to calculate inverses of units modulo prime powers.

Along the paper, we will use some well known properties of prime numbers, which can be found in many texts; see, for instance, [1, 3, 4, 5, 7]. As usual, π(x) denotes the quantity of prime numbers ≤ x, which is a nondecreasing function. Moreover, we will often use the basic properties π(p_{k}) = k and p_{π(n)} ≤ n (with p_{π(n)} = n if and only if n is prime). Let us also note that k + p_{k} is strictly increasing with k. Thus, for a fixed n the solution of (1), if it exists, is unique.

A possible method to try to find k such that n = k + p_{k} is to take f(k) = k + p_{k} − n and solve the equation f(k) = 0 by means of a bisection method starting at the initial points k_{0} = 1 and k_{1} = n. The function f(k) is increasing and satisfies f(k_{0}) < 0 and f(k_{1}) > 0 so, if the solution exists, the bisection method always finds it. Moreover, the number of iterations needed to reach the solution is ⌊log_{2}(n − 1)⌋ (of course, this number can be a bit different due to the rounding of the bisection to an integer in every step). Instead, we propose another method that is faster, as we can see in the examples, and has a nice dynamics with its own interest.

The iterative method that we are going is simple and, as far as we know, has not been proposed before in this context; it is a kind of regula falsi method to solve an equation f(k) = 0 with f(k) = π(n − k) − k, that is not equivalent to (1), but closely related. Since p_{k} ≈ k log k, it follows that p_{k} gives the main contribution to the sum k + p_{k}. The idea is then to approximate the equation (1) by the equation n = p_{k}, and so to take a first guess k = π(n); then we adjust the initial guess by successive corrections. Let us note that any k that solves n = k + p_{k} satisfies n − k = p_{k}, a prime number, so π(n − k) = k. Thus, the procedure for solving (1) is based on the iterative scheme k_{j+1} = π(n − k_{j}), and the goal is to look for a fixed point. The following result shows the dynamics of the iterative method:

Theorem 1. Let n ≥ 4 be a given integer, and let us define the iterative process

k_{j+1} = π(n − k_{j}),  k_{0} = π(n).  (2)

After a finite number of steps, one of these cases occurs:

(i) We get a fixed point k^{∗}.

(ii) We get a cycle {k′, k′′} with k′′ = k′ +1, n−k′ a prime number, (k_{2j})_{j≥0} is a decreasing sequence that converges to k′′, and (k_{2j+1})_{j≥0} is an increasing sequence that converges to k′.

We postpone the proof of this theorem to Section 2. For the moment, let us see the consequences of this result on the solutions of the equation (1).

Theorem 2. Let n ≥ 4 be a given integer, the equation n = k + p_{k}, and the iterative process

k_{j+1} = π(n − k_{j}), k_{0} = π(n).

Under these circumstances:

(i) If we get a fixed point k^{∗} (case (i) in Theorem 1), then k^{∗} is the solution of the equation

n′ = k + p_{k}

where n′ = max{j + p_{j} ≤ n : j ≥ 1}. In particular, the equation n = k + p_{k} has a solution if and only if n′ = n, and then k^{∗} is the solution. (In practice it is enough to check whether k^{∗} + p_{k^{∗}} = n or not.)

(ii) If we get a cycle {k′, k′′} (with k′′ = k′ + 1, case (ii) in Theorem 1), the equation n = k + p_{k} has no solution.

As in the case of Theorem 1, we postpone the proof of Theorem 2 to Section 2.

Both cases (i) and (ii) can really occur, as the following illustrative examples with small numbers show. The case (i) occurs, for instance, with n = 51 or n = 76. For n = 51, the successive k_{j} in (2) are

k_{0} = π(51) = 15, k_{1} = π(51 − 15) = 11,
k_{2} = π(51 − 11) = 12, k_{3} = π(51 − 12) = 12,

so we have reached the fixed point k^{∗} = 12; but k^{∗} +p_{k^{∗}} = 12+37 = 49 ≠ 51, so the equation 51 = k + p_{k} has no solution. For n = 76, the successive k_{j} in (2) are

k_{0} = π(76) = 21, k_{1} = π(76 − 21) = 16,
k_{2} = π(76 − 16) = 17, k_{3} = π(76 − 17) = 17,

so k^{∗} = 17 is a fixed point; this time k^{∗} + p_{k^{∗}} = 17 + 59 = 76, so we have found the solution of 76 = k + p_{k}. To illustrate the case (ii), let us take, for instance, n = 41. The successive k_{j} in (2) are

k_{0} = π(41) = 13, k_{1} = π(41 − 13) = 9, k_{2} = π(41 − 9) = 11,
k_{3} = π(41 − 11) = 10, k_{4} = π(41 − 10) = 11,
k′ = k_{5} = k_{7} = k_{9} = ⋯ = 10, k′′ = k_{6} = k_{8} = k_{10} = ⋯ = 11.

F_{m}  Iterations  k^{∗} or {k′, k′′}  Is k^{∗} a solution? ⌊log_{2} F_{m}⌋
F_{12} = 144  3  30  no  7
F_{13} = 233  3  {42, 43}  —  7
F_{14} = 377  4  {64, 65}  —  8
F_{15} = 610  3  97  no  9
F_{27} = 196 418  5  {16 347, 16 348}  —  17
F_{42} = 267 914 296  7  13 887 473  yes  27
F_{50} = 12 586 269 025  8 {543 402 114, 543 402 115}  —  33
F_{53} = 53 316 291 173  7  2 166 313 972  yes  35
F_{66} = 27 777 890 035 288  9  899 358 426 281  no  44
F_{67} = 44 945 570 212 853  9  1 432 816 693 546  no  45
F_{68} = 72 723 460 248 141  9  2 283 240 409 254  no  46
F_{69} = 117 669 030 460 994 9  3 639 256 692 076  no  46
F_{70} = 190 392 490 709 135 9  5 801 907 791 391  no  47

Table 1: The iterative method applied to solve F_{m} = k + p_{k} where F_{m} are the Fibonacci numbers with 12 ≤ m ≤ 70. We omit the F_{m} with 15 < m ≤ 65 whose corresponding iterative methods converge to a fixed point k^{∗} that is not a solution of F_{m} = k + p_{k}. In the last column, ⌊log_{2} F_{m}⌋ is a rather precise estimation of the number of iterations required to solve the equation with the bisection method.

Then 41 = k + p_{k} has no solution.

Some examples with bigger numbers are given in Table 1. The iterative algorithm is applied to some Fibonacci numbers (\underline{A000045} in the OEIS), showing whether the method converges to a fixed point k^{∗} or to a cycle {k′, k′′}, as well as the number of iterations to reach it. Observe that the number of iterations for n ≤ F_{70} ≈ 1.9 · 10^{14} is always less than ten; for each equation, we also see how our method is faster than the bisection method, which requires a considerably higher number of iterations.

Instead of (1) we can consider the more general equation

n = ak + bp_{k},

with b ≥ 1 and a ∈ ℤ \ {0} (the trivial case a = 0 is excluded).

In this setting we can consider the iterative process which starts with k_{0} = π(n/b) and continues with

k_{j+1} = π((n − ak_{j})/b), j ≥ 0.

Now, the behavior of the iterative method and its relation with the solution of n = ak + bp_{k} is a bit more complicated than in the case a = b = 1. We analyze it in Section 3.

2 Proof of Theorems 1 and 2

Proof of Theorem 1. It is clear that k_{1} = π(n − k_{0}) ≤ π(n) = k_{0}. From the inequality k_{1} ≤ k_{0}, it follows that k_{2} = π(n − k_{1}) ≥ π(n − k_{0}) = k_{1}. Now, from k_{2} ≥ k_{1} we get k_{3} = π(n − k_{2}) ≤ π(n − k_{1}) = k_{2}, and so on. That is,

k_{2j+1} ≤ k_{2j} and k_{2j+2} ≥ k_{2j+1},  for j = 0, 1, 2, ….  (3)

Moreover, k_{2} = π(n − k_{1}) ≤ π(n) = k_{0}, and from the inequality k_{2} ≤ k_{0} it follows that k_{3} = π(n−k_{2}) ≥ π(n−k_{0}) = k_{1}. Now, from k_{3} ≥ k_{1} we get k_{4} = π(n−k_{3}) ≤ π(n−k_{1}) = k_{2}, and so on. Thus, (k_{2j})_{j≥0} is a decreasing sequence, while (k_{2j+1})_{j≥0} is an increasing sequence. They are both bounded sequences of positive integers, so eventually constant; that is, there exist k′ and k′′ (with k′ ≤ k′′) and a certain J such that

k_{2j+1} = k′ and k_{2j} = k′′ for j ≥ J.

If k′ = k′′, then k^{∗} = k′ = k′′ is the fixed point in (2), the possibility (i) in the theorem. Otherwise, let us suppose that k′ < k′′, so

k′ = π(n − k′′) < π(n − k′) = k′′.

Then π(n − k′) − π(n − k′′) = k′′ − k′, so there are k′′ − k′ prime numbers q_{j} such that

n − k′′ < q_{1} < q_{2} < ⋯ < q_{k′′−k′−1} < q_{k′′−k′} ≤ n − k′.  (4)

Except for 2 and 3, prime numbers are not consecutive numbers, so (4) is only possible in two cases:

• Case k′′ − k′ = 2, with n − k′′ = 1, n − k′ = 3, q_{1} = 2 and q_{2} = 3. In this case, we would have k′ = π(n − k′′) = π(1) = 0, which cannot happen because k′ is the limit of the increasing sequence (k_{2j+1})_{j≥0}.

• Case k′′ − k′ = 1, with a unique prime q_{1} = n − k′ in (4). Then k′′ = k′ + 1 and

π(n − k′) = k′ + 1, π(n − k′ − 1) = k′.

This is the possibility (ii) in the theorem.

Proof of Theorem 2. Let us first analyze the case (i). We have k^{∗} = π(n − k^{∗}) and p_{k^{∗}} ≤ p_{π(n−k^{∗})} ≤ n − k^{∗}, so k^{∗} + p_{k^{∗}} ≤ n. Thus, k^{∗} ∈ A where A is the set

A = {j ≥ 1 : j + p_{j} ≤ n}.

To conclude the proof of case (i), it is enough to check that max A = k^{∗} (in particular, this implies k^{∗} + p_{k^{∗}} = n′). Let us suppose that max A ≠ k^{∗}. In this case, k^{∗} + 1 ∈ A, so p_{k^{∗}+1} + k^{∗} + 1 ≤ n, and therefore p_{k^{∗}+1} ≤ n − k^{∗} − 1 ≤ n − k^{∗}. This implies that π(n − k^{∗}) ≥ k^{∗} + 1, which is false because π(n − k^{∗}) = k^{∗}.

In case (ii), we have

k′ = π(n − k′′) < π(n − k′) = k′′,

with k′′ = k′+1. Using that n−k′ is a prime number, we have p_{k′+1} = p_{k′′} = p_{π(n−k′)} = n−k′, so k′ + p_{k′+1} = n and then

k′ + p_{k′} < n < k′ + 1 + p_{k′+1}.

This clearly implies that n = k + p_{k} has no solution.

Finally, let us check that there cannot exist any solution of (1) not detected by the iterative method (2). Let us suppose, to the contrary, that k is a solution not detected by the method. Then n = k + p_{k} and π(n − k) = k, so k is a fixed point of k_{j+1} = π(n − k_{j}), that is, a fixed point of (2) except for the starting step k_{0} = π(n).

But we have proved that the iterative method (2), starting in k_{0} = π(n), converges to k^{∗} or to the 2-cycle {k′, k′′} with k′′ = k′ + 1. If (2) converges to k^{∗}, this k^{∗} is the unique solution of (1), so k = k^{∗}. If (2) converges to {k′, k′′}, then k < k′ or k > k′′. However, both cases are impossible:

k < k′ ⇒ k = π(n − k) ≥ π(n − k′) = k′′ ⇒ k ≥ k′′, a contradiction;

k > k′′ ⇒ k = π(n − k) ≤ π(n − k′′) = k′ ⇒ k ≤ k′, a contradiction. (5)

Then there cannot exist such a fixed point k.

3 Generalization to the equation n = ak + bp_{k}

A more general equation than (1) is

n = ak + bp_{k}  (6)

with b ∈ ℤ^{+} and a ∈ ℤ \ {0}. Given n, we want to know if there exists some k satisfying (6) and how to find it by the iterative process

k_{j+1} = π((n − ak_{j})/b),  j ≥ 0,  (7)

starting with k_{0} = π(n/b).

Of course, the reason to choose the iterative process (7) is that, if k is a solution of (6), then (n − ak)/b = p_{k}, a prime number, so π((n − ak)/b) = π(p_{k}) = k and k is a fixed point of (7).

Depending on whether a > 0 or a < 0, the beginning of the iterative process (7) varies. If a > 0 we have k_{1} ≤ k_{0}; however, if a < 0 we have k_{1} ≥ k_{0}. Moreover, if a < 0, the sequence ak + bp_{k} is not always increasing with k, so we cannot ensure that the solution of n = ak + bp_{k}, if it exists, is unique. These differences motivate to consider both cases a > 0 and a < 0 separately.

In what follows, we present this study in a more informal way, without stating the properties as theorems. Actually, the behavior of the iterative method and its relation with the solutions of (6) is similar to what happens in Theorems 1 and 2 in the case a > 0, but rather different in the case a < 0.

3.1 Case a > 0

Let us start noticing that we want the k_{j} that arise in the iterative method (7) to be positive integers (otherwise, p_{k_{j}} does not exist). Due to the equivalence π(x) ∼ x/ log(x) for x → ∞ (prime number theorem), we can guarantee that k_{j} > 0 for all j if n is large enough (the exact required size depends on a and b). Indeed, for n → ∞ we have

k_{0} = π(n/b) ∼ \frac{n/b}{log(n/b)} ∼ \frac{n}{b log(n)}

and

k_{1} = π((n − ak_{0})/b) ∼ \frac{(n − ak_{0})/b}{log((n − ak_{0})/b)} ∼ \frac{n}{b log(n)},

so k_{0}, k_{1} ≥ 1 if n is big enough. Then, given the equation n = ak + bp_{k}, we can assume that n satisfies

k_{1} = π((n − ak_{0})/b) = π((n − aπ(n/b))/b) ≥ 1  (8)

(this holds except for a finite set of n’s). Note that, for a = b = 1, (8) becomes π(n−π(n)) ≥ 1, which holds for every n ≥ 4. After imposing this technical restriction for small values of n, let us analyze the iterative method.

The assumption a > 0 gives k_{1} = π((n − ak_{0})/b) ≤ π(n/b) = k_{0}. From k_{1} ≤ k_{0}, it follows that k_{2} = π((n − ak_{1})/b) ≥ π((n − ak_{0})/b) = k_{1}, and from k_{2} ≥ k_{1}, we get k_{3} = π((n−ak_{2})/b) ≤ π((n−k_{1})/b) = k_{2}, and so on. Moreover, k_{2} = π((n−ak_{1})/b) ≤ π(n/b) = k_{0} and k_{3} = π((n − ak_{2})/b) ≥ π((n − ak_{0})) = k_{1}, and so on. In particular, if k_{1} ≥ 1 then k_{j} ≥ 1 for every j, so assuming (8) is enough to ensure that all the k_{j} will be positive integers.

Following as in the proof of Theorem 1 we get that (k_{2j})_{j≥0} is a decreasing sequence, (k_{2j+1})_{j≥0} is an increasing sequence, and there exist k′ and k′′ (with k′ ≤ k′′) and a certain J such that

k_{2j+1} = k′ and k_{2j} = k′′ for j ≥ J.

If k′ = k′′, then k^{∗} = k′ = k′′ is the fixed point in (6). Otherwise, if k′ < k′′ we have

k′ = π((n − ak′′)/b) < π((n − ak′)/b) = k′′

so π((n − ak′)/b) − π((n − ak′′)/b) = k′′ − k′, and there are k′′ − k′ prime numbers q_{j} such that

\frac{n − ak′′}{b} < q_{1} < q_{2} < ⋯ < q_{k′′−k′−1} < q_{k′′−k′} ≤ \frac{n − ak′}{b} .  (9)

From now on, the case k′ < k′′ is somewhat different.

Let us suppose that two of these primes are q_{1} = 2 and q_{2} = 3. Then (n − ak′′)/b = 1 and k′ = π((n − ak′′)/b) = π(1) = 0, which cannot happen. Therefore, we can assume that q_{j+1} − q_{j} ≥ 2 for all these primes q_{j}. Clearly, any interval (x, y] containing m of these primes must satisfy y − x > 2(m − 1). In the case (9), this means that

\frac{n − ak′}{b} − \frac{n − ak′′}{b} > 2(k′′ − k′) − 2,

that is, a(k′′ − k′)/b > 2(k′′ − k′) − 2, or

(2b − a)(k′′ − k′) < 2b.  (10)

Then two situations can occur:

• If a ≥ 2b, (10) is trivial and does not imply any restriction on k′ and k′′.

• If a < 2b, (10) can be written as

k′′ − k′ < \frac{2b}{2b − a}.  (11)

In the particular case a ≤ b we have 1 < 2b/(2b − a) ≤ 2, so (11) is equivalent to k′′ = k′ + 1 (recall that we are analyzing the case k′ < k′′).

In the case a ≤ b, the remaining arguments in the proofs of Theorems 1 and 2 are valid. In particular (5), which guarantees that the iterative method (7), starting at k_{0} = π(n/b), detects as fixed points all the solutions of n = ak + bp_{k}.

If a ≥ 2b or b < a < 2b, we cannot ensure that k′′ = k′ + 1. There might be an integer k with k′ < k < k′′ which is a fixed point

π((n − ak)/b) = k

and a solution of n = ak + bp_{k} not detected by the iterative method (7) starting in k_{0} = π(n/b). That is, the method converges to the 2-cycle {k′, k′′} instead of k. In practice, if we are looking for a solution of n = ak + bp_{k}, it is enough to check if every k satisfying k′ < k < k′′ is a solution.

Let us give some examples to illustrate that these situations can occur.

For the case a ≥ 2b, let us see what happens with the equation

n = 7k + 2p_{k}

for several values of n, with convergence to a fixed point k^{∗} or to cycles {k′, k′′} with different values of k′′ − k′. For n = 10 040, we have k_{0} = 672 and the iterative process converges to k^{∗} = 474, which is a solution of the equation; instead, for n = 10 041, again k_{0} = 672 and the iterative process converges to k^{∗} = 474, which is not a solution of the equation. For n = 10 073, we have k_{0} = 674 and the iterative process converges to the cycle {474, 476}.

For n = 10 300, we have k_{0} = 686 and the iterative process converges to the cycle {482, 485}. For n = 10 325, we have k_{0} = 687 and the iterative process converges to the cycle {483, 487}. For n = 10 532, we have k_{0} = 698 and the iterative process converges to the cycle {491, 497}. In all these cases, less that 10 iterations are enough to reach k^{∗} or {k′, k′′}.

For the case b < a < 2b, in the equation 12 660 = 3k + 2p_{k} we have k_{0} = 824 and the iterative method converges to the cycle {699, 701}, where k′′ − k′ = 2.

Let us also show some instances of the equation n = ak + bp_{k} with a solution k such that the iterative method (7) starting with k_{0} = π(n/b) converges to a cycle {k′, k′′}. For n = 2 · 33 + p_{33} = 203, where k = 33 is clearly a solution of n = 2k + p_{k}, the iterative method converges to the cycle {32, 34}, with k′′ − k′ = 2. For n = 6 · 100 + p_{100} = 1141, where k = 100 is the solution of n = 6k + p_{k}, the iterative method converges to the cycle {80, 121}, with k′′ − k′ = 41.

3.2 Case a < 0

Let us start noticing that, in general, ak+bp_{k} is not increasing with k when a < 0. Therefore, we cannot ensure the uniqueness of the solution of n = ak + bp_{k} for fixed a, b and n. For instance, n = 105 has two solutions k in the equation n = −2k + p_{k}:

105 = −2 · 43 + p_{43} = −2 · 44 + p_{44}.

With n = −3k + p_{k} we can also find two solutions that are not consecutive integers:

100 = −3 · 59 + p_{59} = −3 · 61 + p_{61}.

There can exist more than two solutions, as is the case of the equation n = −4k + p_{k}:

99 = −4 · 83 + p_{83} = −4 · 85 + p_{85} = −4 · 86 + p_{86}.

However, p_{k} always grows faster than k, so the sequence ak + bp_{k} is increasing with k if 0 < −a < b. In this case, again the solution of n = ak + bp_{k}, if it exists, is unique.

Anyway, taking into account that p_{k} ∼ k log k when k → ∞, we have ak + bp_{k} ∼ ak + bk log k = (a + b log k)k. Thus, ak + bp_{k} is increasing with k for k big enough. In particular, this ensures that, for fixed a, b and n, the number of solutions of n = ak + bp_{k} is always finite. Precise estimates of the form

C_{1} \frac{x}{log x} ≤ π(x) ≤ C_{2} \frac{x}{log x}

with C_{1}, C_{2} > 0, which yield an upper bound (depending on a, b, n, C_{1} and C_{2}) of the number of solutions, can be found in many texts of number theory (see, for instance, [2, Theorem 8.8.1]).

Now, let us analyze the behavior of the iterative method (7) starting in k_{0} = π(n/b). As shown below, nothing similar to (3) appears in the case a < 0; the property (3) is very important in the analysis of the case a > 0, and the lack of a suitable alternative is a great handicap. Although the analysis of the case a < 0 is presented here for completeness, it must be concluded that the iterative method described in this paper is not so useful to solve (6) as it is when a > 0.

Since a < 0, we have k_{1} = π((n − ak_{0})/b) ≥ π(n/b) = k_{0}; and, if we assume that k_{j} ≥ k_{j−1}, also

k_{j+1} = π((n − ak_{j})/b) ≥ π((n − ak_{j−1})/b) = k_{j}.

Then k_{j} is an increasing sequence and it cannot tend to a cycle.

Let s be any number such that

π((n − as)/b) ≤ s;  (12)

the existence of such an s follows from the estimate π(x) ∼ x/ log x when x → ∞. Then (recall that a < 0)

k_{0} = π(n/b) ≤ π((n − as)/b) ≤ s;

and assuming that k_{j} ≤ s gives

k_{j+1} = π((n − ak_{j})/b) ≤ π((n − as)/b) ≤ s.

This proves that the increasing sequence of integers k_{j} produced by the iterative method (7) starting with k_{0} = π(n/b) is bounded. So there exists some k^{∗} (and an index J) such that

k_{j} = k^{∗} for every j ≥ J,

and thus k^{∗} is a fixed point of (7).

We cannot ensure that the fixed point k^{∗} is a solution of (6). A solution of (6), if it exists, satisfies π((n − as)/b) = s; in particular, it also satisfies (12). Then k^{∗} ≤ s for any possible solution s of (6) such that s ≥ π(n/b) = k_{0}. In practice, we can continue checking whether k^{∗}, k^{∗} + 1, k^{∗} + 2,… are solutions or not of (6) until, when substituting in ak + bp_{k}, we get a value greater than n; actually, an additional precaution is necessary: we must continue the checking until reaching values of k for which the sequence ak + bp_{k} is already increasing.

For an example of this behavior, let us take n = −7 · 2000 + p_{2000} = 3389 (that is, a = −7 and b = 1), so s = 2000 is a solution of the equation 3389 = −7k +p_{k}. However, the iterative process k_{j+1} = π(3389 + 7k_{j}) starting in k_{0} = π(3389) = 477 converges to k^{∗} = 1989, which is not a solution of the equation. Observe that s − k^{∗} = 11.

Finally, let us observe an extra surprise: in the case a < 0, the fixed point k^{∗} of the iterative method is never a solution of n = ak + b_{k}. If the equation has no solutions, there is nothing to prove. If the equation has a solution s, let us prove that the fixed point k^{∗} cannot be k^{∗} = s, but k^{∗} < s. Indeed, it is enough to check that, if k_{j} < s, also k_{j+1} < s. We have (n − ak_{j})/b < (n − as)/b = p_{s}, a prime, so π((n − ak_{j})/b) < s. But π((n − ak_{j})/b) = k_{j+1}, so k_{j+1} < s, just as we were looking for.

4 Acknowledgments

I am grateful to Samuel Stigliano, an Uruguayan student (of medicine!), for the motivation to study this problem. In March 2021, he told me by email that both numbers of the amicable pair (220, 284) can be written as k + p_{k}, namely 220 = 41 + p_{41} and 284 = 51 + p_{51}, and he asked if a similar property happens with other pairs of amicable numbers (\underline{A259180} in the OEIS). Trying to answer his question, I wanted to decide if a number n can be written as n = k + p_{k} with a fast algorithm, and then I arrived at the iterative method presented in this paper. In particular, this allowed me to find some pairs of amicable numbers that satisfy the requested property; the smaller is

1 392 368 = 99 525 + p_{99 525}, 1 464 592 = 104 283 + p_{104 283}.

This pair of amicable numbers was discovered by Euler in 1747.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976.

[2] E. Ball and J. Shallit, Algorithmic Number Theory. Volume I: Efficient Algorithms, MIT Press, 1996.

[3] P. H. Bateman and H. G. Diamond, Analytic Number Theory: An Introductory Course, World Scientific, 2004.

[4] J. M. De Koninck and F. Luca, Analytic Number Theory: Exploring the Anatomy of Integers, American Mathematical Society, 2012.

[5] B. Fine and G. Rosenberger, Number Theory: An Introduction via the Distribution of Primes, Birkhäuser, 2007.

[6] M. P. Knapp and C. Xenophontos, Numerical analysis meets number theory: using rootfinding methods to calculate inverses mod p^{n}, Appl. Anal. Discrete Math. 4 (2010), no. 1, 23–31.

[7] D. J. Newman, Analytic Number Theory, Springer, 2000.

[8] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

   at https://oeis.org.

2020 Mathematics Subject Classification: Primary 11B83; Secondary 11A41, 11Y16, 37C25, 65H05. Keywords: integer sequence, prime number, iterative method to solve equations, dynamics.

(Concerned with sequences \underline{A014688}, \underline{A000045}, and \underline{A259180}.) Received March 21 2021; revised versions received March 23 2021; November 16 2021; November 21 2021. Published in Journal of Integer Sequences, November 27 2021. Return to Journal of Integer Sequences home page.