Solution to Lists of Large Integers

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 = x² - 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   

  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 10^K, so u*v < 10^(2*K) and (u² + v²) < 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 10^K * u² and 10^K * v² 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 u² + v², since it is (M - 10^(2*K)*u*v - u*v) / 10^K. Let c = u*v and let d = u² + v². 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).

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.

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.

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:

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.

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.

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:

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.

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 * 10¹³⁹ 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 x² + D*x - N = 0 and solve for x. So x = -D/2 + sqrt(D² + 4*N)/2. For each of the 64 possible values of D, we check if D² + 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.

The answer is EUROZONE.