3
$\begingroup$

Suppose that we take two natural numbers $a$ and $b$ with $a<b$.

Then, we may try to arrive at $b$ by starting at $a$ by this set of rules:

1) To arrive at $a_1$ which is such that we have $a< a_1 \leq b$ it is only allowed that we sum $a$ with one of its divisors different from $1$. If $a_1=b$ we are done.

2) If $a_1<b$ then to arrive at $a_2$ which is such that we have $a<a_1<a_2\leq b$ we perform step 1) with $a_1$.

3) Repeat 2) until we arrive at $a_{k(a,b)}=b$

As an example, take $a=12$ and $b=100$, we have $12 \to 16 \to 20 \to 40 \to 80 \to 100$.

As an example where $\gcd (a,b)=1$ take $a=15$ and $b=22$. Then we have $15 \to 18 \to 20 \to 22$.

As an example where $\gcd (a,b)=1$ and where we cannot arrive at $b$, take $a=18$ and $b=23$.

Of course, $k(a,b)$ can be multi-valued since for the example $a=12$ and $b=100$ we also have $12\to 24\to 48\to 96\to 100$. But this question is not about behaviour of $k(a,b)$ (although it could be that its behaviour has some awesome features).

If this procedure exists for some $a$ and $b$ and $a<b$ we may say that $b$ is reachable by $a$.

Can we find some condition(s) on $a$ and $b$ that is(are) both necessary and sufficient to guarantee that $b$ is reachable by $a$?

Since I am not sure did I explain this procedurally in a good way by 1), 2) and 3), I will describe here again the procedure in other words. It is very simple: choose natural numbers $a$ and $b$ with $a<b$. We are trying to arrive at $b$ by adding to $a$ some divisor of $a$ different than $1$. Then we arrive at $a_1=a+\alpha_1$ , where $\alpha_1 | a$. Then if we did not arrive at $b$ with that single step, we add to $a_1$ some divisor of $a_1$ different than $1$ to arrive at $a_2=a_1 + \alpha_2$, where $\alpha_2 | a_1$. We repeat this until we arrive at $b$, if possible. The question is: when is this possible?

$\endgroup$
14
  • $\begingroup$ Do you have an example of a prime $ b $ reachable by some $ a<b $? $\endgroup$ Sep 26, 2017 at 18:10
  • 1
    $\begingroup$ @SylvainJULIEN No, since such an example does not exist. $\endgroup$
    – user114642
    Sep 26, 2017 at 18:27
  • 1
    $\begingroup$ Does the following shorter description capture your procedure correctly? "For natural numbers $a$ and $b$ with $a < b$, we say that $b$ is one-step reachable from $a$ if $b - a$ is a divisor of $a$ other than $1$. We say that $b$ is $n$-step reachable from $a$ if there is a sequence $a = a_0, a_1, \dotsc, a_n = b$ in which $a_{i + 1}$ is one-step reachable from $a_i$ for all $0 \le i < n$." Then maybe you want to define $k(a, b)$ to be the set of all $n$ for which $b$ is $n$-step reachable from $a$, or to be the minimum of that set? $\endgroup$
    – LSpice
    Sep 26, 2017 at 18:55
  • $\begingroup$ @LSpice I added description of the procedure in other words under the question raised in the text, you will not face any difficulties or ambiguities when reading it. $\endgroup$
    – user114642
    Sep 26, 2017 at 18:57
  • 2
    $\begingroup$ $$12 \to 15 \to 18 \to 20$$ $\endgroup$
    – user114642
    Sep 26, 2017 at 19:43

2 Answers 2

3
$\begingroup$

When $\gcd(a,b)>1$, then we can reach $b$ from $a$ by simply repeatedly adding $\gcd(a,b)$.

The least reachable number (LRN) from $a$ is adding its smallest prime divisor, and the greatest "arrivable" number (GAN) to $b$ is subtracting its smallest prime divisor. LRNs and GANs are always even (when defined). Since even numbers have $\gcd$ at least $2$, they are reachable when the difference between $a$ and $b$ is "large".

So the full statement is:

for $a<b$, $a$ can arrive at $b$ iff exactly one of the following holds:

  1. $a$ can arrive at $b$ in $1$ step $\iff 1<b-a=\gcd(a,b)$
  2. $a$ can arrive at $b$ in $2$ or more steps $\iff$ GAN of $b$ exists and is at least LRN of $a$

Sufficiency is constructive and necessity is obvious by definition of LRN and GAN.

$\endgroup$
2
  • $\begingroup$ You can reword it to two exclusive conditions, amounting to your 1. and the last half of your 4. Gerhard "Brevity: The Soul Of Math?" Paseman, 2017.09.26. $\endgroup$ Sep 26, 2017 at 21:06
  • $\begingroup$ 1 and last half of 4 weren't quite exclusive, but now they are. $\endgroup$
    – 8163264128
    Sep 26, 2017 at 22:04
1
$\begingroup$

Let lpf stand for least prime factor. (Assuming gcd(a,b) is 1 and also both are larger than 1,) If b is at least as big as a plus lpf(a) plus lpf(b), then you can reach b from a. This is because you can almost always take steps of size 2 to reach the goal. When you can't take a step of size 2, then b must be at most lpf(a) plus lpf(b) plus a, and if b is reachable at all it must be at least that big.

Gerhard "Taking Small Steps Is Easier" Paseman, 2017.09.26.

$\endgroup$
7
  • $\begingroup$ Of course, if gcd(a,b) is bigger than 1, then it is possible, especially if b-a is the least prime factor of both b and a. Gerhard "Also Leaves That To Reader" Paseman, 2017.09.26. $\endgroup$ Sep 26, 2017 at 19:58
  • $\begingroup$ Further, one can always take a step to reach an even number, so an upper bound for minimal k(a,b) is 2 log_2 b . Gerhard "And Lower Bound Of Zero" Paseman, 2017.09.26. $\endgroup$ Sep 26, 2017 at 21:13
  • $\begingroup$ Why $k(a,b)$ seems to be always divisor either of $a$ or $b$ or both? $\endgroup$
    – user114642
    Sep 27, 2017 at 7:26
  • $\begingroup$ Sorry, it is not always the case that it is so. $\endgroup$
    – user114642
    Sep 27, 2017 at 7:31
  • $\begingroup$ It does not need to be. Consider a and b squares of primes which differ by two. K can be 4 or 5, depending on how you count it. Gerhard "There Are Many Other Examples" Paseman, 2017.09.27. $\endgroup$ Sep 27, 2017 at 7:33

Your Answer

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