如何高效生成有序序列2^I·3^Q的第N项？

Absolutely! Your current brute-force approach works for small values of N, but it doesn't scale well for larger N—you’d need far more than 15 iterations of i and q, and sorting a massive list introduces unnecessary overhead. There’s a direct, efficient way to compute the N-th term of this sequence (these numbers are called 3-smooth numbers, since their only prime factors are 2 and 3).

Core Idea: Binary Search + Counting Function #

The key insight is to use binary search to find the smallest number X such that there are exactly N+1 3-smooth numbers ≤ X (since the sequence starts at A[0] = 1). To make this work, we need a helper function that counts how many 3-smooth numbers are ≤ a given X.

Step 1: The Counting Function #

For a given X, we can count valid pairs (i, q) by iterating over possible values of q (exponents for 3) and calculating the maximum valid i (exponent for 2) such that 2^i ≤ X / 3^q. For each valid q, the number of valid i values is max_i + 1 (since i starts at 0).

Step 2: Binary Search #

We perform binary search over possible values of X:

• Start with a lower bound low = 1 (the first term) and an upper bound high = 2^N (a safe upper limit, since the worst case is all terms are powers of 2).
• For each midpoint mid, use the counting function to check if there are enough 3-smooth numbers ≤ mid. Adjust the bounds until low equals high—this will be the N-th term.

Python Implementation #

Here’s a working example of this approach:

import math

def count_3smooth(X):
    """Count how many 3-smooth numbers are ≤ X"""
    if X < 1:
        return 0
    count = 0
    q = 0
    while True:
        pow3 = 3 ** q
        if pow3 > X:
            break
        # Calculate max i where 2^i ≤ X / 3^q
        max_i = math.floor(math.log2(X / pow3))
        count += max_i + 1  # i ranges from 0 to max_i
        q += 1
    return count

def f(N):
    """Return the N-th term of the 3-smooth sequence (A[0] = 1)"""
    if N == 0:
        return 1
    low = 1
    high = 2 ** N  # Initial upper bound (can be tightened for speed)
    
    while low < high:
        mid = (low + high) // 2
        cnt = count_3smooth(mid)
        if cnt > N:
            # Too many numbers ≤ mid, target is smaller
            high = mid
        else:
            # Not enough numbers ≤ mid, target is larger
            low = mid + 1
    return low

Testing the Function #

Let’s verify with the sample sequence you provided:

• f(0) = 1 ✔️
• f(1) = 2 ✔️
• f(2) = 3 ✔️
• f(3) = 4 ✔️
• f(4) = 6 ✔️
• f(5) = 8 ✔️
• f(6) = 9 ✔️
• f(7) = 12 ✔️

Why This Is Better Than Your Current Approach #

• Scalability: This method works for any large N (e.g., f(1000) returns the 1000th term in milliseconds, whereas your brute-force approach would require generating thousands of numbers and sorting them).
• Efficiency: Binary search runs in O(log X) steps, and each counting step runs in O(log₃ X) time—far faster than generating and sorting a huge list.

Optional Optimization #

To speed up the counting function, you can precompute the maximum q value using logarithms instead of looping until 3^q > X:

def count_3smooth_optimized(X):
    if X < 1:
        return 0
    log3 = math.log(3)
    max_q = math.floor(math.log(X) / log3)
    count = 0
    log2 = math.log(2)
    for q in range(max_q + 1):
        pow3 = 3 ** q
        remaining = X / pow3
        max_i = math.floor(math.log(remaining) / log2)
        count += max_i + 1
    return count

内容的提问来源于stack exchange，提问作者Tunç Demircan