1
$\begingroup$

What are ten smallest natural numbers n, such that n and n+1 have digital sums which are not relatively prime?

$\endgroup$
6
$\begingroup$

Compared to a natural number n, n+1 has all its digits the same except that all trailing 9s become 0s, and the last non-9 digit of n is incremented (where we implicitly include a leading zero in n). Thus if n's digital sum is d(n), d(n+1) = d(n) + 1 - 9 t(n), where t(n) is the number of trailing 9s in n.

Clearly d(n) and d(n+1) must be coprime if t(n) = 0, since two consecutive natural numbers are always coprime. If d(n+1) is not coprime with d(n), it must share a factor greater than 1; this factor must thus also be a factor of d(n) - d(n + 1) = 9 t(n) - 1.

For t(n) = 1, 9 t(n) - 1 = 8, so it suffices that d(n) is even. For t(n) = 2, 9 t(n) - 1 = 17, so d(n) must be a multiple of 17 (and since there must be exactly two trailing 9s, the smallest such value is 8899 with digital sum 34).

We can easily find ten smaller naturals with only one trailing 9 and even digital sum; the ten smallest are: 19, 39, 59, 79, 109, 129, 149, 169, 189, 219.

$\endgroup$
2
  • $\begingroup$ Nice! I wonder, which is the first instance in which the common divisor is not 2. $\endgroup$ Oct 20 at 16:30
  • 1
    $\begingroup$ @BernardoRecamánSantos (39,40) has GCD of 4. If you mean odd GCD > 1, it is only possible when you go to x99 -> (x+1)00 (difference 17) or x999 -> (x+1)000 (difference 26), the smallest possible such number being (8899,8900). $\endgroup$
    – Bubbler
    Oct 21 at 0:54
2
$\begingroup$

Obviously, all consecutive integers are relatively prime. Thus, we must look at

places where the digital sums of integers are nonconsecutive. Specifically, we look at n ending with 9:

19, 20 (sums: 10, 2)
39, 40 (12, 4)
79, 80 (16, 8)
109, 110 (10, 2)
129, 130 (12, 4)
169, 170 (16, 8)
219, 220 (12, 4)
259, 260 (16, 8)
309, 310 (12, 4)
349, 350 (16, 8)

$\endgroup$
1
  • 2
    $\begingroup$ you're absolutely right on both counts lol. I'm not sure how I got mixed up on the first sentence, and I think at some point I switched "relatively prime" for "divisible" in my head. oh well. I've edited the first sentence, and since T. Linnell already got the right answer, I'll leave the rest unchanged $\endgroup$
    – juicifer
    Oct 20 at 15:51

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.