May 2009 - mathfun@mailman.xmission.com

Re: [math-fun] New Pattern Found In Prime Numbers
by Phil Carmody 11 May '09

11 May '09

From: Ray Tayek <rtayek(a)ca.rr.com> > > http://science.slashdot.org/article.pl?sid=09/05/10/1322207 > > <mailto:stephen.schaubach@wellsfargo.com>stephen.schaubach > writes > "Spanish Mathematicians have > <http://www.physorg.com/news160994102.html>discovered > a new pattern > in primes that surprisingly has gone unnoticed until now. > 'They found > that the distribution of the leading digit in the prime > number > sequence can be described by a generalization of > <http://en.wikipedia.org/wiki/Benford%27s_law>Benford's > law. ... As the others have said, this is not new at all. As could have been discovered with only the most elementary research. A simple google search for ``benfords law primes'' points straight to two pages which says almost everything you need to know about the topic. primes.utm.edu/notes/faq/BenfordsLaw.htm primes.utm.edu/glossary/xpage/BenfordsLaw.html In particular they have references to proofs with varying levels of assumptions, culminating with Hill's 1996 paper, which I think finally put the matter to bed. Phil

1 0

Re: [math-fun] Slight change in the rules of chess
by Mark D. Niemiec 11 May '09

11 May '09

Dan Asimov <dasimov(a)earthlink.net> wrote: > I'm wondering if the following potential change in the rules of chess > would make sense, or if it has hidden pitfalls. > > Suppose one player (say Black) has a piece (say a bishop) > that's pinned because if it moved, it would discover > a check to Black's king. And suppose it's White's turn. > > Then I propose that it should be legal for White > to put his own king in "check" from that bishop, since > for the moment that bishop cannot really theoretically > take White's king. > > -->>>General proposed rule: One player should be allowed > to move so as to put their king in "check" from an > opposing piece *if* that piece is -- for the moment -- > forbidden by the rules of chess to move to the square > that king is on. > > (Which of doesn't doesn't mean it would necessarily be > a good idea to do so.) In earlier versions of chess, the objective was to capture the opponsing king - so avoiding putting your own king in check was not a game rule, just an essential strategy. Still, in such a case, moving your own king into a threatened square of a pinned bishop would not be safe, since the bishop would take your king, rendering the exposure of its own king moot. (We can see this dynamic in chess currently - if, say, a bishop is pinned in front of a rook, it is unsafe to move a rook or queen into a square threatened by the bishop.) Your proposal can also make increase the complexity of determining whether a square is threatened or not. Suppose the pinned black bishop is itself pinning a white rook - would the black king be permitted to move into the path of the rook? Theoretically, it should not be able to do so, because even though the rook is pinned by the bishop, the bishop is not available to do the pinning. However, if the king would move out of the pin, this would free the bishop to pin the rook. While unlikely, it's possible to involve a long Rube-Goldberg chain of pieces each pinning each other, and determining it would be impossible to determine whether a particular move is legal or not without examining the positions of many other pieces. Still, it would make for an interesting variant. (In much the same way that modern chess with its stalemate rules makes the endgame subtly more interesting) -- Mark D. Niemiec <mniemiec(a)interserv.com>

4 3

Re: [math-fun] cyclotomic factorization
by Phil Carmody 11 May '09

11 May '09

--- On Sun, 5/10/09, math-fun-request(a)mailman.xmission.com <math-fun-request(a)mailman.xmission.com> wrote: > > There are cyclotomic polynomials Phi(pqr) with maximum > > height 1 where p,q,r == 1 (mod 4) > > E.g.? p = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000949 q = 1000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004533 r = 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000949000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000045330000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000004301816 Using what appears to be one Nathan Kaplan's 2007 result on flat cyclotomics, namely: if p<q<r are prime, and r == +/-1 mod pq, then Phi(pqr) is flat. Note, this is an _if_, not an _iff_. There are interesting flat cases that cannot be proved this way. I might investigate these depending on whether I can steal a copy of Kaplan's paper from somewhere. Phil

1 0

[math-fun] New Pattern Found In Prime Numbers
by Ray Tayek 11 May '09

11 May '09

