Odd Divisors#1520

Odd Divisors (Editorial)

If $n$ is odd, then $f (n) = n$ f(n) = n.

If $n$ is even, then $f (n) = f (n /2)$ f(n) = f(n / 2).

Let

g (n) = f (1) + f (2) + ... + f (n)

g(n) = f(1) + f(2) + ... + f(n)

Consider the partition of the set of positive integers from $1$ to $n$ into two subsets:

ODD — the set of odd numbers,
EVEN — the set of even numbers.

Among the positive integers from $1$ to $n$ , there are exactly

$k = ⌊ (n + 1) /2 ⌋$ k = \left\lfloor (n + 1) / 2 \right\rfloor odd numbers;
$l = ⌊ n /2 ⌋$ l = \left\lfloor n / 2 \right\rfloor even numbers

Then:

f (1) + f (3) + f (5) + ... + f (2 k - 1) = 1 + 3 + 5 + \dots + (2 k - 1) = \frac{1 + 2 k - 1}{2} \cdot k = k^{2}

f(1) + f(3) + f(5) + ... + f(2k - 1) = \\ 1 + 3 + 5 + … + (2k - 1) = \\ {1 +2k - 1\over 2} \cdot k = k^2

At the same time:

f (2) + f (4) + f (6) + ... + f (2 l) = f (1) + f (2) + f (3) + ... + f (l) = g (l) = g (⌊ n /2 ⌋)

f(2) + f(4) + f(6) + ... + f(2l) = \\ f(1) + f(2) + f(3) + ... + f(l) = \\ g(l) = g(\left\lfloor n / 2 \right\rfloor)

To terminate the recursion, let $g (0) = 0$ g(0) = 0. Thus:

g (n) = {k^{2} + g (⌊ n /2 ⌋), k = (⌊ n + 1) /2 ⌋ 0, n = 0

g(n) = \begin{cases} k^2 + g(\left\lfloor n / 2 \right\rfloor), k = (\left\lfloor n + 1) / 2 \right\rfloor \\ 0, n = 0 \end{cases}

Example

Consider the first test case where $n = 7$ n = 7.

Among the positive integers from $1$ to $7$ there are exactly:

$k = ⌊ (7 + 1) /2 ⌋ = 4$ k = \left\lfloor (7 + 1) / 2 \right\rfloor = 4 odd numbers;
$l = ⌊ 7/2 ⌋ = 3$ l = \left\lfloor 7 / 2 \right\rfloor = 3 even numbers.

g (7) = ⌊ \frac{7 + 1}{2} ⌋^{2} + g (⌊ \frac{7}{2} ⌋) = 16 + g (3) = 16 + ⌊ \frac{3 + 1}{2} ⌋^{2} + g (⌊ \frac{3}{2} ⌋) = 16 + 4 + g (1) = 16 + 4 + 1 = 21

g(7) = \left\lfloor 7 + 1 \over 2 \right\rfloor^2 + g\left(\left\lfloor 7 \over 2 \right\rfloor\right) = 16 + g(3) = \\ 16 + \left\lfloor 3 + 1 \over 2 \right\rfloor^2 + g\left(\left\lfloor 3 \over 2 \right\rfloor\right) = 16 + 4 + g(1) = 16 + 4 + 1 = 21

Algorithm implementation

Implement the function g.

long long g(long long n)
{
  long long k = (n + 1) / 2;
  if (n == 0) return 0;
  return k * k + g(n / 2);
}

The main part of the program. For each test case read the input value of $n$ and print $g (n)$ .

while(scanf("%lld",&n) == 1)
  printf("%lld\n",g(n));

Java implementation

import java.util.*;

public class Main
{
  static long g(long n)
  {
    long k = (n + 1) / 2;
    if (n == 0) return 0;
    return k * k + g(n / 2);
  }
	
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    while(con.hasNext())
    {
      long n = con.nextLong();
      System.out.println(g(n));
    }
  }
}

Java

Python implementation

Implement the function g.

def g(n):
  if n == 0:
    return 0
  k = (n + 1) // 2
  return k * k + g(n // 2)

The main part of the program. For each test case read the input value of $n$ and print $g (n)$ .

for line in sys.stdin:
  n = int(line)
  print(g(n))