Public Access

# Solution to Lists of Large Integers

by Michael Korn

## Initial Observations

The first step is to factor as many of the numbers as possible. Naturally, smaller numbers will be easier to factor than larger ones. There are a number of websites that will do this; some are very good, others are not so good. Depending on what websites and tools they use, solvers may be able to factor most or all of the numbers in the "Factoring practice" section, but I do not believe they will be able to factor N or any of the numbers in the "Extra practice" section (with one possible exception, noted later). At the very least, they should be able to find the following factorizations.

19534199367679 = 2222321 * 8789999
214956291449113 = 12591707 * 17071259
189227 = 17 * 11131
901406955906697 = 10578521 * 85211057
8786083664737 = 1112333 * 7898789
1747473647 = 22123 * 78989
460220396751503 = 21452747 * 21452749
141404439546196699 = 112111 * 1261289610709
2498570204489999 = 49985699 * 49985701
994897763 = 31541 * 31543
109874163126125579 = 111232321 * 987789899

Solvers should observe that each of the given numbers is a product of two primes, and each factorization has some interesting property. There are four interesting properties that each factorization may have, which we will arbitrarily label (a) through (d).

(a) The factors differ by 2 (i.e., they are "twin primes").
(b) One of the factors has all but one of its digits equal to 1 (while the other factor has no apparent structure).
(c) One of the factors only uses the digits 1, 2, and 3, while the other factor only uses the digits 7, 8, and 9.
(d) The factors use the same digits as each other; the first half of one factor is the last half of the other factor, and vice versa.

At this point, solvers may conjecture that the larger numbers in the puzzle, including the ones in the "Extra practice" section, will have factorizations with one of these properties. It turns out that for each of the properties (a)-(d), twelve of the numbers in the "Factoring practice" section and one of the numbers in the "Extra practice" section have a factorization with that property. (The number N at the start of the puzzle does not have a factorization with any of these properties.)

## Writing programs to factor numbers with given properties.

For each property, it is possible to write a program to quickly factor any number that has a factorization with that property. Needless to say, one will have to do this in a programming language which supports doing exact computations on very large integers. The details of these programs will differ from language to language, but the following paragraphs describe the mathematical algorithms involved.