http://science.slashdot.org/article.pl?sid=09/05/10/1322207 <mailto:stephen.schaubach@wellsfargo.com>stephen.schaubach writes "Spanish Mathematicians have <http://www.physorg.com/news160994102.html>discovered a new pattern in primes that surprisingly has gone unnoticed until now. 'They found that the distribution of the leading digit in the prime number sequence can be described by a generalization of <http://en.wikipedia.org/wiki/Benford%27s_law>Benford's law. ... Besides providing insight into the nature of primes, the finding could also have applications in areas such as fraud detection and stock market analysis. ... Benford's law (BL), named after physicist Frank Benford in 1938, describes the distribution of the leading digits of the numbers in a wide variety of data sets and mathematical sequences. Somewhat unexpectedly, the leading digits aren't randomly or uniformly distributed, but instead their distribution is logarithmic. That is, 1 as a first digit appears about 30% of the time, and the following digits appear with lower and lower frequency, with 9 appearing the least often.'" ... --- vice-chair http://ocjug.org/

3 2

Re: [math-fun] Slight change in the rules of chess
by Dan Asimov 10 May '09

10 May '09

At this point, I aqree with what Gene wrote below. Or at least with the consequences of this kind of thinking: whoever *can* take the other's king first is the winner. --Dan Gene wrote: << I guess I don't see the benefit of an inconsistent set of rules, that one may sometimes place one's King in check, but sometimes not. Perhaps a more sensible modification to the rules would be to always permit moves that put one's own King in check, and then also permit a player to actually capture the opponent's King. >> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

Re: [math-fun] Slight change in the rules of chess
by Dan Asimov 10 May '09

10 May '09

Hmmm, apparently I was wrong and Gene was right. Since, the Black Queen might "checkmate" White -- an apparently inescapable *threat* -- but then thinking the way Gene has done below, it's White who actually has the chance to take the Black King before Black could in principle take the White King. --Dan I wrote: <<<<<< << Gene, that's a worthwhile point, but I don't feel Black "can capture" the White King with the pinned Black Bishop, since that piece is temporarily immobilized. Suppose we elaborate on this example, so that the Black Bishop, which is pinned (because of a potential discovered check to the Black King), were *also* able to discover a checkmate against the White King (from some other Black piece -- let's say the Queen). That, too, would in principle end the game right there, likewise keeping White from exploiting the clear view to taking the Black King. It's easy to cook up such an example. But that's not permitted, since the Black Bishop is deemed immobile. --Dan Gene wrote: <<<< I wrote: << I'm wondering if the following potential change in the rules of chess would make sense, or if it has hidden pitfalls. Suppose one player (say Black) has a piece (say a bishop) that's pinned because if it moved, it would discover a check to Black's king. And suppose it's White's turn. Then I propose that it should be legal for White to put his own king in "check" from that bishop, since for the moment that bishop cannot really theoretically take White's king. >> If White puts his King in check, then on the next move, Black can capture the White King, and the game is over. Thus White never gets the opportunity to exploit that discovered check on Black's King. >>>> >>>>>> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

1 0

Re: [math-fun] Slight change in the rules of chess
by Dan Asimov 10 May '09

10 May '09

