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

Home > Algorithms
Seventeen Divisibility Surmise (Posted on 2023-03-04) Difficulty: 3 of 5
Devise an algorithm to find all possible values of a positive integer N ≤ 20220 that simultaneously satisfies the following conditions:
  1. N is divisible by 17
  2. The sum of digits of N is divisible by 17.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Two algorithms | Comment 1 of 2
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.

  Posted by Brian Smith on 2023-03-04 10:09:50
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information