Vedic Divisibility

July 8, 2011

Vedic arithmetic is a system of arithmetic devised in India for pencil-and-paper calculations. One of the calculations determines if one number is a divisor of another; the divisor must be odd and not divisible by 5; if the divisor is even or divisible by 5, factors of 2 and 5 should be removed before continuing. The calculation is a three-step process:

1) Determine the osculator of the divisor by multiplying it by the smallest number that will make the last digit 9, then strip the last digit 9 and add 1.

2) For each digit in the dividend, strip the last digit, then add that last digit times the osculator to the remaining digits in the dividend, giving a new dividend. Repeat as long as the dividend keeps decreasing.

3) Finally, divide the remaining dividend by the original divisor. If the remainder is 0, then the original divisor evenly divides the original dividend; otherwise not.

Here’s an example. For a divisor of 23, the number 23 is multiplied by 3, giving 69, then the last digit 9 is stripped, giving 6, and 1 is added, giving 7; thus, the osculator for 23 is 7. To test if 13174584 is divisible by 23, strip the 4 from the end of 13174584, multiply the stripped 4 times the osculator 7, giving 28, and add 28 to the stripped dividend 1317458 giving 1317486. Repeat, giving a new dividend of 131748 + 42 = 131790. Repeat again, giving a new dividend of 13179 (you can always drop a trailing 0, because 0 times the osculator is 0). Another iteration gives a new dividend of 1317 + 63 = 1380, from which we drop the trailing 0, giving 138. One final iteration gives 13 + 56 = 69. Now 69 ÷ 23 = 3, so 23 divides 13174584 and we are finished.

It is obviously easier for a computer to just perform the division and check the remainder; this method is intended for pencil-and-paper calculation (or even mental calculation).

Your task is to write a function that implements the Vedic divisibility test. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

About these ads

Pages: 1 2

5 Responses to “Vedic Divisibility”

  1. arturasl said

    Solution in Python:

    def divides(dividend, divisor):
        endings = {1 : 9, 3 : 3, 7 : 7, 9 : 1}
    
        if divisor % 10 not in endings:
            raise Exception('divisor should end in 1, 3, 7 or 9')
    
        osculator = ((divisor * endings[divisor % 10]) // 10) + 1
    
        while True:
            prev_dividend = dividend
            dividend = dividend // 10 + (dividend % 10) * osculator
    
            if prev_dividend <= dividend:
                dividend = prev_dividend
                break
    
        return (dividend % divisor) == 0
    
    print(divides(13174584, 23))
    
  2. WillJ said
    #include <iostream>
    
    using namespace std;
    
    int findOsculator( int num )
    {
        int temp, i = 1;
        do
        {
            temp = num * i;
            i++;
        }
        while( temp % 10 != 9 );
        temp = temp / 10;
        return temp + 1;
    }
    
    bool divisible(int dividend, int divisor)
    {
        int remainder,prev_dividend, osc;
        osc = findOsculator( divisor );
        do
        {
            prev_dividend = dividend;
            remainder = dividend % 10;
            dividend = (dividend / 10) + (osc * remainder);
        }
        while( dividend < prev_dividend );
        return !( dividend % divisor );
    }
    
    int main()
    {
        cout << divisible(13174584,23);
    }
    
  3. Graham said

    Python:

    def is_divisible(n, d):
        osc = 1 + (d * {1: 9, 3: 3, 7: 7, 9: 1}[d % 10]) // 10
        old, new = float('inf'), n
        while new < old:
            a, b = divmod(new, 10)
            old, new = new, a + b * osc
        return new % d == 0
    
    if __name__ == "__main__":
        for (n, d) in [(13174584, 23), (175121, 37), (134567, 29)]:
            print "Is %d divisible by %d?%7s" % (n, d, "Yes." if is_divisible(n, d)
                                                 else "No.")
    

    And since Remco hasn’t jumped on it yet, here’s my attempt in Haskell:

    import Data.Map
    
    osculator :: (Integral a) => a -> a
    osculator d = f e where
              f x = 1 + d * x `div` 10
              e = fromList [(1,9), (3,3), (7,7), (9,1)] ! (d `mod` 10)
    
    isDivisible :: (Integral a) => a -> a -> Bool
    isDivisible n d = aux old new where
                old = n + 1
                new = n
                osc = osculator d
                aux x y | x <= y            = y `mod` d == 0
                        | otherwise         = aux y (a + b * osc) where (a,b) = divMod y 10
    
    main :: IO ()
    main = mapM_ (\(n,d) -> print $ "Is " ++ show n ++ " divisible by " ++ show d ++
         "? " ++ show (isDivisible n d)) [(13174584, 23), (175121, 37), (134567, 29)]
    
  4. Mike said

    Just to be different, how about an F# version.

    
    exception BadValue of string
    
    let osculator n = 
        match (n / 10, n % 10) with
        | d,1 -> d*9 + 1
        | d,3 -> d*3 + 1
        | d,7 -> d*7 + 1
        | d,9 -> d   + 1
        | _,_ -> raise <| BadValue("divisor cannot be divisible by 2 or 5")
    
    let isdivisible dividend divisor =
        let osc = osculator divisor
        let rec loop old_dividend =
            let new_dividend = old_dividend / 10 + old_dividend % 10 * osc
            if new_dividend >= old_dividend then
                old_dividend % divisor = 0
            else
                loop new_dividend
        loop dividend
    
  5. Mike said

    Line 07 above should be:

        | d,7 -> d*7 + 5   // 7*7 = 49, so carry the 4
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 634 other followers

%d bloggers like this: