[Note] Totient summatory function in sublinear time

Original post: https://math.stackexchange.com/questions/316376/how-to-calculate-these-totient-summation-sums-efficiently

Background:

• Totient summatory function: Wolfram

Python code snippet:

class TotientSummatoryFunction():
  """Totient summatory function class."""

  def __init__(self, bound, mod):
    """Initialize.

    Args:
      bound: An integer.
      mod: An integer.
    """
    self.mod = mod
    self.small_values = None
    self.small_value_bound = None
    self.big_values = {}
    self.InitSmallValues(bound)

  def InitSmallValues(self, bound):
    """Initialize small values for totient summatory function.

    Args:
      bound: An integer.
    """
    n = 3 * int(math.pow(bound, 2 / 3))
    assert(n**3 >= bound**2)
    print('InitSmallValues({n})'.format(n=n))

    phi = [i for i in range(n + 1)]
    for i in range(2, n + 1):
      if phi[i] != i:
        continue
      for j in range(i, n + 1, i):
        phi[j] = phi[j] // i * (i - 1)

    self.small_values = [0 for i in range(n + 1)]
    self.small_values[1] = phi[1] % self.mod
    for i in range(2, n + 1):
      self.small_values[i] = (self.small_values[i - 1] + phi[i]) % self.mod
    self.small_value_bound = n

  def Get(self, n):
    """Get totient summatory function value.

    Args:
      n: An integer.

    Returns:
      An integer.
    """
    if n <= self.small_value_bound:
      return self.small_values[n]

    if n not in self.big_values:
      result = n * (n + 1) // 2
      m = self.IntegerSqrt(n)
      for d in range(1, m + 1):
        result -= self.Get(d) * (n // d - n // (d + 1))
      for k in range(2, n // (m + 1) + 1):
        result -= self.Get(n // k)
      self.big_values[n] = result % self.mod
    return self.big_values[n]

  def IntegerSqrt(self, n):
    """
    Get the integer part of Sqrt[n].

    Args:
      n: An integer.

    Returns:
      An integer.
    """
    guess = (n >> n.bit_length() // 2) + 1
    result = (guess + n // guess) // 2
    while abs(result - guess) > 1:
      guess = result
      result = (guess + n // guess) // 2
    while result * result > n:
      result -= 1
    return result

[Note] Dynamic programming on ProjectEuler

Latest revised on 2019-10-21

General rule:

Time complexity = Number of states * Number of transitions of one state * Time complexity of transition function

Examples:

• #31: Coin sums
• #67: Maximum path sum II
• #612: Friend numbers
• #618: Numbers with a given prime factor sum
• #655: Divisible Palindromes
• #662: Fibonacci paths
• #679: Freefarea

[FWD] 景氣指標查詢系統

Link: https://index.ndc.gov.tw/n/zh_tw/leading#/

鈍化。趁往下的時候研究股票。

[Leetcode] 1170. Compare Strings by Frequency of the Smallest Character

1. Pre-calculated on words.

2. Counting sort and built-in quick-sort (need to know the average/worst time complexity of quick sort.)

3. Binary search of time complexity O(log(n)). Stick on single implementation.

• left-closed and right-open interval. Same as for loop.
• < in while loop.
• mid = lower + (upper - lower) / 2 to avoid overflow.
• return lower.

You can develop other various implementations based on this one.

---

Source code:

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] sorted = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            sorted[i] = calculate(words[i]);
        }
        Arrays.sort(sorted);

        int[] nums = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int target = calculate(queries[i]);
            int lower = 0;
            int upper = words.length;
            while (lower < upper) {
                int mid = lower + (upper - lower) / 2;
                if (sorted[mid] <= target) {
                    lower = mid + 1;
                } else {
                    upper = mid;
                }
            }
            nums[i] = words.length - lower;
        }
        return nums;
    }
    
    private int calculate(String word) {
        int[] counting = new int[26];
        for (char c : word.toCharArray()) {
            counting[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (counting[i] > 0) {
                return counting[i];
            }
        }
        return 0;
    }
}