For property (a), the factors differ by 2. So if the number to be factored is M, then we can write M = (x-1)*(x+1) for some x. Equivalently, M = x2 - 1, so x = sqrt(M+1). So to factor a number with this property, we need to check if M+1 is a square, and if so, take its square root. (Incidentally, the general-purpose factoring method known as Fermat's Method works effectively if the factors of M are very close to being equal, and would find this factorization immediately. However, Fermat's method is not very powerful in general when dealing with large numbers, and so most modern optimized factoring programs wouldn't bother trying to apply Fermat's method. However, it is conceivable that a general purpose factoring program might give Fermat's method a try before moving on to more powerful algorithms. I think this is the only case in which a general-purpose factoring program would be able to factor one of the numbers in the "Extra practice" section.)

For property (b), one of the factors has all but one of its digits equal to 1. In this case, it is reasonably quick to enumerate all numbers of this form which are less than the number to be factored and test if the given number is divisible by any of them. If M has k digits, then one should consider factors whose length j is k or less; for a j-digit factor, there are j positions which could be the non-1, and 9 possible values for that digit. While one could check if each of these potential factors is prime, it is probably quicker to just try dividing M by each of the numbers. In the case of the largest number in the "Extra practice" section, there are about 300,000 potential factors to try, but this should not take more than a few seconds.

For property (c), one of the factors only uses the digits 1, 2, and 3, while the other factor only uses the digits 7, 8, and 9. In this case, one can build up the factors starting with their rightmost digits. For instance, suppose the final three digits of the original number M are 937. If x and y are the factors, then naively, x can end in 1, 2, or 3 and y can end in 7, 8, or 9, however, since their product M is 7 mod 10, the only possibilities are (1,7) and (3,9). Now look at the bottom two digits. Modulo 100, the possibilities are (11,77), (21,77), (31,77), (11,87), (21,87), (31,87), (11,97), (21,97), (31,97), (13,79), (23,79), (33,79), (13,89), (23,89), (33,89), (13,99), (23,99), and (33,99). By design, all of these lead to a product which is 7 mod 10, but the only ones which lead to a product which is 37 mod 100 are (21,97) and (33,89). Then working mod 1000, each of these will lead to nine possibilities, and one can rule out those whose product is not 937 mod 1000. And so on. There may be a handful of possibilities at the end; the final step is to see if their product is the given number.

For property (d), the factors have the same digits, but with their first and second halves swapped. Let K denote the number of digits in each "half". Then each factor will have 2*K digits, and their product will therefore have either 4*K - 1 or 4*K digits. So we can determine K by looking at the number of digits in the given number M. Letting u and v denote the value of each "half", the factors are

`  x  =   10K * u  +  v   `
and
`  y  =   10K * v  +  u.`

So we have

```  M  =   (10K * u  +  v) * (10K * v  +  u)
M  =   10(2*K) * u*v   +   10K * (u2 + v2)   +   u*v```

Both u and v are less than 10K, so u*v < 10(2*K) and (u2 + v2) < 2*10(2*K). From this we can see that the bottom K digits of M will equal the bottom K digits of u*v, since the first two terms above each end with at least K 0's. Also, the top digits of M will equal the top digits of u*v. This is true because the sum of the second and third terms has at most 3*K+1 digits, while M has about 4*K digits. Here's an example to make this clear.

```  u = 84397
v = 61653
x = 8439761653
y = 6165384397
M = 52034374809805128241
K = 5

1010 * u*v    =   52033282410000000000
105 * u2      =        712285360900000
105 * v2      =        380109240900000
u*v           =             5203328241
--------------------
M             =   52034374809805128241```

So we can almost just read off the value of u*v from the high and low digits of M. The only complication is that there may be carries from the addition of 10K * u2 and 10K * v2 which overflow into the high digits. But this carry can be no larger than 2. So there are three possibilities for u*v. We'll have to try them each in turn.

In each case, we can then compute u2 + v2, since it is (M - 10(2*K)*u*v - u*v) / 10K. Let c = u*v and let d = u2 + v2. Then d+2*c and d-2*c should both be perfect squares. Assuming they are, then u+v = sqrt(d+2*c) and |u-v| = sqrt(d-2*c), and so u = 1/2 * (sqrt(d+2*c) + sqrt(d-2*c)) and v = 1/2 * (sqrt(d+2*c) - sqrt(d-2*c)) or vice versa.

## Reading and applying the messages from the "Extra practice" numbers.

Once solvers have written the program for a particular property, they should try it against all the numbers in the puzzle to see what numbers factor in that way. Writing these programs is (likely) the only way to factor the numbers in the "Extra practice" section. These programs will also help get any remaining numbers from the "Factoring practice" section that they weren't able to get with general-purpose factoring algorithms.

Each of the numbers in the "Extra practice" section factors in a way matching one of the properties (a)-(d). Solvers won't know ahead of time which number has which property; they'll have to try each program against each number. In each case, the factorization produces a message in some way.

## Group (a): Twin primes.

Property (a) applies to the second number in the "Extra practice" section. Its factorization is:

53735505445758898384038022841430842526695016035215069425183418246952027784446685057194827746723798138041190616673025150514812640845073458956680497851907441298986714469900118428921656029214999261571466081111832354937985056601915083253489123 = 231809200520080519050914020119052008091820251909241920151610211920020506151805200805060918192014151412052020051899004181 * 231809200520080519050914020119052008091820251909241920151610211920020506151805200805060918192014151412052020051899004183.

Reading either of these factors by taking two digits at a time and converting 01-26 to letters spells:

WRITE THESE IN BASE THIRTY-SIX, STOP JUST BEFORE THE FIRST NON-LETTER.

(This is followed by the two-digit value 99 and some other irrelevant digits; this was necessary in order to make the factors prime.)

The "THESE" in the message refers to the factors of the numbers in the "Factoring practice" section which have property (a). Below are the numbers in the "Factoring practice" section which have property (a), along with their factorizations, and the base-36 representation of the smaller factor (the base-36 representation of the larger factor only differs slightly at the end).

NumberFactorizationBase-36
39791368329452832625515474137530708563051258383199477738932074404605371 * 199477738932074404605373wheaccessible4b
37119987701796725959709467373786385071129631926654813447305769341 * 1926654813447305769343baltirioles03h
30822170568554721991788551629431755624406544711 * 1755624406544713habepus01z
152950709362533623104774590950573521294911857528993910891322480511259045229 * 3910891322480511259045231housesofparent65
51807149552451394115371694183032276118396578951 * 2276118396578953metector5z
46022039675150321452747 * 21452749crt1n
297875567953154250095616466186358148710354577977972177958847 * 54577977972177958849binomiarem3zz
249857020448999949985699 * 49985701trd7n
99489776331541 * 31543oc5
888636227580718682979205390656559298949663651294512394267503816570781359320681 * 94267503816570781359320683buenosagentina06h
10014329987386541999573139069136253196764673599100071624286740454603559 * 100071624286740454603561gandabetting1lz
17450582025965056503921631066757650600572777023132100651118626423309031 * 132100651118626423309033lieutenvernor8n

Stopping just before the first non-letter produces some almost-readable sequences of letters. Solvers must recognize these as words or phrases with some letters missing (always a consecutive sequence of letters from within the original word or phrase). The shortest examples will be ambiguous at first, but the larger ones should be uniquely identifiable. In each case, the missing letters can be anagrammed to form a word from the NATO phonetic alphabet. This further constraint should allow the solvers to identify the shortest ones as well. In this way, each item on the list yields a letter.

wheaccessiblewhe[elchair] accessibleelchaircharlieC
baltiriolesbalti[more o]riolesmoreoromeoR
habepushabe[as cor]pusascoroscarO
housesofparenthouses of par[liam]entliamlimaL
crtcr[oche]tocheechoE
binomiarembinomia[l theo]remltheohotelH
trdtr[inida]dinidaindiaI
ococ[tagon]tagontangoT
buenosagentinabuenos a[ires, ar]gentinairesarsierraS
gandabetting[aidin]g and abettingaidinindiaI
lieutenvernorlieuten[ant go]vernorantgotangoT

## Group (b): Almost-all-1's.

Property (b) applies to the fourth number in the "Extra practice" section. Its factorization is:

2575657783400810095955063818861033325050679161681409136325985009571994361108682930688653936574971570369702482911305533513778159182277112740897510755386867643432164435453427621656508883131776463866577206466109953307610978877332010220955094288332010995386556661 = 1111111111111411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 * 2318092005060103201518191209110520080919151405091420051814011825200805141805010420231501190104011908011404151405011901041520990051

Reading the factor that doesn't have all the 1's by taking two digits at a time and converting 01-26 to letters spells:

WRITE FACTORS LIKE THIS ONE IN TERNARY, THEN READ TWO AS A DASH AND ONE AS A DOT.

(This is followed by the two-digit value 99 and some other irrelevant digits; this was necessary in order to make this factor prime.)

The values to write in ternary are the random-looking factors of the numbers in the "Factoring practice" section which have property (b). Below are the numbers in the "Factoring practice" section which have property (b), along with their factorizations, and the ternary (base-3) representation of the appropriate factor.

NumberFactorizationTernary
18922711131 * 17122
7872395702895375122222222222930737835482805982434982651932684711111111111111111111111111111211111111111111111 * 70851561326058376111201110012210121010111001102110102102
107119266525763993596762689007524763934551114772536894774908875207145803761111111111111111111111111111111 * 175286072496704716794702582012313568776671110112022022010121002220121102122022012210110212101110011110222011102021210110202122
534731504468270628365596728711111131 * 48125749257053186427711101202100201201110012101011021021101010121
5585163959983591435370647966641111362443433458733125866875915903481444711111111111111111111111111111111111611111 * 502664756398523229183358316997711101120121011120110111202220121001110100120111022202102101202201
141404439546196699112111 * 126128961070911110120121102220221001021
994419421951706078233054463257402075674157879698609818346591111111111111111111711111 * 8949774797565354699264612673608806910222021001221012102220211011202121010211002111022202102110112101101211022
1729423628530534793342588705128962247243111111111111111112111111 * 155648126567748132210121010102120001211010202010121
2837596931175995828283571567182842260777777777777777777494018084685716567327706131111111111211111111111111111111111111111111111111111111 * 25538372378285508940506448311101120122101012102111022201220121101220110210210010121
38920281861605663773111511111111 * 349026043220022202100201111
835200223940332230652186999657770251111111111102759559855475593122560622840911111711111111111111111111111111111111111111111 * 751639613007196618969543944319122201201221012021010111010012210012101011210102121020112012101
531501002366194367517154876071111151 * 47833372994866977352057121012011021002111022201220212102220121102220121

As the phrase indicates, we must now take these ternary strings, take the 1's as dots and 2's as dashes and read in Morse code. The 0's indicate breaks between letters. (In some cases there are multiple 0's in a row; this has no relevance and was only necessary to make the factors prime.) Here are the phrases that come from decoding the Morse code:

 122 W 11201110012210121010111001102110102102 U.S. PRESIDENT 1110112022022010121002220121102122022012210110212101110011110222011102021210110202122 SUMMER OLYMPICS HOST CITY 11101202100201201110012101011021021101010121 SANTA'S REINDEER 11101120121011120110111202220121001110100120111022202102101202201 SURVIVOR SEASON NAME 11110120121102220221001021 HALOGEN 10222021001221012102220211011202121010211002111022202102110112101101211022 EON-PRODUCED BOND FILM 2210121010102120001211010202010121 GREEK LETTER 11101120122101012102111022201220121101220110210210010121 SUPER BOWL WINNER 220022202100201111 MONTH 122201201221012021010111010012210012101011210102121020112012101 JAPANESE PREFECTURE 121012011021002111022201220212102220121102220121 RAINBOW COLOR

