sequences-everywhere

Let's consider some integer X. We will call the following sequence S a sequence generated by X:
for i = 1: S[i] = X 
for i > 1: S[i] equals to the minimal positive integer such that S[i] is not a divisor of S[i - 1]. If there is no such integer than S[i - 1] is the last element of S.

For example S = (10, 3, 2) is a sequence generated by 10.

Can you find the total sum of lengths of the sequnces generated by all the integers from A  to B inclusive.

Input
The only line contains two integers: A and B. (A ≤ B)

Output 
Output the only integer - answer to the question. It's guaranteed that this value can be stored in 64-bit integer.

Constraints 
1 < A ≤ B ≤ 10^17

SAMPLE INPUT
2 6

SAMPLE OUTPUT
12

Source: hackerearth | Difficulty: HARD


Solutions:
def gcd(a,b):
	if b==0:return a
	return gcd(b,a%b)
def lcm(a,b):return a*(b/gcd(a,b))

f=[1,1,1]
for i in range(3,100):
	for j in range(1,i+1):
		if i%j!=0: 
			f.append(1+f[j])
			break

def solve(x):
	if x==0:return 0
	global f
	m=1
	ans=1   
	for v in range(2,min(x+1,50)):
		#v<m*d<=x
		inc=x/m-v/m
		m=lcm(m,v)
		inc-=x/m-v/m
		ans+=inc*(1+f[v])
	if 2<=x:ans+=1
	return ans

a,b=[int(x) for x in input().split()]
print(solve(b)-solve(a-1))


from fractions import gcd

def seq(x):
	for i in range(1, x):
		if x % i != 0:
			return [x] + seq(i)
	return [x]

def lcm(a, b):
	return a * b / gcd(a, b)

A, B = list(map(int, input().split()))

S = [1] * 42
for i in range(1, 42):
	for j in range(1, i):
		if i % j != 0:
			S[i] = S[j] + 1
			break

def calc(N):
	if N == 1:
		return 0

	x = [1]
	for i in range(1, 41):
		x.append(lcm(x[-1], i))

	ways = [0] * 41
	ans = 0
	
	for i in range(40, 0, -1):
		ways[i] = N / x[i]
		for j in range(i + 1, 41):
			ways[i] -= ways[j]
		ans += ways[i] * S[i + 1]

	return ans

C = min(B + 1, max(100, A))

ans = 0
for i in range(A, C):
	ans += len(seq(i))

A = C

ans += calc(B) - calc(A - 1) + B - A + 1

print(ans)