# An algorithm on divisibility

Posted 2 months ago
433 Views
|
4 Replies
|
3 Total Likes
|
 I put on your consideration this algorithm to know if an odd number S is divisible by another number (called "primo" here) : DivisibleQ[S_, primo_ ] (* S is odd and primo>5 *) := Module[{factor = ModularInverse[primo - 10, primo] , numero = S}, While[numero > primo, numero = FromDigits[Most[IntegerDigits[numero]]] - factor * Last[IntegerDigits[numero]]]; If [numero < 0, While[numero < 0, numero = numero + primo], While[numero > 0, numero = numero - primo]]; If[numero == 0, True, False]] Very simple, fast, general and economic. I hope you like it. Free to use naming the source; I named it EGP algorithm. I post it here because I want to share it with all the users of Mathematica. All suggestions are welcome.
4 Replies
Sort By:
Posted 2 months ago
 Interesting. I will make a few observations and offer a recoding.(1) Working in base 10 is computationally inefficient. If the digit length is n, then the algorithmic complexity of IntegerDigits/FromDigits becomes n log(n) whereas is is just n in base power-of-2 (because the underlying storage is base 2).(2) Another advantage to working in a power-of-2 base is that now the prime 5 is not disallowed. Also there is no restriction to primes, the only restriction is that the putative divisor not be even.(3) It is not necessary to convert to/from a digit string in the main loop. One can let the hex (or base 10) digits become negative. The issue we want to avoid from these conversions is that each iteration then has more work to do.Here is my recoding using hex. divisibleQ2[s_, primo_] := Module[{factor = ModularInverse[-16, primo], numero = s, digits, plen, diff}, digits = IntegerDigits[numero, 16]; plen = Length[IntegerDigits[primo, 16] + 1]; While[ Length[digits] > plen + 1, diff = IntegerDigits[factor*Last[digits], 16, Length[digits] - 1]; digits = Most[digits] - Sign[Last[digits]]*diff; ]; numero = FromDigits[digits, 16]; If[numero < 0, While[numero < 0, numero = numero + primo], While[numero > 0, numero = numero - primo]]; If[numero == 0, True, False]] I have not thoroughly tested it but I believe it works correctly. Or at least could be made to.The down side: it is still algorithmically O(n^2) because it needs O(n) iterations and each operates on lists of length O(n). So it does not beat "schoolkid" (used to be "schoolboy") division by more than a constant factor. Still, it's interesting.
Posted 2 months ago
 What are the advantages of using this algorithm rather than the built-in Divisible?