Let $N$ be some number. Let $R$ and $S$ be semiprimes (ie, each is a product of two prime numbers) such that $R \le N \le S$.

For quite a few numbers $N$ we can find $R, S$ such that $S-R$ is small; eg, for $N=50$, we have $7\cdot7 = 49 < 50 < 51 = 3\cdot17$, giving $S-R=2$.

For $N=10240579048185725616$ and certain other large numbers too numerous to mention we can quickly (via prime quadruplets) find semiprimes $R, S$ such that $S-R=12$. But what about products of three primes? How small can the interval be made?

The challenge in this puzzle is to find $U_k, V_k$, each the product of three primes, such that $U_k \le N_k \le V_k$, given that $N_k$ is the RSA number with k decimal digits, while minimizing $\Delta_k = V_k-U_k$. Find best solutions for $k\in\{100, 160, 320, 480\}$.

For example, RSA-100

$$= 15226050279225333605356183781326374297180681149613806886579\\08494580122963258952897654000350692006139 = 37975227936943673922808872755445627854565536638199 × 40094690950920881030683735292761468389214899724061$$

If we let

$$U = 6246644847868435165458917\cdot1150435884651666110524532974697443\cdot211874175165550696134616092679587435515153$$


$$V = 6246644847868435165458967 \cdot 1150435884651666110524532974697441\cdot211874175165550696134616092679587435515309$$

then we obtain $U \le N \le V$ and

$$\Delta_{100} = 1218738270442411472694284522980510595717360280370\\4967527962531133881349172780$$

which is about 75 orders of magnitude larger than achievable with a little more work. But what is the best achievable (or, minimal) value for $\Delta_{100}$?

  • 3
    $\begingroup$ When a puzzle involves this much math, shouldn't it be in Mathematics rather then puzzling? $\endgroup$ – Tim Couwelier Sep 8 '14 at 8:29
  • $\begingroup$ @TimCouwelier, solving the puzzle requires a little insight, which once achieved may make it seem trivial. It might be laughed at in Mathematics. $\endgroup$ – James Waldby - jwpat7 Sep 8 '14 at 12:01
  • $\begingroup$ This question is not a puzzle, but rather an exercise in wasting CPU time. $\endgroup$ – aaaaaaaaaaaa Sep 11 '14 at 19:59
  • 1
    $\begingroup$ @jwpat7 Most people don't know all the number theory you're asking about; I'm pretty sure it would be treated as well as a specialist topic in Math.SE. (The place you're thinking of where it would be laughed at is Math Overflow.) $\endgroup$ – Joe Z. Sep 12 '14 at 2:00

The insight I mentioned in a comment is realizing that most numbers no larger than those mentioned in the question have relatively few factors. More concretely, the Erdős–Kac theorem says (roughly) that if $\omega(n)$ is the number of distinct prime factors of n, the distribution of $\frac{\omega(n) - \log\log n}{(\log\log n)^{1/2}}$
is standard normal. Thus, numbers in the neighborhood of RSA-320 average about $(\log\log n)^{1/2} \approx 6.6$ distinct prime factors, with standard deviation about 2.6, making it not at all unlikely there will be a number near RSA-320 having exactly three (not necessarily distinct) prime factors. The following code uses linear search to look for tri-prime near-neighbors of RSA-100, 160, 320, and 480. It runs for about 3 seconds on my i3-2120@3.30GHz system, to produce the output shown after the program.

#!/usr/bin/env python
# Close triprimes - jw 8 Sep 2014
from gmpy import is_prime, mpz
# Note, will run ok without mpz, but is twice as fast with it.
# Ref http://puzzling.stackexchange.com/questions/2227/products-of-three-primes-that-bound-rsa-numbers

# Return a tuple of nfax factors if k appears to
# factor into that many primes; else return None
def testfaxtuple(k, nfax):
    fax = []
    for p in smallprimes:
        while k % p == 0:       # Factors don't have to be distinct
            fax.append(p)       #   Add factor to list
            k /= p              #   Divide factor out of k
            if is_prime(k):     # If k is prime we are done with k
                if len(fax) == nfax:
                    return fax  # Right number of prime factors
                    return None # There are too few prime factors
            if len(fax) == nfax:
                return fax if k==1 else None
            if k==1:
                return None
    return None                 # No small prime divides k

# Search up or down from k to find a number with nfax prime factors
def searchfaxtuple(k, d, nfax):
    while k:
        t = testfaxtuple(k, nfax)
        if t:
            return k, t     # Return the number and its factor tuple
        k += d

primeLim = 162401 # <--- With checks to 13, we are ok below that Carmichael#
smallprimes = [2,3,5,7,11,13]+[x for x in range(17,primeLim,2) if 1==pow(2,x-1,x)==pow(3,x-1,x)==pow(5,x-1,x)==pow(7,x-1,x)==pow(11,x-1,x)==pow(13,x-1,x)]

n100 = mpz(1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350692006139)
n160 = mpz(2152741102718889701896015201312825429257773588845675980170497676778133145218859135673011059773491059602497907111585214302079314665202840140619946994927570407753)
n320 = mpz(21368106964100717960120874145003772958637679383727933523150686203631965523578837094085435000951700943373838321997220564166302488321590128061531285010636857163897899811712284013921068534616772684717323224436400485097837112174432182703436548357540610175031371364893034379963672249152120447044722997996160892591129924218437)
n480 = mpz(302657075295090869739730250315591803589112283576939858395529632634305976144571441696598170401251852159138533455982172343712313383247732107268535247763784105186549246199888070331088462855743520880671299302895546822695492968577380706795842802200829411198422297326020823369315258921162990168697393348736236081296604185145690639952829781767901497605213955485328141965346769742597479306858645849268328985687423881853632604706175564461719396117318298679820785491875674946700413680932103)

