More fun with factorization

Using the tables at the Cunningham Project, one can factor M1279-1, where M1279=2^1279-1 is the 15th Mersenne Prime.

? M1279=2^1279-1;
? isprime(M1279)
%50 = 1
? print(factor((M1279-1)/(a*b*c*d*e*f*z*y*x*w*v)))
[2, 1; 3, 3; 7, 1; 19, 1; 73, 1; 1279, 1; 5113, 1; 17467, 1; 66457, 1; 102241, 1; 228479, 1; 48544121, 1; 56409643, 1; 212885833, 1]

? [a,b,c,d,e,f,v,w,x,y,z]
%51 = [ 28435302301212461494420074814087, 1329628131546931497103420134367, 84462210560148142953097, 4205268574191396793, 2849881972114740679, 581211581673454706767349073071710126567, 4856686864845032704799031665030860909072721381346530375665783654750574941128789505171, 13952598148481, 203525545766301306933226271929, 69779014917427, 8970948423964301024591994817 ]

The large factor (v=48566...171) factors v-1 = 32670537017659 * 30745017857595820376423803727 *372195264810848171907297121582928687 * smaller_factors

No such luck with the next Mersenne prime M2203, where we get stuck with C217 factor of 2^1101+1.

With M2281, we again get pretty lucky to obtain a complete factorization of M2281-1:

2 * 3 * 3 * 5 * 5 * 7 * 11 * 13 * 17 * 31 * 41 * 61 * 151 * 191 * 229 * 241 * 331 * 457 * 571 * 761 * 1217 * 1321 * 2281 * 4561 * 32377 * 54721 * 61681 * 90289 * 131101 * 148961 * 160969 * 174763 * 185821 * 247381 * 524287 * 525313 * 1101811 * 1212847 * 160465489 * 420778751 * 3996146881 * 4562284561 * 9036489073 * 30327152671 * 275415303169 * 24517014940753 * 1457772869697961 * 276696631250953741 * 2416923620660807201 * 3011347479614249131 * 1491477035689218775711 * P23 * 25349242986637720573561 * 29034057164920993379000074993 * P29 * 3435950210316335724157758000789490561 * P38 * P51 * P170

[P23= 23480412082098913326841 ]
[P29= 64326196787727903551977150861 ]
[P38= 15653990705896313547269237220041169361 ]
[P51= 153787279330237476887106331233239525756635010497681 ]
[P170= 51049903050598156013062477654241640657829025002976204451060261008689478158715729745160924860467530309657376827104233308157772350164622158651187694109112727796663977157921 ]

using the automated cunningham factor calculator. Unfortunately P170-1 does not factor easily. It has small factors 2*2*2*2*2*3*5*19*23*41, nontrivial factors 57872616793 and 271819582242082307 and a left over 135 digit composite 377341463808543326355616919094375236137049329420738596924600642749151360224737826546584980131240115699417216932276614698618252847357337.

It is fun to google search some of these numbers to see who else has replicated these results.

Fun with factorization

I'm pleased to report that 253262965868307257488778209946038131361 is a factor to P134-1, where P134 is a prime factor of M757=2^757-1 from NFSNET and is also given below. The desire to factor "prime minus 1" stems from proving primality as well as interesting cycles within the Galois field generated by the prime. The computation took 3.27 days using the MPQS routine in PARI/GP. The final linear algebra step reported by GP is: MPQS: starting Gauss over F_2 on 40260 distinct relations MPQS: Gauss done: kernel has rank 1263, taking gcds... MPQS: splitting N after 70 kernel vectors MPQS: time in Gauss and gcds = 1779770 ms Thus, the complete factorization of P134-1 is 2 * 757 * 31771 * 225975587 * 426665371159 * 2901513458813 * 253262965868307257488778209946038131361 * 7052139211996899091204255207082765933446054813418773253. The product of the last two factors, the 94-digit number 1786045692546521893242296017081938219863268932108739868225086786180708765562719633225087287333, was the hard thing to factor. Note that 757 occurs as a factor, which is not a coincidence. The penultimate factor of M757 is P79, and P79-1 factors without too much trouble: P79-1 = 2 * 2 * 2 * 2 * 13 * 757 * 1229897 * 54286614780461303 * 1380765008073205793 * 394201037959710813849206239443089. Again 757 occurs as a factor. Just to repeat the NFSNET result: 2^757-1 = 9815263 * 561595591 * P79 * P134, where P79 = 5722137022002067824248227975095857749151312827809388406962346253182128916964593 and P134 = 24033821640983508088736273403005965446689002356344332130565066643193813901119771090424269412054543072714914742665677774247325292327559

They specifically chose a day he wasn't in DC

On September 11th, Al Qaeda chose to keep George Bush in power. On November 2nd, you too can do the same.

Metric units of time

micromonth	=	2.6297438	second
millihour	=	3.6	second
microyear	=	31.556926	second
milliday	=	86.4	second
milliweek	=	604.8	second
milliday	=	1.44	minute
milliweek	=	10.08	minute
kilosecond	=	16.666667	minute
millimonth	=	43.829064	minute
milliyear	=	525.94877	minute
milliyear	=	8.7658128	hour
kilominute	=	16.666667	hour
megasecond	=	277.77778	hour
megasecond	=	11.574074	day
kilohour	=	41.666667	day
megaminute	=	694.44444	day
megasecond	=	1.6534392	week
kilohour	=	5.952381	week
megaminute	=	99.206349	week
kiloday	=	142.85714	week
kilohour	=	1.3689546	month
megaminute	=	22.815911	month
kiloday	=	32.854911	month
kiloweek	=	229.98438	month
gigasecond	=	380.26518	month
megaminute	=	1.9013259	year
kiloday	=	2.7379093	year
kiloweek	=	19.165365	year
gigasecond	=	31.688765	year
kilomonth	=	83.333333	year
megahour	=	114.07955	year

