How to solve the LCM in 50 bytes of Python

Question

I've recently stumbled upon a Russian site called acmp.ru, in which one of the tasks, HOK, asks us to find the LCM of two positive integers. The full statement, translated to English is as follows:

The only line of the input contains two natural numbers A and B separated by a space, not exceeding 46340.
In the only line of the output, you need to output one integer - the LCM of the numbers A and B.

On the Python leaderboard, the top solution is just 50 bytes, followed by a stream of 52s.

Note that the scoring method for this site is not standard, and uses the following formula:

max(code length without spaces, tabs and newlines, full code length divided by 4)

With this in mind, I have come up with two solutions that give a score of 52. One of them simply uses math.lcm, while the other one calculates it more directly:

from math import*
print(lcm(*map(int,input().split())))

a,b=map(int,input().split())
v=a
while v%b:v+=a
print(v)

Now I'm stumped. How can I save 2 bytes off my solution? (the Python version is 3.9.5).

Answer 1

My solution to 50 bytes:

v=1
for x in input().split()*6**6:v+=-v%int(x)
print(v)

Explanation

The solution itself is relatively simple, but finding it was significantly more difficult.

First, note that the LCM of a and b is the smallest number v such that v%a==0 and v%b==0.

The main logic for this algorithm is in v+=-v%int(x). In a nutshell, it sets v to the first multiple of x greater than or equal to v. This means that if v%x==0, v doesn't change.

In a for loop, we repeat this process cyclically with both numbers. Whenever v is not divisible by x, v+=-v%x ensures that v becomes the immediate next divisor of x. This means that, at some point in the loop, v will equal the LCM. When it does, v will stop changing, since both numbers will be divisible by v.

To better illustrate the algorithm, here is an example on the input 36 27:

                v=1
(36): v+=-v%36; v=36
(27): v+=-v%27; v=54
(36): v+=-v%36; v=72
(27): v+=-v%27; v=81
(36): v+=-v%36; v=108
(27): v+=-v%27; v=108
(36): v+=-v%36; v=108
...

It remains to determine how many iterations are required. In the worst case, A and B are coprime, for which the LCM is A*B. For this, we would need exactly min(A,B) iterations. The statement tells us that both numbers are guaranteed to be at most 46340. We could simply use this number, but 6**6 is one shorter, and only does 316 extra operations.