If I were to write 40 in binary {101000}, I could tell just from looking at it that 40 is divisible by 2, 3 times.

If I were to write 40 in ternary (base 3) {1111}, I can tell from looking at it that 40 is not divisible by 3.

  • Is there a way to know how many times a number can be divided by a prime, without changing base and without performing an algorithm.

I suspect if there is a way to do it, logarithms will be key.

I know that I can determine the length of a number in a different base. I.e. $\frac{log(40)}{log(2)} = 5.322..$ so 40 in binary is 6 digits long. Not sure if this will be useful though.

  • I'm also wondering if testing divisibility by 2 and 5 may have some rule with the digits because of base 10 being base 2×5.

Thanks in advance

  • $\begingroup$ "Is there a way to know..." - yes, ask somebody else what the answer is. If you (very reasonably) exclude this sort of thing, then I'm not sure what you mean by "without performing an algorithm", since a "way to know" will essentially be an algorithm. Perhaps you could clarify the question. $\endgroup$ – David Aug 10 '16 at 1:14
  • $\begingroup$ A deterministic formula, like the one for determining the length of a number in a different base. Essentially, I'm after a formula which will tell me how many 0's a number will have if written in a different base. $\endgroup$ – Ben Crossley Aug 10 '16 at 1:35
  • $\begingroup$ How does a "deterministic formula" differ from "an algorithm"? $\endgroup$ – Milo Brandt Aug 10 '16 at 1:43
  • $\begingroup$ Sorry. That was me being tired and using the wrong term. I meant closed form. Not deterministic. Although, deterministic (i.e. not probabilistic) would also be desirable. $\endgroup$ – Ben Crossley Aug 10 '16 at 2:47
  • $\begingroup$ I think that your question is not well-posed, since after all, writing $40$ in binary or ternary involves an algorithm. $\endgroup$ – Lubin Aug 10 '16 at 3:25

Logarithms only tell you the maximal power under the limit. For example $p^x \leq n$ leads to $x \leq \log_p(n)$ but it doesn't tell you whether $p$ actually divides $n$ or how many times it does (unless the log calculation turns out to be an integer). It only provides an upper bound on the multiplicity.

Other than that you won't be able to really tell "without an algorithm." You usually just divide $n$ by $p$ over and over again while the modulus is $0$.

  • $\begingroup$ So, are you certain there is way to do it? Or just that logarithms aren't the way forward? Thank you for your input. $\endgroup$ – Ben Crossley Aug 10 '16 at 2:48
  • $\begingroup$ An area of maths I've never gotten into (I'm only undergrad) is the p-adic orders. Is that an area of maths that could possibly reveal an answer? $\endgroup$ – Ben Crossley Aug 10 '16 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.