The weird thing about this table is its order and format. I thought about many different ways of presenting the equivalent information. For example, I could put un-prefixed units along the left column, or I could sort the rows by length of time. Both of these might be more logical. However, the ordering and layout above somehow struck me as paradoxically the most elegant. See also Slow cycle times.

An invented cursive alphabet

This invented cursive alphabet has only four characters, which I will call "i", "r", "l", and "j". The way that they connect to each other is shown below in a four-by-four grid. Note that "rr" and "lr" join in not quite the expected way: there is a cusp instead of a curve before the r. The extra entry at the bottom is "jrj" which has an extra loop to distinguish it from "jj".

Eventually I'll post a Huffman coding of English letter frequencies to map to the English alpabet to this script alphabet.

Document ReFindingKey

For every webpage one creates, also include within it (perhaps in a font the same color as the background) the string like "Document ReFindingKey vturoagj". Also include the ReFindingKey vturoagj in the file name of the webpage (or for index.html, the name of the enclosing directory). If the webpage moves, and all the links to it die, the page can re-found (hence re-finding-key) again by web searching for vturoagj. And people know the ReFindingKey because they know the file name of the old (dead) link.

I'd recommend 8 random characters of 'a' through 'z', enough for 200 billion unique keys. Collisions are not a problem because there is presumably a human in the loop who can distinguish among the collisions.

Update: search UUID

Random string generator

Pitchers' Home Run Derby

Tejada towers at Derby: "Berkman proposed a pitchers' Home Run Derby would be way more entertaining -- because 'all they do in BP is try to hit home runs, anyway.'"

Baseball blasphemies

What changes would I like to see to baseball?

• Trade Nomar to the Giants, for the good of the game. Nomar is great, and I'd love to see him continue to play for Boston, but there's someone who needs him more: Barry Bonds. The world wants to see Bonds hit, and all his intentional walks are denying the world that privilege. The Giants need a high batting average slugging threat behind Bonds in the line-up, so that opposing teams will pitch to Bonds more. To maintain parity, the Yankees should send Alex Rodriguez over, too. Maybe the Giants can give us Jason Schmidt back in exchange.
• Eliminate the home run. (Yeah, I know these blasphemies are incompatible with each other.) With the horrid specter of steroid use hanging over the game, we can lesson the effect of steriods by not rewarding power hitting. Any ball that goes over the far fence is just like any other fence: foul.
• Replace the pitcher with a pitching machine. The outcome of the game depends too heavily on the pitcher's performance. All that repetitive motion gets them injured in sad ways. Replace him with a pitching machine that always throws strikes. The strategic component is choosing the right pitch on every occasion. Put a cap of (say) 85 mph on the pitch, but allow curves of every possible axis, angle, orientation, and rate of rotation. Where the seams are relative to the axis of rotation matters.
• Each league's All-Star lineup should have a defensive squad and an offensive squad. The defensive squad does nothing but field each inning, and the offensive squad does nothing but hit. Of course, a player may be selected to play on both defensive and offensive squads (e.g., Ichiro). Offense matters much more than good fielding, so too often we see sloppy defense in the All-Star game. We all like to see web gems, too.
• Open a franchise in Havana.

Boston Chowderfest 2004

Clam chowder and artificial lemonade do not go well together: Some weird reaction in the mouth causes the lemonade to taste awful. Also, food coma set in after a medium-sized quantity, probably caused by the large quantity of milk or cream.

Polygonal Moser's worm decision problem

Given a worm defined by connected line segments, and a blanket defined by a polygon, can the blanket be rotated, shifted, and flipped to cover the worm?

Three cuts, seven equal pieces

By extending the edges of a triangle, one can cut a cake into seven pieces. Is there a convex shape that can be cut into 7 equal-area pieces by 3 cuts? Failing that, of all shapes which can be cut into 7 equal-area pieces by 3 cuts, which has the minimum perimeter? Does the answer change if we prohibit holes? The answer will probably have a pleasing 3-pointed boomerang shape. Is it possible to cut a (possibly concave) shape into 7 equal-area pieces by 3 cuts so that the resulting pieces are all convex? (Pretty easily yes.) What if we require every cut to be of the form "air-cake-air"? That is, the knife encounters only a single segment of cake along the infinite length cut.

Grammar checking by markov chaining

Start with a reasonably good Markov model of English, say, 1st-order. Also append to it the bigram counts of the text to be grammar checked. This eliminates zero probabilities of non-existent bigrams in the training set. Finally, highlight the bigrams in the text which are low probability, perhaps ranked by probability. Mumble mumble some sort of normalization, conditioning, etc., mumble mumble. The most frequent grammar errors I make are those caused by cut-and-paste, or losing my train of thought while typing. These result in "easy" grammar errors: sentences that make no sense at all. Consequently, these errors can be caught by a relatively simple model of the language.

Things wrong with xcalc

• Button text doesn't scale as the window is scaled
• AC clears memeory
• No visual feedback when keyboard shortcuts are used (especially for operators)
• Buttons should be square
• Buttons should re-array themselves to stay squarish
• When window is large, a large amount of the left side of the output display is unused
• ability to FLIP the arguments to minus, divide, and power.
• Backspace
• 5 + = = = = = should print out multiples of 5
• A few more extra functions, like erf, binomial
• reverse polish notation
• Scroll back of the calculation (view stack)
• cut and paste buttons
• Sound feedback