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 even-position 1's exactly balance the odd-position 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 1001-fold. Therefore the difference between the odd-position sum and the even-position 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 odd-position and even-position 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 2011-11-05 15:19:19