2
$\begingroup$

I am given $A$ and $B$, where $A$ is less than or equal to $B$, and they are in the range of $[1, 100000000]$. I want to calculate the number of pronic numbers in that interval $[A, B]$. These numbers are numbers $n$ such that $k \times (k + 1) = n$ for some $k$. The following algorithm works, but I am having a lot of trouble understanding the intuition behind it. Can one explain to me why it works?

def pronic(num) :
 
    # Check upto sqrt N
    N = int(num ** (1/2));
 
    # If product of consecutive
    # numbers are less than equal to num
    if (N * (N + 1) <= num) :
        return N;
 
    # Return N - 1
    return N - 1;
 
# Function to count pronic
# numbers in the range [A, B]
def countPronic(A, B) :
     
    # Subtract the count of pronic numbers
    # which are <= (A - 1) from the count
    # f pronic numbers which are <= B
    return pronic(B) - pronic(A - 1);
$\endgroup$

1 Answer 1

0
$\begingroup$

First of all, denoting the number of pronic integers in $1,\ldots,m$ by $N_m$, the number of pronic integers in $A,\ldots,B$ is $N_B - N_{A-1}$: this counts the number of pronic integers in $1,\ldots,A-1,A,\ldots,B$, minus their number in $1,\ldots,A-1$.

Next, a formula for $N_m$. It is the unique integer $x$ such satisfying $x(x+1) \leq m < (x+1)(x+2)$: the pronic integers in $1,\ldots,m$ are $1\cdot(1+1),2\cdot(2+1),\ldots,x\cdot(x+1)$. Roughly speaking, $x \approx \sqrt{m}$, and this suggests checking whether $\lfloor \sqrt{m} \rfloor$ might work. The main observations are $$ m = \sqrt{m}^2 < (\lfloor \sqrt{m} \rfloor + 1)^2 < (\lfloor \sqrt{m} \rfloor + 1)(\lfloor \sqrt{m} \rfloor + 2) $$ and $$ m = \sqrt{m}^2 \geq \lfloor \sqrt{m} \rfloor^2 > \lfloor \sqrt{m} - 1 \rfloor \lfloor \sqrt{m} \rfloor. $$ If $\lfloor \sqrt{m} \rfloor (\lfloor \sqrt{m} \rfloor + 1) \leq m$ then $x = \lfloor \sqrt{m} \rfloor$ works, and otherwise $x = \lfloor \sqrt{m} \rfloor - 1$ does.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.