1
$\begingroup$

How to find the minimum possible number of length N ,which is simultaneously divisible by the single digit prime number like 2,3,5,7 ?like of length 5 minimum possible number is 10080.

  • 0
    No, $N$ is the length. I used $n$ to represent a number which is a multiple of 210. You need to find the smallest $n$ which is a multiple of 210 and has length $N$.2012-11-25

3 Answers 3

2

Just for an alternate solution, you are looking for the smallest non-negatiave integer $r_N$ such that $210\mid 10^{N-1}+r_N$, that is, such that $r_N\equiv -10^{N-1}\pmod {210}$.

But $-10^{N-1}$ is necessarily cyclic, and since it is always zero mod $2$ and $5$ and $-1$ mod $3$ for all $N>1$, the only relevant factor is $7$, and therefore it has a cyclic length of at most $6$.

Indeed, we quickly get that $r_2=200,r_3=110,r_4=50,r_5=80,r_6=170, r_7=20$, and then it cycles back to $r_8=200$.

The advantage to this version is that you don't need to divide $10^{N-1}$ by $210$ to get the result for large $N$. For example, the smallest number for $N=62$ is $10^{61}+200$.

1

As the lcm of $2,3,5,7$ is $210,$ we need to find the minimum multiple in $N$ digits.

So, $N$ must be $\ge 3$ to admit solution.

The minimum natural number with $N$ digits is $M=100\cdots00$ with $(N-1)$ zeros.

So, if $D=\lfloor\frac M {210}\rfloor,$ the answer will be $210(D+1)$

For example if $N=4,D=\lfloor\frac {1000} {210}\rfloor=4,$ the answer will be $210(4+1)=1050$

As pointed out by Thomas in his comment,

we can use Carmichael Function, $\lambda(21)=lcm(\lambda(3), \lambda(7))=lcm(2,6)=6$

So, $10^6\equiv1\pmod {21}\implies 10^{6m}\equiv1\pmod {21}$

$\implies 10^{6m+1}\equiv{10}\pmod {210},$ the minimum number with length $(6m+1+1)=6m+2,$ will be $10^{6m+1}+(210-10)$

$\implies 10^{6m+2}\equiv{100}\pmod {210},$ the minimum number with length $6m+3,$ will be $10^{6m+1}+(210-100)$ and so on.

  • 0
    It was great .Thanks2012-11-25
0

The first thing to realize is that any number that is divisible by such a number has to be of the form 2*3*7*M = 210 * M, for some M$\in$ N. Therefore, such numbers are of the form: 210*1, 210*2, 210*3, 210*4, and so on.

We now need to find the first n-digit number which is divisible by 210. The first n-digit number is $10^n$. To find the nearest number that is divisible by 210, we need to iterate from [$10^n$, $10^n + 210$) to find the number that is divisible by 210. One in every 210 consecutive numbers is divisible by 210.

Ex: For n = 6, the minimum possible 6-digit number is 100000. To find the first 6-digit number that is divisible by 210, iterate from 100000 to 100210 and report the number that is divisible by 210. In this case, that number is 100170.

Sometimes when you're dealing with these type of problems in competitive programming, n may be very large and $10^n$ may not be representable as an integer on a machine. We need to deal with it as a string. We need to figure out what number should be added to $10^n$, in order to make it divisible by 210.

$10^n$ mod 210 can be found by representing the number as a string. (An easy method exists, just google it).

Let k = $10^n$mod(210). Then the answer is $10^n$+210-k because (210-k) is the least number that needs to be added to $10^n$ to make the modulus 0.