All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Divisible by 11 (Posted on 2008-01-02)
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.)

 See The Solution Submitted by Chesca Ciprian Rating: 1.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 as a computer program | Comment 2 of 3 |

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

 Search: Search body:
Forums (0)