Smallest multiple having only 0 and 4 as its digits

Question

Given a number A find the smallest number B, such that A * B contains digits 4 and 0 only and zeroes should only be in the end i.e. numbers like 404 are not valid.

For example:

| A | B   | A*B |
|---|-----|-----|
| 1 | 4   | 4   |
| 2 | 2   | 4   |
| 3 | 148 | 444 |
| 4 | 1   | 4   |
| 5 | 8   | 40  |

---

Well, I attempted the question in this manner. Maintain a queue of integers. The smallest possible number is 4.

Pop the number (i.e. the front element of the queue) and push the numbers that can be derived from this popped number. 
That is , when we pop 4, we push (4*10) = 40 and (4*10 + 4) = 44 with the constraint that the popped number is not divisible by 10. If it is, push only its next multiple of 10.

So, my queue will be like: 4,40,44,400,440,444,....

As I am popping elements from the queue, I'll check if it is divisible the given number A. If yes, just break and the number popped is my desired result.

Because my number can be really large, I maintained a queue of pair<string,int> where string corresponds to the number and int corresponds to the remainder. Thus, remainder of the next stage can be computed easily.

Ex:

queue : <"4",4> 
Pop , current result is string : "4" and remainder is lets say prev = 4
check if the last digit is 0 or not (for checking if its a multiple of 10 or not)
If not, then append 0 to this string and remainder as (prev*10)%a and push this pair in the queue. Also, append 4 to this string with remainder as : (prev*10 +4)%a and push. If the last digits is 0, append 0(not 4) and corresponding remainder, push this pair in the queue.

Queue: <"40",(prev*10)%a>, <"44", (prev*10 +4)%a> and so on..

Till the pair in the front of the queue has remainder 0, we'll continue doing this.

Though this improvement seemed to be a bit good, but not correct and didn't pass all the test cases. Can someone please throw some light on how this should be solved in an optimal manner. (The range of A is 10^10).

Answer 1

If I understand the problem, solutions must match the regualr expression 0|4+0*

It mades looong time I do not program in C, but following code could do the trick.

int calc( int n ) {
  int factor5;
  int factor2;
  int j;
  int a;
  int b;
  int i;

  /* trivial case 0 result is 0 */
  if( n==0 ) return 0;

  /* find the number of factors 2 and 5 in n */
  for( a=n, factor5=0; a%5==0; a/=5, factor5++ ); 
  for( a=n, factor2=0; a%2==0; a/=2, factor2++ ); 

  /* result is r=b*a where a=2^(j+2)*5^j */
  j=factor5;
  if( j < factor2-2 ) j=factor2-2; 

  for( a=4,i=0; i<j; i++, a*=10 ); 

  /* generate b in 1, 11, 111, ... until solution found */ 
  for( b=1; (a*b)%n!=0; b=10*b+1 );
  return a*b;
}

it can be tested with:

int main ( void ) {
  int n,r;

  for( n=0; n<10; n++) {
    r=calc(n); printf( "n=%d r=%d\n", n, r );
  }

  return 0;
}

Note: Optimize it. Alsochange "int" to "long", "long long" or use a librarian of any length integers.

Tests:

n=0 r=0
n=1 r=4
n=2 r=4
n=3 r=444
n=4 r=4
n=5 r=40
n=6 r=444
n=7 r=444444
n=8 r=40
n=9 r=444444444

Rationalle:

In addition to the trivial case 0 with result 0, the result "r" must match the regular expression "4+0*": fours followed by zeros. That is, in normal arithmetics, r=x*10^j where x is in 4,44,444,... .

If we extract the factor of 4, we have r=x*4*10^j with x in the sequence 1, 11, 111, ... . Note than numbers in this sequence has never factors 2 nor 5 (they are not even numbers nor finish by 0 or 5).

In conclusion, r=x*2^(j+2)*5^j, with x in 1, 11, 111, ... and "j" obtained from the factorization of the argument. The first step of the program is calculate "j", next calculate a=2^(j+2)*5^j, and finally generate the sequence 1, 11, 111, ... and test it until first valid result.

Answer 2

Let's call the 40-number C, i.e. C = A x B.

