Anti-Triangle

Computer Science Level pending

Chris wants a list of numbers up to \(N\) that is not divisible by any triangular numbers greater than 1. Here is his algorithm in Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def anti_tri(N):
    # L[i] = 1 implies i is not divisible by any triangular number > 1
    L = [0] + [1] * N

    T = 3   # triangular number
    i = 3
    while T <= N:
        for i in range(T,N,T):
            L[i] = 0
        T += i
        i += 1

    ans = []
    for i in range(N+1):
        if L[i] == 1:
            ans.append(i)

    return ans

What is the time complexity of the algorithm above?

Details and Assumptions

  • \(N\) : range of numbers
  • \(M\) : number of triangular numbers smaller than \(N\)
  • Triangular Numbers are numbers that can be expressed in the form \(n(n+1) / 2\). The first 5 triangular numbers are 1, 3, 6, 10 and 15.
×

Problem Loading...

Note Loading...

Set Loading...