The Dividing Path

Number Theory Level 5

All the digits of the positive integer $N$ are either $0$ or $1$ . The remainder after dividing $N$ by $37$ is $18$ . What is the smallest number of times that the digit $1$ can appear in $N$ ?

Details and Assumptions :

This problem is not original.

The answer is 5.

6 solutions

Christopher Boo
Aug 7, 2014

EDIT: This solution is written with the help of Calvin Lin.

First, make sure you are familiar with the divisibility of 37 .

Did you noticed the trick? We can form a group of three and add it altogether.

Let $a$ be the number of 1's added in the hundredths.

Let $b$ be the number of 1's added in the tenths.

Let $c$ be the number of 1's added in the ones.

Now, the question can be translated to, solve

$100a+10b+c \equiv 18 \mod 37$

$26a+10b+c \equiv 18 \mod 37$

over non-negative integers, for the minimum value of $a+b+c$ .

By trial and error, we can easily get that $a=2$ , $b=0$ , $c=3$ satisfy the condition and it's the minimum value of $a+b+c$ . Hence, the answer is $5$ .

It is easier to translate this question to solving, over non-negative integers, for the minimum value of $a + b + c$ given that $10a + 26 b + c \equiv 18 \pmod{37}$ .

The solution is $a = 0, b = 2, c = 3$ .

Calvin Lin Staff - 6 years, 10 months ago

I'm a bit confused, do you mean

$\overline{abc}=18 \mod 37$

$100a+10b+c=18 \mod 37$

$26a+10b+c=18 \mod 37$ ?

Christopher Boo - 6 years, 10 months ago

No. My approach is very different from yours. Note that your solution is incomplete because it has not established that 5 is indeed the minimum.

My solution: (Let me change my notation slightly)
Observe that $10 ^ 0 \equiv 1, 10^1 \equiv 10, 10^2 \equiv 26, 10^3 \equiv 1 \pmod{37}$ . Now, given any binary string S, let the number of 1's in the 0 mod 3 place be a, the number of 1's in the 1 mod 3 place be b, the number of 1's in the 2 mod 3 place be c. Then $S \equiv a + 10b + 26c \pmod{37}$ .

As such, your question translates to finding the minimum, over non-negative integers, of $a+b + c$ , given that

$26a + 10b + c \equiv 18 \pmod{37}$

As mentioned, $a = 2, c = 3$ is the minimum solution (which is easily checked). An example of $S$ that this corresponds to is $1101101$ .

Calvin Lin Staff - 6 years, 10 months ago

@Calvin Lin – Ok! Do you want to post this as a formal solution instead in the comment section? Else I feel like deleting my solution, as mentioned, it's badly organised...

Christopher Boo - 6 years, 10 months ago

This is only a first draft I've written during midnight. Please suggest edits.

Christopher Boo - 6 years, 10 months ago

It’s easier is you write 26a + 10b + c  -11a + 10b + c  18  -19 mod 37

And then you see that a=2 and c=3 makes the sum = -19

Ignacio Alegre de Miquel - 6 years, 9 months ago

Grrrrrrrrrrrreat problem @Christopher Boo

Shubhendra Singh - 6 years, 8 months ago

Sarupya Ganguly
Sep 17, 2014

I did this : 37 * 18 = 666

666 in binary is : 1010011010

Minimum no. of 1s is : 5.

Simple. :)

Nit Jon
Apr 6, 2015

import java.util.ArrayList;

public class BinaryLoop {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    String num = "";
    int counter = 0;
    long count = 9223372036854775807L;
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i <= count; i++) {

        String bin = Integer.toBinaryString(i);

        if (bin.equalsIgnoreCase("10000000000000000000")) {
            break;

        } else {
            long binit = Long.parseLong(bin);
            if (checkMod(binit)) {
                list.add(checkdig(binit));
            }

        }
        int least = leastNum(list);
        System.out.println(least);
    }

}

public static boolean checkMod(long num) {
    if (num % 37 == 18)
        return true;
    else
        return false;

}

public static int checkdig(long num) {
    int occurance = 0;
    String number = num + "";
    char[] digits = number.toCharArray();
    for (int i = 0; i < digits.length; i++) {
        if (digits[i] == '1') {
            occurance++;
        } else {
        }

    }

    return occurance;

}

public static int leastNum(ArrayList<Integer> digit) {
    int least = 1000000;
    for (int i = 0; i < digit.size(); i++) {
        if (least >= digit.get(i)) {
            least = digit.get(i);
        }
    }
    return least;
}

}

Nafees Zakir
Sep 30, 2014

Here's my code for Python:

>>> min = 'inf'
>>> for a in range( 0,10):
        for b in range( 0,10):
            for c in range( 0,10):
                if((26*a+10*b+c)%37 == 18 and a+b+c<min):
                    print "%d + %d + %d = %d " % (a,b,c,a+b+c)


0 + 1 + 8 = 9 
0 + 5 + 5 = 10 
0 + 9 + 2 = 11 
1 + 2 + 9 = 12 
1 + 6 + 6 = 13 
2 + 0 + 3 = 5 
2 + 4 + 0 = 6 
2 + 7 + 7 = 16 
3 + 1 + 4 = 8 
3 + 5 + 1 = 9 
3 + 8 + 8 = 19 
4 + 2 + 5 = 11 
4 + 6 + 2 = 12 
4 + 9 + 9 = 22 
5 + 3 + 6 = 14 
5 + 7 + 3 = 15 
6 + 1 + 0 = 7 
6 + 4 + 7 = 17 
6 + 8 + 4 = 18 
7 + 2 + 1 = 10 
7 + 5 + 8 = 20 
7 + 9 + 5 = 21 
8 + 3 + 2 = 13 
8 + 6 + 9 = 23 
9 + 0 + 6 = 15 
9 + 4 + 3 = 16 
9 + 8 + 0 = 17

Here we can see from the Output when a=2, b=0, c=3 then we get minimum value = 5

King George
Aug 20, 2014

// using c++ for help

bool check(int n)

{

int x;

while(n)

{

    x=n%10;

    if(x>1) return false;

    n/=10;

}

return true;

}

int main( ) {

int n=18;

while(1)

{

    if(check(n)) break;

    n+=37;

}

cout<<n;

}

Sunil Bn
Aug 20, 2014

JavaScript for(var i =1;i<200;i++){ var b = (i).toString(2); var res1 = parseInt(b) % 37; if(res1 == 18) console.log("Great Number "+ b + " at "+i); }

The Dividing Path

The answer is 5.

6 solutions

0 pending reports