Determine the highest power of 11 (base ten) that evenly divides N (base ten), where:
N = 12....221 (the digit one followed by 2001 twos followed by one)
*** For an extra challenge, solve this puzzle without using a computer program.
10 for I=1 to 2002
20 N=N*10+1
30 next
40 N=N*11
50 print N:print
60 while N @ 11=0
70 N=N//11
80 inc Ct
90 wend
100 print Ct
Finds the highest power of 11 that divides N is 3.
Start of analytic solution:
As the formation of N in the above program makes use, N is 11 times a number that's a concatenation of 2002 1's. Thus, so far we have a single factor of 11.
The concatenation of 2002 1's itself is divisible by 11, as the evenposition 1's exactly balance the oddposition 1's in the 11's divisibility test. So we have a second factor of 11.
If the division of that concatenation of 2002 1's by 11 is carried out, the result is an alternation of 0's and 1's, as each 11 needs no borrows from beyond it. The repetition of "01" is 1001fold. Therefore the difference between the oddposition sum and the evenposition sum is 1001, which is divisible by 11, and this quotient is also divisible by 1, making N divisible by at least 11^3.
However, dividing the remaining quotient by 11 again is not that easy. The UBASIC system tells me that after having divided by 11 the three times, the following is the quotient, which is not divisible by 11, leaving 3 as the highest power. For an analytic solution, I don't see any other way that by using long division to get the below number and keeping track of the oddposition and evenposition sums:
9182736455463728191000918273645546372819100091827364554637281910009182736455463
72819100091827364554637281910009182736455463728191000918273645546372819100091827
36455463728191000918273645546372819100091827364554637281910009182736455463728191
00091827364554637281910009182736455463728191000918273645546372819100091827364554
63728191000918273645546372819100091827364554637281910009182736455463728191000918
27364554637281910009182736455463728191000918273645546372819100091827364554637281
91000918273645546372819100091827364554637281910009182736455463728191000918273645
54637281910009182736455463728191000918273645546372819100091827364554637281910009
18273645546372819100091827364554637281910009182736455463728191000918273645546372
81910009182736455463728191000918273645546372819100091827364554637281910009182736
45546372819100091827364554637281910009182736455463728191000918273645546372819100
09182736455463728191000918273645546372819100091827364554637281910009182736455463
72819100091827364554637281910009182736455463728191000918273645546372819100091827
36455463728191000918273645546372819100091827364554637281910009182736455463728191
00091827364554637281910009182736455463728191000918273645546372819100091827364554
63728191000918273645546372819100091827364554637281910009182736455463728191000918
27364554637281910009182736455463728191000918273645546372819100091827364554637281
91000918273645546372819100091827364554637281910009182736455463728191000918273645
54637281910009182736455463728191000918273645546372819100091827364554637281910009
18273645546372819100091827364554637281910009182736455463728191000918273645546372
81910009182736455463728191000918273645546372819100091827364554637281910009182736
45546372819100091827364554637281910009182736455463728191000918273645546372819100
09182736455463728191000918273645546372819100091827364554637281910009182736455463
72819100091827364554637281910009182736455463728191000918273645546372819100091827
36455463728191000918273645546372819100091827364554637281910009182736455463728191
There is a repetition that would cut down on the work involved.

Posted by Charlie
on 20111105 15:19:19 