Given the constraints as I understand them, this makes C = AxB from language 4^n 0^m (don't read this as 4 to the power n, it is intended to mean repeat 4 n times) so we need only n and m to describe C.

Observations:

1. Finding the smallest B is equivalent to finding the smallest C that is a multiple of A.
2. When two C-numbers have a different number of digits the C with the higher number of digits is larger.
3. When two C-numbers have an equal number of digits n + m, the C with the higher number of 4s is larger.

Hence, we loop over number of digits in C (starting with 1 and increasing) and over the number of 4s in a C with a fixed number of digits, again starting with a single 4 and increasing. This gives us all the possible C-numbers in numerical order.

As noted and put to use in @pasaba por aqui's answer, it is possible to reduce the search space by making use of the fact that A and C might share prime factors. In this case, every C always at least has the prime factor 2 (2^2 = 4) and possibly 5 (2*5 = 10).

Indeed, C = x * 2^(j + 2) * 5^j with x in [1, 11, 111, ...] (i.e. C = x * 4 * 10^j). The smallest j is equal to the highest number of 2 or 5 factors in A. E.g. if A % 25 == 0, j needs to be 2, if A % 400 == 0, j needs to be 4 and so on.

See pasaba por aqui's answer for that solution.

Brute force version:

#include <cstdint>
#include <iostream>


int
main(int, char *[])
{
    // use uintmax_t and hope that the number still fits.
    uintmax_t = 13ul; // or whatever

    for (unsigned k = 1u;; ++k) {
        // k is the number of digits
        for (unsigned m = 1u; m <= k; ++m) {
            // m is the number of 4s. 
            // We start at one 4 (zero does not make sense)
            uintmax_t C = 0u;
            // build C, add as many 4s as requested and
            // fill up with zeros
            for (unsigned i = 0; i < k; ++i) {
                if (i < m) {
                    C = C * 10 + 4;
                } else {
                    C = C * 10;
                }
            }
            // check if we have a multiple of A
            if (C % A == 0) {
                std::cout << "C = " << C << std::endl;
                std::cout << "B = " << (C / A) << std::endl;
                return 0;
            }
        }
    }

    return 1;
}

Answer 3

Here I give an efficient algorithm, i.e. one that works in time (edit: correction) polynomial in the value of A to solve the question for number A. I also give a proof that this number N exists for all numbers A and prove the correctness of my algorithm -- the proof shows that for any number A, the right answer has at most A^2 4's in it (and the number of zeros is at most something like twice the number of digits of A, crudely). (I don't know if A^2 fours is the best bound but I think it's probably not too far off.) The running time is not going to be more than polynomial in the size of A or the output. (I didn't work it out exactly.) Seeing the other answers now, it's basically the same as pasaba por aqui's answer but I think I give a more rigorous explanation of why it works. (Although my writing could be improved probably...)

Terminology: In the sequel, I'm going to say that a number N has the form {STRING} to mean that it's decimal expansion matches a regular expression {STRING}, even though that is not standard number theory terminology.

Problem: Given A, Find the smallest integer N of the form "4+0*" such that N mod A = 0

Step 1: Consider 10 mod A, and in particular the sequence { 10^n mod A } for n = 1,2,3,...

First obvious question is, what happens if 10 is invertible mod A, i.e. 10 is coprime to A, vs. if it isn't. (Edit: this is not actually obvious, but in 90% of these elementary number theory things, the way to make progress is to do some case analysis based on the prime factorizations of numbers involved, and thinking about when things are coprime vs. when they share common factors is often a good direction.)

If 10 is not coprime to A, there are a few possibilities. One is that 10 divides A, this is a silly case. We can simply divide A by 10, find the answer then, and multiply it by 10. If that's ruled out, then either 5 divides A, but 2 does not, or 2 divides A but 5 does not, or A is coprime to 10.

Suppose 5 divides A, but 2 does not. If N mod A = 0 has the form above, consider N mod 5 -- it is equal to the lowest order digit since 5 | 10. Therefore the lowest order digit must be 0 and not 4, so 10 | N. That is, in this case, any integer of the form "4+0*" such that N mod A = 0, also has N mod 2A = 0. And 10 divides 2A so this means we can reduce to a simpler problem.

Suppose 2 divides A, but 5 does not. It's obvious that 4 in fact divides any number of the form "4+0*", so for any odd number A', the smallest integer N as described is that same whether we take A to be A', 2A', or 4A'. Now suppose that 8 divides A. Since 8 divides any number of the form "40+", and 8 does not divide 4, by a similar argument as before it implies that the number N must have zero as its lower digit, so if 8 | A, it implies that if N mod A = 0, then also N mod 5A = 0. So we can move to this number, and then pull out a power of 10 and reduce to a simpler question.

