4 ms·

As you said, this is equivalent to factorisation in terms of complexity. The Wikipedia article[0] on the subject does a good job of summarising the details of t

by mrmr1993 9y ago

As you said, this is equivalent to factorisation in terms of complexity. The Wikipedia article[0] on the subject does a good job of summarising the details of this in the section "Other properties of repeatend lengths". For a simple answer, the lengths are bounded above by Euler's totient function [1] (the sum of factors) of the denominator. Any tighter bounds depend on the specific primes in the factorisation. Note that Euler's totient function is "always 'nearly n'" in magnitude (Hardy and Littlewood), so that representation will be very expensive for most fractions of large denominator. [0]: https://en.wikipedia.org/wiki/Repeating_decimal https://en.wikipedia.org/wiki/Repeating_decimal [1]: https://en.wikipedia.org/wiki/Euler%27s_totient_function https://en.wikipedia.org/wiki/Euler%27s_totient_function

danbruc 9y ago
That Wikipedia article on repeating decimals is probably where I started looking into it, but the article is somewhat weird. For many problems Wikipedia articles say we know this and that but those other things are still unknown, this article has a lot of information but does not talk about unknown things at all. The length of the repeating fractional part of 1 / n divides φ(n)...and then nothing. Is this all we know or is there more but just not in this article? I still remember that quite well because that was probably the first and only time that I was unable to find someone stating that we do not know any better, and not only the Wikipedia article but everywhere I looked there was no such statement to be found. I eventually gave up after a couple of evenings but it obviously kept stuck somewhere in my mind and that is why I wrote the initial comment.
- jcranmer 9y ago
  MathWorld is often a decent resource for finding this kind of information: <http://mathworld.wolfram.com/DecimalPeriod.html> http://mathworld.wolfram.com/DecimalPeriod.html>, but it's often difficult to arrive at those pages if you don't have any idea where to start.
  - yorwba 9y ago
    There's an extra > at the end of your link.
  - danbruc 9y ago
    I certainly also looked through MathWorld but I failed to make some - in hindsight - rather obvious connections or did not pay enough attention. I certainly knew what the discrete logarithm problem is and that it is hard but I did not realize until a few minutes ago that finding the multiplicative order is just that only with a different name. And now being aware of that the MathWorld article spells exactly this out in a way that it seems impossible to miss.
- yorwba 9y ago
  The repeating digits in the fractional part are essentially the output of a linear congruence random number generator. Finding the period is almost the same as determining the order of an element of the state space, but by chance you might get a shorter repetition that fits into the longer one. Finding the order of an element in a group is a hard problem on par with factoring http://mathworld.wolfram.com/GroupOrder.html http://mathworld.wolfram.com/GroupOrder.html I'm not sure about cases where the state space doesn't form a multiplicative group, but I doubt that it gets much easier.
thaumasiotes 9y ago
> As you said, this is equivalent to factorisation in terms of complexity. This can't be right. Factorisation is, legendarily, a hard problem, unsolved (in realistic time frames) for large input. But more than that, it's harder than division is. Finding the length of the nonrepeating and repeating parts of a rational number's decimal expansion can be done just by doing the division. That would appear to be evidence that it is not harder than division? Edit: from the wikipedia section you link: > If k = 2^a·5^b·n where n > 1 and n is not divisible by 2 or 5, then the length of the transient of 1/k is max(a,b) and the period [of the repetend, presumably] is r, where r is the smallest integer such that 10^r ≡ 1 (mod n) All integers (except those whose only prime factors are 2 and 5) satisfy this condition, so this would appear to be exactly the method desired? Repeatedly dividing by 5 is much, much easier than factoring is. Taking the discrete log of 1... could be equivalent to factoring.
- danbruc 9y ago
  That would appear to be evidence that it is not harder than division? From your edit I guess that you already realized this, but the hard part here is that for 1 / q you would have to perform up to q divisions of integers of size n = log₂(q) which of course takes time O(2ⁿ) even assuming the divisions are O(1).

danbruc 9y ago

That Wikipedia article on repeating decimals is probably where I started looking into it, but the article is somewhat weird. For many problems Wikipedia articles say we know this and that but those other things are still unknown, this article has a lot of information but does not talk about unknown things at all. The length of the repeating fractional part of 1 / n divides φ(n)...and then nothing. Is this all we know or is there more but just not in this article? I still remember that quite well because that was probably the first and only time that I was unable to find someone stating that we do not know any better, and not only the Wikipedia article but everywhere I looked there was no such statement to be found. I eventually gave up after a couple of evenings but it obviously kept stuck somewhere in my mind and that is why I wrote the initial comment.

jcranmer 9y ago
MathWorld is often a decent resource for finding this kind of information: <http://mathworld.wolfram.com/DecimalPeriod.html> http://mathworld.wolfram.com/DecimalPeriod.html>, but it's often difficult to arrive at those pages if you don't have any idea where to start.
- yorwba 9y ago
  There's an extra > at the end of your link.
- danbruc 9y ago
  I certainly also looked through MathWorld but I failed to make some - in hindsight - rather obvious connections or did not pay enough attention. I certainly knew what the discrete logarithm problem is and that it is hard but I did not realize until a few minutes ago that finding the multiplicative order is just that only with a different name. And now being aware of that the MathWorld article spells exactly this out in a way that it seems impossible to miss.
yorwba 9y ago
The repeating digits in the fractional part are essentially the output of a linear congruence random number generator. Finding the period is almost the same as determining the order of an element of the state space, but by chance you might get a shorter repetition that fits into the longer one. Finding the order of an element in a group is a hard problem on par with factoring http://mathworld.wolfram.com/GroupOrder.html http://mathworld.wolfram.com/GroupOrder.html I'm not sure about cases where the state space doesn't form a multiplicative group, but I doubt that it gets much easier.

thaumasiotes 9y ago

> As you said, this is equivalent to factorisation in terms of complexity. This can't be right. Factorisation is, legendarily, a hard problem, unsolved (in realistic time frames) for large input. But more than that, it's harder than division is. Finding the length of the nonrepeating and repeating parts of a rational number's decimal expansion can be done just by doing the division. That would appear to be evidence that it is not harder than division? Edit: from the wikipedia section you link: > If k = 2^a·5^b·n where n > 1 and n is not divisible by 2 or 5, then the length of the transient of 1/k is max(a,b) and the period [of the repetend, presumably] is r, where r is the smallest integer such that 10^r ≡ 1 (mod n) All integers (except those whose only prime factors are 2 and 5) satisfy this condition, so this would appear to be exactly the method desired? Repeatedly dividing by 5 is much, much easier than factoring is. Taking the discrete log of 1... could be equivalent to factoring.

danbruc 9y ago
That would appear to be evidence that it is not harder than division? From your edit I guess that you already realized this, but the hard part here is that for 1 / q you would have to perform up to q divisions of integers of size n = log₂(q) which of course takes time O(2ⁿ) even assuming the divisions are O(1).