__________________ | | | Is Multiple Of? | |__________________| To check if a number is multiple of 2 (if it's even) we can just check if it matches /[02468]$/. To check if a number is multiple of 3, we can do the following logic: echo 43271894789322 | sed ' s/[0369]//g :r; s/[147][258]// s/[258][147]// s/[147][147]/2/ s/[258][258]/1/ tr /./ s|.|not | s/$/multiple of 3/' we can apply this reductions because: -> (n+m)%3 = n%3 + m%3 -> (n*m)%3 = (n%3)*(m%3) % 3 then, since our base is 10 and 10%3=1, -> (n*10^k + m) % 3 = (n+m) % 3 we can delete 3s, 6s, 9s and 0s, and the number maintains the same congruence modulo 3. Then we can merge the remaining numbers until only one remains, adding two numbers congruent with 1 can be reduced to a 2, same logic can be used with two numbers congruent with 2: [(2+3n)+(2+3n)]%3 = (2+2)%3 = 4%3 = 1. For the 1+2 and 2+1 cases we can just remove them. Another shorter alternative can be obtained by translating the number to unary and then checking if the length is a multiple of 3: echo 43271894789322 | sed ' s/[0369]//g; s/[147]/x/g; s/[248]/xx/g s/\(xxx\)*// /./ s|..*|not | s/$/multiple of 3/'