0

Reposted from Stack Overflow - I think this is a more appropriate place to ask the question.

I have an algorithm that for an integer x and a starting integer i such that 1 < i < x the next value of i is computed by i = floor(x / i) + (x mod i). This continues until we reach an i that we've already seen.

In JavaScript (though this question is language agnostic):

function f(x, i) {
    var map = {};
    while(!map[i]) {
        map[i] = true;
        i = Math.floor(x / i) + (x % i); // ~~(x / i) is a faster way of flooring
    }
    return i;
}

I can prove that we will eventually reach an i we've already seen, but I'm wondering:

  1. Is there is a more efficient way of computing the next i?
  2. (More importantly) Is there is a way to compute the nth i without running through the loop n times?

Just to clarify - I know there are faster ways than using JS hash maps for that check, and that flooring can be replaced by integer division in other languages. I have made both of those optimizations, but I left them out to try to make the code easier to understand.

  • 4
    Please don't post the same question on multiple stackexchange sites, because it will split the answers and discussion. Pick which site would be more appropriate, and when you realize you've choosen poorly, either delete the question before you repost it or flag it for moderator attention and request a migration. – Philipp Apr 27 '16 at 7:45
  • @Philipp thanks! I flagged my question on SO for a moderator to close it. – winhowes Apr 27 '16 at 8:19
  • If x = i^2 then the next i is the same. If x = ki for some integer k then the next to numbers are k, i. – gnasher729 Apr 27 '16 at 15:58
  • Too late to do anything about the two questions now. – Robert Harvey Apr 28 '16 at 23:35
3

Your proof that you will always reach a previously used 'i' appears to imply that your mapping function is topologically mixing. This in turn suggests that your function is probably chaotic. If it is chaotic, then by definition there is no faster way of producing the result than iterating your mapping function.

Looking at it less rigorously, the modulus function has a property of taking small differences and expanding them (relative to the size of the result) while integer division takes large differences and reduces them. These two properties are commonly found in chaotic functions (e.g. the Lorentz attractor), so are suggestive that your function may be chaotic.

  • I looked up topological mixing, but I'm not sure if this function represents that behavior or not (apologies if I'm not grasping the definition, but I want to learn!) So the behavior of this function is that there is a path of one number going to another and eventually a cycle at the end (eg 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8 > 9 > 7 > 8 > 9 > 7...). Is that topological mixing? Additionally I've noticed patterns for how the numbers in the cycles relate to each other, and there seems to be a relationship between the numbers in the cycles and the factors of x – winhowes Apr 27 '16 at 8:36

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.