# My algorithm is too slow

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.

• 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

• 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