Devise an algorithm to find all possible values of a positive integer N ≤ 20220 that simultaneously satisfies the following conditions:
- N is divisible by 17
- The sum of digits of N is divisible by 17.
I came up with two algorithms. Both of the algorithms, I just used old UBASIC. Its slow, but 20220 is still small enough that Ubasic is still good enough.
My first algorithm is the plain idea of step through all multiples of 17 and see if the sum of digits is also a multiple of 17:
10 L=20220
20 for N=0 to L step 17
30 X=N:S=0
40 while X>0
50 S=S+X@10:X=X\10
60 wend
70 if (S@17)=0 then print N;
80 next
90 print:end
This gets us the list of values:
0 476 629 782 935 1088 1394 1547 1853 2159 2465 2618 2771 2924 3077 3383 3536 3842 4148 4454 4607 4760 4913 5066 5219 5372 5525 5831 6137 6290 6443 6902 7055 7208 7361 7514 7820 8126 8432 9044 9350 9503 9979 10268 10574 10727 10880 11186 11339 11492 11645 11951 12257 12563 12716 13175 13328 13481 13634 13940 14093 14246 14552 14705 15164 15317 15470 15623 16082 16235 16541 17153 17306 17612 18071 18224 18530 19142 19601
This first algorithm spends a lot of time checking values that won't be solutions. In particular in any span of numbers XX00-XX99, we try 5-6 values but at most one of them could be a solution.
So then my second algorithm has the idea of stepping through possible 'heads' of a solution and then uses modular arithmetic to calculate the tens and units digit.
More specifically if we have number VWXTU then VWX is the head and we take that value, call it N, and its sum of digits, call that S.
Then we have a system of equations mod 17:
100N+10T+U=0 mod 17 and S+T+U=0 mod 17.
Solving this for T and U yields:
U=13N+14S mod 17 and T=4N+2S mod 17
Then one final check to see if T and U are less than 10 finishes the algorithm:
10 L=202
20 for N=0 to L
30 X=N:S=0
40 while X>0
50 S=S+X@10:X=X\10
60 wend
70 U=(13*N+14*S)@17:T=(4*N+2*S)@17
80 if U<10 and T<10 then print 100*N+10*T+U;
90 next
100 print:end
This gets us the same list of solutions as before but runs much faster.