Gene, that's a worthwhile point, but I don't feel Black "can capture" the White King with the pinned Black Bishop, since that piece is temporarily immobilized. Suppose we elaborate on this example, so that the Black Bishop, which is pinned (because of a potential discovered check to the Black King), were *also* able to discover a checkmate against the White King (from some other Black piece -- let's say the Queen). That, too, would in principle end the game right there, likewise keeping White from exploiting the clear view to taking the Black King. It's easy to cook up such an example. But that's not permitted, since the Black Bishop is deemed immobile. --Dan Gene wrote: <<<< I wrote: << I'm wondering if the following potential change in the rules of chess would make sense, or if it has hidden pitfalls. Suppose one player (say Black) has a piece (say a bishop) that's pinned because if it moved, it would discover a check to Black's king. And suppose it's White's turn. Then I propose that it should be legal for White to put his own king in "check" from that bishop, since for the moment that bishop cannot really theoretically take White's king. >> If White puts his King in check, then on the next move, Black can capture the White King, and the game is over. Thus White never gets the opportunity to exploit that discovered check on Black's King. >>>> _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

[math-fun] Slight change in the rules of chess
by Dan Asimov 10 May '09

10 May '09

I'm wondering if the following potential change in the rules of chess would make sense, or if it has hidden pitfalls. Suppose one player (say Black) has a piece (say a bishop) that's pinned because if it moved, it would discover a check to Black's king. And suppose it's White's turn. Then I propose that it should be legal for White to put his own king in "check" from that bishop, since for the moment that bishop cannot really theoretically take White's king. -->>>General proposed rule: One player should be allowed to move so as to put their king in "check" from an opposing piece *if* that piece is -- for the moment -- forbidden by the rules of chess to move to the square that king is on. (Which of doesn't doesn't mean it would necessarily be a good idea to do so.) --Dan _____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele

2 1

Re: [math-fun] Fast factoring ?? (really denesting)
by rwg＠sdf.lonestar.org 08 May '09

08 May '09

> On Fri, Dec 19, 2008 at 12:20 PM, <rwg(a)sdf.lonestar.org> wrote: > >> Amen. I've now tried ~ 10^8 cases of (a^(1/5)-b^(1/5))^(1/3) >> without further success, and for sqrt, only >> >> 3/5 4/5 3/5 2/5 2/5 4/5 1/5 1/5 >> 1/5 1/5 - 2 3 + 3 + 2 2 3 - 2 3 + 2 >> sqrt(4 - 3 ) = ---------------------------------------------------. >> 5 >> >> And, of course, these can only give pentanomials. >> --rwg >> ALGORISMIC MICROGLIAS > > I have no technical knowledge on denesting, but here is how I look at > the problem: > > Since sqrt( a^(1/5) + b^(1/5) ) = a^(-2/5) * sqrt( a + (a^4*b)^(1/5) > ), I'll consider only the form: sqrt( a + b^(1/5) ). If sqrt( a + > b^(1/5) ) could be denested, I'd expect it to be denested into the > form: > > x0 + x1*b^(1/5) + x2*b^(2/5) + x3*b^(3/5) + x4*b^(4/5). Notice that in the (comparatively easy) 4th root case, your conjecture catches 1/4 3/4 1/4 sqrt(161 - 12 5 ) = 2 5 - 3 sqrt(5) + 4 5 + 6 but not 1/4 1/4 1/4 3/4 3/4 1/4 sqrt(2) sqrt(31 - 4 3 5 ) = 3 5 - 2 sqrt(5) + 3 5 + 2 sqrt(3). > That's why I don't think you could find anything longer than > pentanomial. OTOH, sqrt( a^(1/7) + b^(1/7) ) is a better bet for > finding hexanomials or longer. Indeed, but the only one I've found so far is perversely pentanomial: 1/7 Sqrt(7 (2 - 2 )) 1/7 3/7 5/7 6/7 ------------------ = -1 + 2 2 + 2 + 2 - 2 . 1/14 2 > Just my 2 cents. > > Warut > You didn't propose 6th roots. Did you have reason to suspect that they are as infertile as they seem to be? --rwg PRECHRISTMAS PETRARCHISMS ALGORISMIC MICROGLIAS

17 71

[math-fun] 1869 MIT entrance exam; SHA1 progress; Xor multiply
by rcs＠xmission.com 07 May '09

07 May '09

Tech Review has put online the 1869 MIT entrance exam. http://libraries.mit.edu/archives/exhibits/exam/arithmetic.html There are 4 parts, English, Arithmetic, Algebra, Geometry. The math parts are relatively easy, corresponding to grade level 10.5, the middle of sophomore year in US high school. I found the English section more challenging: The language skills section is undoable -- the source text to be analyzed is missing. There are questions on history, literature, geography, and current events. I was especially surprised to do badly on the geography questions: I've been to Europe multiple times, and couldn't say exactly where Vienna is, nor describe the course of the Danube. ---- SHA1 update [some funsters have crypto interests] Some respectable cryptographers claim to have reduced the effort to find a SHA1 collision to 2^52 hash computations. Their slides are posted at http://eurocrypt2009rump.cr.yp.to/837a0a8086fa6ca714249409ddfae43d.pdf The presentation is too sketchy to evaluate yet, but the authors are well known. The collision work is about 20 years on a late model PC. ---- Xor Multiply Intel is introducing the PCLMULQDQ instruction, which does a 64x64->128 bit Xor-Multiplication. (Their naming conventions remind me of the Tom Lehrer song about the Red Line.) This instruction is helpful in several crypto applications, and also in working with error correcting codes. Puzzle: a) Use the new instruction in a routine to reverse 64 bits. This swaps the sign bit with the low order bit, etc. b) The new instruction can obviously be used to Xor-Square a 64-bit quantity. Use it to do "square root": collect the odd numbered bits 63-1 in the left half of the word, and the even numbered bits 62-0 in the right half. c) Extra credit: describe the relationship with card shuffling. d) Is PCLMULQDQ useful in implementing an arbitrary pre-specified bit permutation? Rich

4 4