Module dsalgo::number_of_gcd_pairs_in_range_table_with_multiples_fast_mobius

Functions

number_of_gcd_pairs

\forall 1 <= g < hi, f(g) = \sum_{lo <= a, b < hi, gcd(a, b) = g}{1} \zeta{f(g)} := \sum_{g|x}\sum_{lo <= a, b < hi, gcd(a, b) = x}{1} (easy) f(g) = mobius_transform(\zeta{f(g)})