Each of these describes an ordered list of items. Solvers must now notice that the other factor (the one with all the 1's) has the same number of digits as there are items in this list. The location of the non-1 digit in this factor indicates which item to take from the list, and the digit itself indicates which letter to take from that item. In this way, each item on the list yields a letter.

Decoded Morse codeOther factornumber of digitslocation of non-1 digitvalue of non-1 digitlist itemextracted letter
W (i.e., "the 5 W's")11131543WH(E)RE (or WH(E)N)E
U.S. PRESIDENT111111111111111111111111111121111111111111111146292H(A)RDING (or W(A)RREN HARDING)A
SUMMER OLYMPICS HOST CITY611111111111111111111111111111113216ATHEN(S)S
SANTA'S REINDEER11111131873DO(N)NER (or DU(N)DER)N
SURVIVOR SEASON NAME1111111111111111111111111111111111161111141366GHOST (I)SLANDI
HALOGEN112111632B(R)OMINER
EON-PRODUCED BOND FILM111111111111111111171111125207DIE ANO(T)HER DAYT
GREEK LETTER11111111111111111211111124182S(I)GMAI
SUPER BOWL WINNER111111111121111111111111111111111111111111111111111111155112R(A)IDERS (or O(A)KLAND RAIDERS)A
MONTH1115111111111245APRI(L)L
JAPANESE PREFECTURE111117111111111111111111111111111111111111111114767YAMAGA(T)AT
RAINBOW COLOR1111151765INDI(G)OG

## Group (c): 123/789.

Property (c) applies to the first number in the "Extra practice" section. Its factorization is:

8641975308641975308641983198319753086419753165308741995309649864197532864397531653094508671975308641975418488294100246913680446917903822570343599335825702569027580269237023569324691358257028013609124880246913593717171593759122247 = 1111111111111111111111112111211111111111111121111111111111112111111111111111111211112111111111111111111122232323223 * 7777777777777777777777777877787777777777777778777777777777777877777777777777777787777877777777777777777778988999889

In this case, the message is spelled by counting the length of the runs of 1's and 7's in the factors, and converting values 1-26 to letters. The factor with the digits 1, 2, and 3 spells out X-COORDS, and the factor with the digits 7, 8, and 9 spells out Y-COORDS. (The sequences of 2's and 3's or 8's and 9's at the end of the factor are not relevant, but were necessary to make the factors prime.) As before, this message applies to the numbers from the "Factoring practice" section that have property (c). In each case, the two factors have the same number of digits. If the factors each have k digits, then the factorization can be viewed as a sequence of k points in the plane, with the 1/2/3 factor providing the sequence of x-coordinates and the 7/8/9 factor providing the sequence of y-coordinates. In each case, tracing a path from point to point in this order forms the shape of a letter. Here are the numbers having property (c) and the letters that are traced out.

NumberFactorizationLetter Traced
195341993676792222321 * 8789999T
232123210952962087923244097495181257784475902354664491205388235723212321121111121123211212121111 * 99999999888787888999998888888787F
232198718518557633357824913678792322222222222121 * 9998987878789999T
87860836647371112333 * 7898789N
174747364722123 * 78989Y
107666313378130058771211111123 * 8889878999F
219901987383176588448793057122212322232123 * 98999998777777I
255106686975346511516700563658379671013233332323332111123 * 7889899999899987887R
107761940739308276072269174795987546825983923848968572616704902577121232321232123212121232323232123 * 888887877787778777777788878888899S
109874163126125579111232321 * 987789899D
88617383097001613725711233333211 * 78887878987A
175533103133918314274197989924242265723905712222222121232221212123 * 7898989999999877777777I

## Group (d): Swapped halves.

Property (d) applies to the third number in the "Extra practice" section. Its factorization is:

401833279169841952944755364355519074282215394320089433871085108080700877204461640309371860634695761359356236526845461433287618955686322816939429649784867491999050815812786166671859895000235580003337396071913709307120309146066422068125305900967083807629207 = 20011105040906060518051403050205202305051420080508011222051999072008051421190520080520140914051608151405110525160104031504059901 * 20080514211905200805201409140516081514051105251601040315040599012001110504090606051805140305020520230505142008050801122205199907

Each factor produces a message by taking two digits at a time and converting 01-26 to letters. Each message ends with the digits "99" just less than halfway through the factor. The messages are:

TAKE DIFFERENCE BETWEEN THE HALVES.
THEN USE THE T-NINE PHONE KEYPAD CODE.

This message applies to the numbers from the "Factoring practice" section that have property (d). In this case, the "halves" are the first and last half of either of the factors. Subtracting these from each other yields a number composed of digits in the range 2-9. Here are these numbers, their factorizations, and the differences:

NumberFactorizationDifference
21495629144911312591707 * 17071259448
90140695590669710578521 * 852110577464
33004960546528492994777500573793393600030777852959533611485089493955322224223308337 * 22224223308337148508949395537373328368784
81283924278344381272501101487800923 * 800923101487699436
309172834443486211391948018924630374729128927871443825494670919345380599705823276812885604149759 * 681288560414975945380599705823272274825633567432
104073802093834462759665574659243806744246178238296011726888928308472252333597208021146207099260448677 * 462070992604486772252333597208021123683763288368466
113905474623772968098614040835380460040312414384439175281721 * 917528172112414384437933843278
361768214370975900337206276272880117442346026389497860017227 * 786001722746026389493257378278
593417948863821469945406431595646799525390904050049164636609513793256189782390569983 * 897823905699836609513793256123687252637422
395381823812368982714449407001971449 * 971449407001564448
69276210691959588650799386848096609474317385293745787742019320124095129489759632875112612339427 * 28751126123394272409512948975963465599663363464
31524268415523389441572697469871353458471520331157243809367200480187693 * 20048018769315724380936743236378326

The T9 phone keypad code is the code which maps ABC=2, DEF=3, GHI=4, JKL=5, MNO=6, PQRS=7, TUV=8, and WXYZ=9. Solvers have to convert these digits into letters to make meaningful words or phrases. The shortest ones might be ambiguous at first, but the longer ones only have one reasonable interpretation. Each of these is a word or phrase that might lead to a single letter when interpreted as though it were part of a cryptic clue. Here are the phrases and the letters they lead to.

 448 HIT H 7464 RING O 7373328368784 PERFECT FOURTH F 699436 OXYGEN O 2274825633567432 CAPITAL OF FLORIDA F 23683763288368466 CENTER OF ATTENTION N 7933843278 SWEET HEART E 3257378278 FALSE START F 23687252637422 CENTRAL AMERICA R 564448 KNIGHT N 465599663363464 HOLLYWOOD ENDING D 43236378326 HEAD OF STEAM S

## The clue phrase and the final program.

In this way, each of the 48 numbers in the "Factoring practice" section leads to a single letter. Reading these letters in the order the numbers appear in the original puzzle spells:

THE FACTORS OF N ONLY DIFFER IN THEIR FIRST AND LAST DIGITS.

The final step is to factor N. This will require writing another program. One way to do this is as follows. Let x and y be the factors of N, with x < y. Consider the value of D = y - x. Since x and y only differ in their first and last digits, there are only a few possibilities for D. The difference in the first digit will contribute u * 10139 to the difference, where u is in the set {1,2,3,4,5,6,7,8} (recall that x and y are known to be 140 digits long). The difference in the last digit will contribute v to the difference, where v is in the set {-8, -6, -4, -2, 2, 4, 6, 8} (note that x and y must both be odd, although we don't know which one will have a larger units digit). So there are 64 possibilities for D. If we know D, then we can solve for x, since y = (x + D) and N = x * y, so we have x * (x + D) = N, which we can write as x2 + D*x - N = 0 and solve for x. So x = -D/2 + sqrt(D2 + 4*N)/2. For each of the 64 possible values of D, we check if D2 + 4*N is a square. If so, then we know the factors of N.

The factors are:

• 12305121204151405200805011419230518251521180512151511091407061518091905211815261514052008051805192015062008091914211302051809190609121205189
• 82305121204151405200805011419230518251521180512151511091407061518091905211815261514052008051805192015062008091914211302051809190609121205183

Ignoring the first and last digits, and reading the rest two digits at a time spells the following:

WELL DONE! THE ANSWER YOU'RE LOOKING FOR IS EUROZONE. THE REST OF THIS NUMBER IS FILLER.