2^P*3^Q

gistfile1.py

import math


def generate_numbers(N):
    """Generate first N elements of the sequence S. Complexity is NlogN.
    
    We have 3 bounds to consider:
    1) Numbers generated when P == Q
    2) Numbers generated when P > Q, the bound is given by grounding the Q
    3) Numbers generated when P < Q, the bound is given by grounding the P
    
    - For (1) we just include in solution.
    - For (2) and (3) cases we generate numbers in its neighbourhood (and on the bound itself)
    since they are most likely to give smallest numbers we are searching for.
    
    - Now when we cover all those 3 cases, only thing left to check is 
    the spread between bound (2) and (3), which is done by checking 
    the combination space given by sqrt(N) which can be done in O(N).
    
    So by analyzing those cases we end up having 2 x { O(NlogN) + O(N) } + C
    """
    results = []
    amortization = math.ceil(N ** (1/3))+1  # We introduce this amortization so the boundaries themselves also get included.
    
    # O(N) for cases where P == Q
    for i in range(N):
        results.append((2**i) * (3**i))

    # O(N) + amortization 
    for i in range(ceil(log(N))+amortization): 
        for j0 in range(math.ceil(math.sqrt(i)) + amortization):
            value = (2**i) * (3**j0)  # for cases where P > Q
            if value not in results:
                results.append(value)
                
            value2 = (2**j0) * (3**i)  # for cases where P < Q
            if value2 not in results:
                results.append(value2)

    # O(N) => fill in missing numbers missing betwen boundary P > Q and P < Q given P, Q < sqrt(N)
    for i in range(math.ceil(math.sqrt(N)) + amortization):
        for j0 in range(math.ceil(math.sqrt(N)) + amortization):
            value = (2 ** i) * (3 ** j0)
            if value not in results:
                results.append(value)
            
            value0 = (2 ** j0) * (3 ** j0)
            if value0 not in results:
                results.append(value0)
                
    # O(NlogN) + cutting of the tail => This last step is important 
    # cause we don't have a guarantee that we squeezed out all the numbers after N, 
    # so the density of numbers in the tail is incomplete and we don't care about it.
    return sorted(results)[:N]

You can test the solution with this:

# Ground truth
S = []
for P in range(200):
    for Q in range(200):
        S.append(2**P * 3**Q)
S2 = sorted(S)

# Submitted
from math import log
S = []
for P in range(24):
    for Q in range(int((24 - P ) * log(2)/log(3))+1):
        S.append(2**P * 3**Q)
S = sorted(S)
# same
for i in range(200):
    assert(S2[i]==S[i])

I disagree that

    for i in range(N): 
        for j0 in range(math.ceil(math.sqrt(i))):

is O(NlogN). The integral from 0 to x of xˆ1/2 is 2/3 xˆ{3/2} which will lead to 0(n sqrt(n) ) .

Here is a linear time solution using math.

from math import sqrt, log, ceil
a = sqrt(400 * log(2)/log(3))
Qmax = ceil(a) 
Pmax = ceil(a * log(3) / log(2))

S = []
for P in range(Pmax):
    for Q in range(Qmax - ceil(P * log(2)/log(3)) + 1):
        S.append(2**P * 3**Q)
S = sorted(S)

This computes only 225 numbers for the 200 that we need.

I disagree that

    for i in range(N): 
        for j0 in range(math.ceil(math.sqrt(i))):

is O(NlogN). The integral from 0 to x of xˆ1/2 is 2/3 xˆ{3/2} which will lead to 0(n sqrt(n) ) .

You're right. It's not the same. The way I looked at is not strictly exact due to the different case analysis. Associated with big O notation are several related notations, using the symbols o, Ω, ω, and Θ, to describe other kinds of bounds on asymptotic growth rates.

With that said in asymptotic analysis we say that log2(n) == O(sqrt(n)). The way this gets interpreted (and it's my understanding), that sqrt(n) is the considered the upper bound of log2(N). Because of that fact (and the fact that we usually have to consider all different cases of asymptotic growth rates) we don't usually calculate exact, but only consider where on average the line will be close to.

When we talk about complexity analysis there is a general rule which says: "any operation that halves the length of the input has an O(log(n)) complexity". Obviously, this can't be true if we are considering specific cases excatly, but when we generalize (try to classify different problem classes) it applies. There is more general rule to this which says: "for all reduction of lengths of the input by (B-1)/Bth complexity is O(logB(n))"

Here is a linear time solution using math.

from math import sqrt, log, ceil
a = sqrt(400 * log(2)/log(3))
Qmax = ceil(a) 
Pmax = ceil(a * log(3) / log(2))

S = []
for P in range(Pmax):
    for Q in range(Qmax - ceil(P * log(2)/log(3)) + 1):
        S.append(2**P * 3**Q)
S = sorted(S)

This computes only 225 numbers for the 200 that we need.

Ah, perfect. Did you submit this linear one or N^2 one? Cool solution, btw!

Thanks for pointing out the exact difference between N*sqrt(N) and NlogN. I've looked into that part again and it turns out I could do better. In the fixed solution it should run in O(N) since sqrt(N)*log(N) + C = O(N).

But the entire solution is still O(NlogN) due to the sorting.

I think we both have the same problem at this point and the question still remains about how to run this in linear time.

Can we generate numbers as ordered sequence in O(N).

This should work:

def gen_nums(N):
    S = [1, 2, 3]
    if N <= len(S):
        return S[:N]
    
    idx2, idx3 = 1, 2
    for i in range(3, N):
        idx2_num = S[idx2] * 2
        idx3_num = S[idx3] * 3
        if idx2_num <= idx3_num:
            idx2 += 1
        if idx2_num >= idx3_num:
            idx3 += 1

        S.append(min(idx2_num, idx3_num))
    
    return S