Arithmetic derivative P86263


Statement
 

pdf   zip

thehtml

Given a natural number n, its arithmetic derivative d(n) is defined as follows:

  • d(0) = d(1) = 0.
  • If n is prime, then d(n) = 1.
  • Let n = x · y, with 1 < x, y < n. Then d(n) = x · d(y) + y · d(x).

For instance, d(4) = 2d(2) + 2d(2) = 2 + 2 = 4, and d(6) = 3d(2) + 2d(3) = 3 + 2 = 5. It ‍can be proven that this definition is consistent. For example, d(12) = 4d(3) + 3d(4) = 4 + 12 = 16, and also d(12) = 6d(2) + 2d(6) = 6 + 10 = 16.

We say that f is a fixed point of d(n) if d(f) = f. For instance, 0 and 4 are fixed points. Given ℓ and r, can you compute the number of fixed points of d(n) in [ℓ..r]?

Input

Input consists of several cases, each one with ℓ and r, with 0 ≤ ℓ ≤ r ≤ 1018.

Output

For each case, print the number of fixed points of d(n) in [ℓ..r].

Public test cases
  • Input

    0 4
    1 20
    4 4
    5 23
    900000000000000000 1000000000000000000
    

    Output

    2
    1
    1
    0
    0
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++