Smallest "diamond-number" above some power of ten?

Question

Let us call a positive integer $N$ a "diamond-number" if it has the form $p^2q$ with distinct primes $p,q$ with the same number of decimal digits. An example is $N=10^{19}+93815391$. Its factorization can be seen here

Can we efficiently find the smallest diamond number above some given power of $10$ ? For $10^{37}$ , the smallest I found so far is $10^{37}+434907760840094559$ (factorization here) , but I am pretty sure that this is not optimal (The above example should be optimal for $10^{19}$). My approach was to determine the smallest positive integer above $10^{37}$ divisible by $p^2$ for various prime numbers $p$ , but this soon gets totally infeasible.

Is there any better approach ?

Answer 1

The smallest "diamond-number" (if my calculations are correct), related to $10^{37}$, is $$ 10^{37} + 1483238923930317 = 1102689419521^2 \times 8224198521037. $$

The smallest "diamond-numbers" (again, if no mistakes) related to numbers of the form $10^{3k+1}$, are:

10^n  + delta             =              p ^2 * q          log_2(delta)
---------------------------------------------------------------------
10^19 + 93815391          =        2150209 ^2 * 2162911        26.4833
10^22 + 782939691         =       15634603 ^2 * 40909699       29.5443
10^25 + 44473963077       =      164317583 ^2 * 370366693      35.3722
10^28 + 192056856217      =     1417504619 ^2 * 4976809697     37.4827
10^31 + 1903633770933     =    13116605573 ^2 * 58124212477    40.7919        
10^34 + 4064603456403     =   245902790183 ^2 * 165376229827   41.8863
10^37 + 1483238923930317  =  1102689419521 ^2 * 8224198521037  50.3977
10^40 + 11233721191891321 = 10229370048307 ^2 * 95565738654929 53.3187 (???)

The used algorithm: starting from a pair of odd numbers $(p_0,q_0)$, for which $p_0^2q_0 \in (10^{37}, 10^{37} + \delta)$ (where $\delta$ is reasonably "small": say, initially $10^{17}$),
iterate over $p$ forward with step $2$, $q$ backward with step $-2$
until $p^2q$ will appear inside $(10^{37}, 10^{37} + \delta)$ again, after that check if $p$ and $q$ are primes (as time consuming operation); and so on.

The pseudocode (without division operations in main cases):

base = 10^37
p = p_0, q = q_0

pp = p*p, ppq = pp*q, diff = ppq - base

while (p < p_max && q > q_min) {
    if (diff in [0, diff_min]) {
        if (isPrime(p) && isPrime(q)) {
            diff_min = diff
            output something
        }
        p += 2, q -= 2, pp = p*p, ppq = pp*q
        diff = ppq - base
    }

    while (diff > diff_min) {
        q -= 2, ppq -= 2pp, 
        diff = ppq - base
    }

    while (diff < 0) {
        p += 2, pp = p*p, ppq = pp*q
        diff = ppq - base
    }
}

Possible modification: for the given bound $\delta$ construct the set $A$ of all the pairs $(p,q)$ of odd numbers, such that $10^{37} < p^2q < 10^{37} + \delta$. After that, apply primality filtering for the set above.