-2

I am trying to work out an equation for calculating how many times the code below (y and z are constants) will run before it starts to repeat itself.

while (true) {
    std::cout << (x * y) % z << std::endl;
    x++
}

For example, with a being 100 and z being 360, the code will run 18 times before the output becomes 0 again.

int y = 100;
for (int i = 0; i < 19; ++i) {
    std::cout << y*i % 360 << std::endl;
}
8176135
  • 3,755
  • 3
  • 19
  • 42

2 Answers2

1

This is called Least Common Multiple. For your example, the LCM of x=100 and y=3600 is 1800 / x = your 18.

std:lcm exists as of C++17.

If you can't use that, consult C++ algorithm to calculate least common multiple for multiple numbers for some implementations, though yours can be simpler than those since they support more than 2 inputs.

lotyrin
  • 192
  • 8
1

This is more of a math problem than a programming problem, but here goes:

You need to observe one key thing: (A * B) % C will be zero if A, B, or A * B is divisible by C without remainders. So one thing you need to find is the least common multiple.

Example: y = 5, z = 12. Your loop will yield 0 every 12 iterations. And on your example, 100 / 360 => 5 / 18. So you need x to be 18 since 5 and 18 are coprime, ie. A * B will need to be zero.

There are many algorithms to find the least common multiple of 2 numbers. I'll share one from here.

SenselessCoder
  • 1,139
  • 12
  • 27