algorithm - How to find the smallest number with just 0 and 1 which is divided by a given number?

Question

Every positive integer divide some number whose representation (base 10) contains only zeroes and ones.

One can prove that:

Consider the numbers 1, 11, 111, 1111, etc. up to 111... 1, where the last number has n+1 digits. Call these numbers m₁, m₂, ... , m_n+1. Each has a remainder when divided by n, and two of these remainders must be the same. Because there are n+1 of them but only n values a remainder can take. This is an application of the famous and useful “pigeonhole principle”;

Suppose the two numbers with the same remainder are m_i and m_j , with i < j. Now subtract the smaller from the larger. The resulting number, m_i?m_j, consisting of j - i ones followed by i zeroes, must be a multiple of n.

But how to find the smallest answer? and effciently?

Answer 1

The question equals to using 10ⁱ mod n (for each i, it can be used at most once) to get a sum m of n. It's like a knapsack problem or subset sum problem. In this way, dynamic programming will do the task.

In dynamic programming the complexity is O(k*n). k is the number of digits in answer. For n<10⁵, this code works perfectly.

Code:

#include <stdio.h>
#define NUM 2000

int main(int argc, char* argv[])
{
    signed long pow[NUM],val[NUM],x,num,ten;
    int i,j,count;
    for(num=2; num<NUM; num++)
    {
        for(i=0; i<NUM; pow[i++]=0);
        count=0;
        for(ten=1,x=1; x<NUM; x++)
        {
            val[x]=ten;

            for(j=0; j<NUM; j++)if(pow[j]&&!pow[(j+ten)%num]&&pow[j]!=x)pow[(j+ten)%num]=x;
            if(!pow[ten])pow[ten]=x;
            ten=(10*ten)%num;
            if(pow[0])break;
        }

        x=num;
        printf("%lddivides",x=num);
        if(pow[0])
        {
            while(x)
            {
                while(--count>pow[x%num]-1)printf("0");
                count=pow[x%num]-1;
                printf("1");
                x=(num+x-val[pow[x%num]])%num;
            }
            while(count-->0)printf("0");
        }
        printf("
");
    }
}

PS: This sequence in OEIS.