Re: Finding minimum in arithmetic series modulo N

On 2008-04-11, 3130@xxxxxxxx <3130@xxxxxxxx> wrote:
When considering the sequence of floor(N/D) iterations, the
resulting sequence is decreasing, I think, if D < N, and increasing
if D > N. (There is a trivial result if D = N.)

If D > N then the sequence is identical to one with D' = D mod N.


I do wonder if there's a more efficient approach.

I doubt it. This approach has the same complexity as the Euclidean
algorithm.


- Tim
.

Relevant Pages

  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... Shakespeare play as any other sequence. ... isn't the same thing as compression with use of a formula like Pi or ... S has a complexity of one bit when CS is taken as reference computer. ...
    (talk.origins)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: Of Mice and Straw Men
    ... examples of template-based evolution where improved binding to another ... pre-established sequence result in increased selectability. ... these examples end up beyond very low levels of functional complexity. ... requirements that go beyond a few hundred fairly specified residues. ...
    (talk.origins)