Thus we can restrict attention to the case that 10 is coprime to A.

This simplifies things because then elementary number theory (chinese remainder theorem) tells us that 10 is invertible mod A, i.e. 10^k = 1 mod A for some large enough k. It means also that we can ignore the possibility of zeros in the digits of N -- since if X * 10^y = 0 mod A, and 10 is invertible mod A, we must also have that X = 0 mod A, which would be a smaller solution.

Thus once 10 is coprime to A, the smallest integer N of the form "4+0*" such that N mod A = 0 is the same as the smallest integer of the form "4+" such that N mod A = 0.

(Additionally, its now clear that there always exists SOME integer N of this form is that divisible by A. So all these programs indeed terminate and do not infinite loop for any input :) Because, we can do a win-win analysis. Suppose that 10^k = 1 mod A. Now consider the value of the decimal number K made of exactly k 4's, reduced modulo A. If this is zero, then that proves the number exists and we're done. If it's not zero, then say it is some value "a" mod A not equal to 0. We know that the number K * 10^k is also equal to "a" mod A, because 10^k = 1 mod A. And K * 10^k also has the form we care about, and this is true also for K * 10^{ik} for any i. Thus if we take a decimal number made of exactly A * k 4's, it must be equal to A*a = 0 mod A. Thus we have constructed a number N of the desired form which is divisible by A.)

Now we can solve the problem without brute force directly by a simple for loop. We just keep track of the value "4000000... mod A" and the value "444444.... mod A" where the numbers are k digits long, and we figure out these modulo values for k+1 digit numbers by, multiplying the value of the first by the value of 10 mod A, reducing modulo A, then adding this also to the second and reducing that modulo A.

Here's the complete code:

#include <cassert>
#include <iostream>

typedef unsigned long long ul;

ul fast_finder(ul A) {
  assert(A);
  ul num_zeros = 0; // remember how many zeros we need to add at the end

  while ((A % 10) == 0) {
    A /= 10;
    ++num_zeros;
  }

  while ((A % 5) == 0) {
    A /= 5;
    ++num_zeros;
  }

  while ((A % 8) == 0) {
    A /= 2;
    ++num_zeros;
  }

  while ((A % 2) == 0) {
    A /= 2;
  }

  ul four_mod_A = 4 % A;
  ul ten_mod_A = 10 % A;

  ul num_fours = 1;
  // in these variable names "k" is the number of fours we are considering
  ul four_times_ten_to_the_k_mod_A = four_mod_A;
  ul sum_of_fours_mod_A = four_mod_A;
  while (sum_of_fours_mod_A) {
    four_times_ten_to_the_k_mod_A *= 10;
    four_times_ten_to_the_k_mod_A %= A;
    sum_of_fours_mod_A += four_times_ten_to_the_k_mod_A;
    sum_of_fours_mod_A %= A;
    ++num_fours;
  }

  // now build an integer representation of the result from num_fours, num_zeros
  ul result = 0;
  while (num_fours) {
    result *= 10;
    result += 4;
    --num_fours;
  }
  while (num_zeros) {
    result *= 10;
    --num_zeros;
  }
  return result;
}

// This is to check the correctness of the fast algorithm, it's just the naive algorithm.
ul slow_finder(ul A) {
  assert(A);
  for (ul B = 1;;++B) {
    ul N = B * A;
    bool saw_four = false;
    while (N) {
      ul low = N % 10;
      if (low == 4) {
          saw_four = true;
      } else if (low != 0 || saw_four) { break; }
      N /= 10;
    }
    if (N == 0)
      return A*B;
  }
}

void check(ul x) {
  std::cout << x << ": ";
  ul f = fast_finder(x);
  std::cout << f << std::flush;
  ul s = slow_finder(x);
  if (f != s) {
    std::cout << "failed! ( " << s << " )" << std::endl; return;
  }
  std::cout << '.' << std::endl;
}

int main() {
  check(1);
  check(3);
  check(4);
  check(5);
  check(10);
  check(11);
  check(13);
  check(15);
  check(18);
  check(73);
  check(64);
  check(52);
}