for kfax in [3]:
    for n, digi in ((n100,100),(n160,160),(n320,320),(n480,480)):
        hik, hit = searchfaxtuple(n, +1, kfax)
        lok, lot = searchfaxtuple(n, -1, kfax)
        print 'n+{}: {}'.format(hik-n, hit)
        print 'n-{}: {}'.format(n-lok, lot)
        print '{}_Delta_{} = {}'.format(kfax, digi, hik-lok)

In each section of the output shown below, n represents an RSA number; eg, in the first line, n+118 refers to a triprime equal to RSA-100 plus 118, and in the next line, n-93 is a triprime equal to RSA-100 minus 93, so $\Delta_{100} = 211$.

n+118: [13, 2953, mpz(39662534265610809360379754047582313415771916824126199918151254124361743292582586096381785164813L)]
n-93: [2, 75211, mpz(10122222998780320435412495367251049911037402208196810896397524927072655351337921963901559284493L)]
3_Delta_100 = 211
n+61: [2, 14519, mpz(74135308999204136025071120645802928206411377809961980169794671698399791487666476192334563667383809477322746301797135281427071928686646468097663303083117653L)]
n-70: [3, 1319, mpz(544033637280487667903971493887496949521802777064866307852033782354847901243077871031845099765855713824235003060799902527692523291686338170487729844560922519L)]
3_Delta_160 = 131
n+214: [11, 11, mpz(176595925323146429422486563181849363294526275898577963001245340525884012591560637141201942156625627631188746462786946811291756101831323372409349462897825265817338014972828793503479905244766716402622505987077689959486257125408530435565591308740005042768854308800768879173253489662414218570617545437984800765215949786931L)]
n-224: [13, 52967, mpz(31032539802141998370713948372794923048803506659048861371086912175551926415110187757087410014292935577266307064917373174540174489372323446763705246097551098091406550394530533545445667236373260977760206608231250640961988106055050507069621794059785570660151780084977488712077145638070904012868277923403920427364977503L)]
3_Delta_320 = 438
n+200: [3, 106109, mpz(950774126276096183294945921381446762571545246168059443262838630195698059368421282821118442360377386018586338752233308339262184430625526918133036932977045947049886582664643810707506629521666465240684262732647707617310165234420519487180926538436354475738540234808925486588681635303203907204533053585577836882503225253106681619695563938239299517807832686153949058563511011452366526580713058739184326135349574123004434448558166804769056335520764178595660391647191959672602115689L)]
n-169: [2, 3, mpz(50442845882515144956621708385931967264852047262823309732588272105717662690761906949433028400208642026523088909330362057285385563874622017878089207960630684197758207699981345055181410475957253480111883217149257803782582161429563451132640467033471568533070382887670137228219209820193831694782898891456039346882767364190948439992138296961316916267535659247554690327557794957099579884476440974878054830947903980308938767451029260743619899352886383113303464248645945824450068946821989L)]
3_Delta_480 = 369

Suppose the last seven lines of the program are replaced with the following eight:

print '#f   D100  D160  D320  D480'
for kfax in range(2,9):
    ro = []
    for n, digi in ((n100,100),(n160,160),(n320,320),(n480,480)):
        hik, hit = searchfaxtuple(n, +1, kfax)
        lok, lot = searchfaxtuple(n, -1, kfax)
    print '{}:  {:5} {:5} {:5} {:5}'.format(kfax, *ro)

With that code, the program computes and prints $\Delta$ values for 2-factor, 3-factor, ... and 8-factor cases for four RSA numbers. This took about 80 seconds of computation.

#f   D100  D160  D320  D480
2:     56   132   626   420
3:    211   131   438   369
4:     54    11    98  1434
5:    106   155   303   302
6:    341    75  1286   319
7:     76   836   284  3244
8:    100   417   620  2628

Eg, this shows there is a pair of quad-factor numbers that bound RSA-160 and differ by only 11.

  • $\begingroup$ Note, most of the numbers in the last table are likely to not be optimal because many 3rd, 4th, 5th... factors will exceed the largest test divisor in smallprimes. Eg, with primeLim=9999999 instead of 999999, line 4 of the table reads 4: 39 6 98 1113 and line 7 reads 7: 76 677 41 2404. Also, test division methods get proportionally slower as #f increases, suggesting use of better factoring methods. $\endgroup$ – James Waldby - jwpat7 Sep 11 '14 at 17:55
  • $\begingroup$ A big -1 from here, the "trick" is to use a bunch of formulas other people have created, on top of plenty CPU time. And you can't even produce optimal solutions. $\endgroup$ – aaaaaaaaaaaa Sep 11 '14 at 19:52
  • $\begingroup$ @eBusiness, the Erdős–Kac theorem was mentioned to show the accuracy of the intuition there will be lots of 3-factor numbers near an RSA number, and that linear search is feasible without using a lot of CPU time. Granted, the program shown doesn't check or guarantee optimality. It would take perhaps 4 more lines of code to check for optimality (which has a reasonable chance of occurring, even without any special measures) but would require a full-blown factoring method to guarantee it $\endgroup$ – James Waldby - jwpat7 Sep 11 '14 at 20:07
  • $\begingroup$ For 100 and 160 digit numbers a full factoring could take an awful lot of time on a desktop computer. For 320 and 480 digits, well, the RSA numbers themselves haven't been factored yet, not even by people with big clusters. If this is to remotely resemble a puzzle you should at least cherry pick numbers so that an optimal solution can be proven without excessive CPU time consumption. $\endgroup$ – aaaaaaaaaaaa Sep 11 '14 at 20:15

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