1
$\begingroup$

A question in Google Code Jam 2019 qualification round wanted a positive integer n which contains at least one digit 4 to be represented as a sum of two positive integers a and b, neither containing 4.

For my solution, I found that simply replacing all 4s in n with 3s to get a always results in no 4s in b for all n < 100,000,000 (when it starts taking too long on my puny laptop). Can it be proven that this method always works for any integer n?

More generally, can I always replace digit d with d - 1, for n > 1?

$\endgroup$
  • $\begingroup$ A friend just pointed out that the 4-to-3 case is obvious: b just contains 1s in the same position as the 4s and 0s otherwise. I'm still unsure about the general case, though, especially for d = 1. $\endgroup$ – Gnubie Apr 7 at 21:04
1
$\begingroup$

It is easy to construct the desired summands :

To get the first summand, replace every digit $\ 4\ $ by digit $\ 2\ $ The difference between those numbers only contains twos and zeros and a representation is found.

$\endgroup$
1
$\begingroup$

For 2 ≤ d ≤ 9, the method in my comment always works as b just contains 1 in the same position as any d and 0 otherwise. E.g. for d = 2, n = 25225222,

 25225222
—15115111
—————————
 10110111

For d = 0, put 9 in the same position as any 0 and 9 otherwise.

d = 1 is interesting. With this program:

def is_bad(x): return '0' in str(x)
for n in range(1, int(1e5) + 1):
  if (is_bad(n)):
    is_ok = False
    for a in range(1, n):
      b = n - a
      if (not (is_bad(a) or is_bad(b))): is_ok = True; break
    if (not is_ok): print('%d has no solution!' % (n))
    # else: print('%d = %d + %d' % (n, a, b))

I got

1 has no solution!
19 has no solution!
21 has no solution!
199 has no solution!
201 has no solution!
219 has no solution!
221 has no solution!
1999 has no solution!
2001 has no solution!
2019 has no solution!
2021 has no solution!
2199 has no solution!
2201 has no solution!
2219 has no solution!
2221 has no solution!
19999 has no solution!
20001 has no solution!
20019 has no solution!
20021 has no solution!
20199 has no solution!
20201 has no solution!
20219 has no solution!
20221 has no solution!
21999 has no solution!
22001 has no solution!
22019 has no solution!
22021 has no solution!
22199 has no solution!
22201 has no solution!
22219 has no solution!
22221 has no solution!

There are 2 ^ (m - 1) values of n with m digits with no solution. For m > 2, prepend 1 and append 0 to the binary representation of values from 0 to 2 ^ (m - 2), zero-padded to m - 2 digits; multiply the result by 2; and ± 1.

So it's possible to find a pair for all d except 1!

$\endgroup$

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.