We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Mathematics
  3. Number Theory
  4. A Weird Function
  5. Discussions

A Weird Function

  • cafelatte
     + 0 comments

    It seems to be OK to post code so let me share mine to show that you don't need lots of code to do it in Python 

    ...
from math import isqrt
from itertools import accumulate

NMAX = 10**12
TMAX = math.isqrt(2*NMAX) + 2

TOT = None
ACC = None

def totient_init(n):
    global TOT
    TOT = list(range(n+1))
    for i in range(2,n+1,2): TOT[i] //= 2
    p = 3
    while p <= n:
        if TOT[p] == p:   # not touched yet, that is: prime
            for i in range(p,n+1,p): TOT[i] = TOT[i] * (p-1) // p
        p += 2

def solve(l,r):
    # prepare totient table etc
    global TOT,ACC
    if not TOT:
        totient_init(TMAX)
        # for even i we need phi(i/2) not phi(i), different for  i=4*k
        for i in range(4,TMAX+1,4): TOT[i] //= 2
        # multiply neighbours
        tot_it = iter(TOT)
        next(tot_it)
        ACC = [a*b for a,b in zip(TOT,tot_it)]
        ACC = list(accumulate(ACC))
    return ACC[tri_down(r)] - ACC[tri_up(l)-1]


def tri_up(n):   # idx of next triangular number at n or above
    i=isqrt(2*n)
    if i*(i+1)//2 < n: i+=1
    return i

def tri_down(n):  # idx of next triangular number at n or below
    i=isqrt(2*n)
    if i*(i+1)//2 > n: i-=1
    return i