Give an algorithm that determines whether a given number is divisible by 11 or not. The number could have up to one million digits.

(Note that simply dividing by 11, or doing long division by 11 is not allowed as a solution.)

So as not to overflow, the individual odd and even digit counters are kept mod 11. The digits are read off a file. Anything other than a digit or a comma stops the number, and commas are ignored.  As a bonus, the congruence mod 11 is given.

OPEN "number.txt" FOR BINARY AS #1
dig$ = " "
DO
  GET #1, , dig$
  IF EOF(1) THEN EXIT DO
  IF INSTR("0123456789,", dig$) = 0 THEN EXIT DO
  IF INSTR("0123456789", dig$) > 0 THEN
    digNo = (digNo + 1) MOD 2
    ct(digNo) = ct(digNo) + VAL(dig$)
    IF ct(digNo) > 10 then ct(digNo) = ct(digNo) - 11
  END IF
  PRINT dig$;
LOOP
CLOSE
PRINT
IF digNo THEN
 diff = ct(1) - ct(0)
ELSE
 diff = ct(0) - ct(1)
END IF

IF diff < 0 THEN diff = diff + 11

PRINT "mod 11 = "; diff
PRINT "Therefore it is ";
IF diff > 0 THEN PRINT "not ";
PRINT "divisible by 11."

122
mod 11 =  1
Therefore it is not divisible by 11.
121
mod 11 =  0
Therefore it is divisible by 11.
1111
mod 11 =  0
Therefore it is divisible by 11.
1,111
mod 11 =  0
Therefore it is divisible by 11.
1,113
mod 11 =  2
Therefore it is not divisible by 11.
1,113,678,992,376
mod 11 =  5
Therefore it is not divisible by 11.
1,113,678,992,376,777,565,492,365,555,123
mod 11 =  4
Therefore it is not divisible by 11.
1,113,678,992,376,777,565,492,365,555,119
mod 11 =  0
Therefore it is divisible by 11.
11
mod 11 =  0
Therefore it is divisible by 11.
12
mod 11 =  1
Therefore it is not divisible by 11.
19
mod 11 =  8
Therefore it is not divisible by 11.
1
mod 11 =  1
Therefore it is not divisible by 11.
1589123477421159822231568945667123566842255778988874445612358974100230145054123
mod 11 =  3
Therefore it is not divisible by 11.

Verification of this last by extended precision UBASIC:
a=158912347742115982223156894566712356684225577898887444561235897410023014505412
3
OK
?a@11
 3
OK

 

Posted by Charlie on 2008-01-02 18:04:12