- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Re: Factorial n
by Richard Guy 04 Jul '06

04 Jul '06

Many thanks for several replies. This one seems to contain the definitive answer. R. On Tue, 4 Jul 2006, moree(a)mpim-bonn.mpg.de wrote: > Richard Guy asked: > > Presumably 0! = 1! = 0^2 + 1^2. > 2! = 1^2 + 1^2 > 6! = 12^2 + 24^2 > > are the only integer solutions of > > n! = x^2 + y^2 > > but is there a proof? R. > > David Wilson wrote: > > No, I don't have a proof, I do have an argument following from a solid > conjecture. > > We know that for n >= 2, there exists a prime p with n appears that for n >= 4, there exists prime p == 3 (mod 4) with n I cannot prove this myself, but I am sure it is true. > > This conjecture implies that for n >= 7, there is a prime p == 3 (mod 4) > with [n/2] factorization of n, so that n! cannot be of the form x^2+y^2. > > ***** > Paul Erdos seems to have been the first to have supplied such a proof. > He namely proved that for n >= 4, there exists > a prime p == 3 (mod 4) with n arithmetic progressions'. The rest of the argument is then as David > Wilson described above. > > Reference: > P. Erdos, Ueber die Primzahlen gewisser arithmetischer Reihen, > Math. Zeitschrift 39 (1935), 473-491. > > I quote now from p. 491: > Mit Hilfe der Primzahltabellen bestimmt man nun leicht die genauen > unteren Grenzen von \xi, von welchen ab zwischen \xi (exkl.) und > 2\xi (inkl.) Primzahlen von den betrachten Formen existieren. Man > findet dass das Intervall \xi Primzahl von der Form 6k+1, fuer \xi \ge 5.5 eine Primzahl von der > Form 6k+5, fuer \zi\ge 6.5 eine Primzahl von der Form 4k+1 und endlich > fuer \zi \ge 3.5 eine Primzahl van der Form 4k+3 enthalt. Aus der > letzten Tatsache folgt auf Grund eines bekannten Satzen der elementaren > Zahlentheorie, dasz 1!, 2! und 6! die einzigen Faktoriellen sind, die > sich in die Summe zweier Quadratzahlen zerlegen lassen. > > The above article of Erdos gives an elementary method to determine > for a certain finite set of moduli d, explicitly numbers x_0(d) > and z(d) such that every interval of the form (x,z(d)x) with > x>=x_0(d) contains a prime p with p=a(mod d), for any a coprime to d. > > More precisely, for a modulus d>=2 put > sigma(d)=\sum_{p<d, p does not divide d}1/p, where p runs over the primes. > Erdos proved that if sigma(d)<1 and z>d(d-1)^{-1}(1-sigma(d))^{-1}, then > there is at least one prime from each primitive congruence class modulo > d in the interval (x,zx] for all x sufficiently large. > This result can be made effective. Erdos did this for d=4 and d=6 > (with the outcome given in the quote above). In my paper > > P. Moree, Bertrand's postulate for primes in arithmetical progressions. > Comput. Math. Appl. 26 (1993), no. 5, 35--43. > > this is done for the remaining 52 values of d satisfying \sigma(d)<1. > > Finally, I liked to note that R. Breusch earlier than Erdos published > a proof of Bertrands' Postulate for modulus 4. It is rather technical > and computational and uses results on the first zeros of L(s,\chi_4). > > R. Breusch, Zur Verallgemeinerung des Bertrandschen Postulates, dass > zwischen x und 2x stets Primzahlen liegen, Math. Zeitschrift 34 (1932), > 505-526. > > In the early 30's also G. Ricci worked on Bertrand's Postulate for > arithmetical > progressions, but I cannot comment on this paper (which I have never seen): > > G. Ricci, Sui teorem di Dirichlet relativo alla progressione arithmetica, > Bolletino della Unione Mathematica Italiana 12 (1933), 304-309. > > I hope this helps, > Pieter Moree >

1 0

Re: Re: [math-fun] Factorial n
by dasimov＠earthlink.net 04 Jul '06

04 Jul '06

Michael writes: << If the primes congruent to a mod m have a large desert between N and (1+e)N, then the density of such primes up to (1+e)N is 1/(1+e) times what it is up to N, and so those two densities cannot both be arbitrarily close to the asymptotic value 1/phi(m) >> Aha -- what I wanted to be true would be, had I wanted the right thing to be true. -dan

1 0

Re: [math-fun] Factorial n
by David Wilson 04 Jul '06

04 Jul '06

Michael Kleber already told us that Erdos had already proved my assertion that primes of the form 4n+1 and 4n+3 exist between n and 2n for n >= 7. I would be willing to conjecture that if there are an infinitude of primes == r (mod m), then there is a prime of this form between n and n(1+e) for sufficient n. Are there any results on the density of such primes relative to all of the primes? If so, then probably the prime number theorem could probably be used to establish the above conjecture. ----- Original Message ----- From: "Eric Bach" <bach(a)cs.wisc.edu> To: "David Wilson" <davidwwilson(a)comcast.net> Sent: Tuesday, July 04, 2006 1:53 AM Subject: Re: [math-fun] Factorial n > On Mon, 3 Jul 2006, David Wilson wrote: > >> No, I don't have a proof, I do have an argument following from a solid >> conjecture. >> >> We know that for n >= 2, there exists a prime p with n > appears that for n >= 4, there exists prime p == 3 (mod 4) with n > 2n. >> I cannot prove this myself, but I am sure it is true. > > Kevin McCurley had a paper (Math. Comp.?) giving explicit prime > number theorems for arithmetic progressions. Probably your supposition > would follow from his work plus some computer checking of small cases. > > Eric > > > > -- > No virus found in this incoming message. > Checked by AVG Free Edition. > Version: 7.1.394 / Virus Database: 268.9.8/381 - Release Date: 7/3/2006 > >

2 1

[math-fun] Factorial n
by Richard Guy 04 Jul '06

04 Jul '06

Presumably 0! = 1! = 0^2 + 1^2. 2! = 1^2 + 1^2 6! = 12^2 + 24^2 are the only integer solutions of n! = x^2 + y^2 but is there a proof? R.

6 7

Re: [math-fun] Sudoku levels
by Michael Reid 02 Jul '06

02 Jul '06

> I implemented the k=1 & k=8 rules, and this is "level 1". > > Interestingly, these 2 rules are somewhat dual to one another -- perhaps someone > else has better insight on this? i think this is well understood. consider the 9 x 9 "possibility matrix" whose rows are indexed by the nine cells in the row [column, box] and whose columns are indexed by the nine possible values, and whose entries are either 0 ("not possible") or 1 ("possible"). to fill in the nine cells, we need to find a "transversal" of the matrix, which is a set of nine non-zero entries, one from each row and each column. suppose the matrix has the property that the rows and columns can be permuted so that the matrix becomes "upper triangular in block form", i.e. looks like / \ | A B | | 0 D | \ / where A and D are square. then it is clear that any transversal must arise from a transversal of A and a transversal of D . the duality is between the sizes of A and D . alternatively, we can interchange the roles of "cell" and "value" which corresponds to transposing the matrix. then we seek a "lower triangular block form" of the matrix, but this is equivalent to upper triangular by reversing the order of rows and the order of columns. mike

1 0

[math-fun] Sudoku levels
by Henry Baker 02 Jul '06

02 Jul '06

I've since extended my program to what I call "level 2" -- propagating forcing constraints a bit further: If a digit in a _row_ can only appear in 2 or 3 positions within the same 3x3 block, then that digit is eliminated from the rest of the block. If the digit can appear in multiple blocks, then we can't eliminate it. Ditto for columns. For blocks, the rule is more complicated. If a digit can only appear within a single row or column within a block, then it can be eliminated from the rest of the row or column, respectively. These new rules, together with the previous set of forcing rules, appears sufficient to solve the LATimes Sudoku's called "Moderate", while the previous set of rules were sufficient for those called "Gentle". However, my "level 2" is not sufficient for LATimes "Diabolical", nor for the Sudoku's in "Sudoku Genius". It would appear that the LATimes _does_ have a precise definition of what it means to be "Gentle" (~ level 1), "Moderate" (~ level 2), and "Diabolical". Since "level 2" appears to be exhausting the notion of what can be done with only local rules & "force fields" (the information propagating on rows, columns & blocks), I would suggest that level 2 captures the notion of "non-backtracking". --- BTW, I mentioned that my bit representation produced "surprises" in that some squares "accidentally" produced singleton sets. However, because these singletons were "accidental", they didn't get a chance to propagate their "first-class" status and suppress the same digit in rows, columns and blocks. While this problem is automatically fixed by level 2, this constraint really belongs to level 1, and so my level 1 program has to have an extra check just for this constraint. "The representation giveth, and the representation taketh away."

3 4

Re: [math-fun] Re: genetics-fun question -- another one
by dasimov＠earthlink.net 30 Jun '06

30 Jun '06

Just a few months ago my sister mentioned to me that her husband's U.S. ancestors all descended from just one married couple, who came to the U.S. around 1650, before having any children. She asked me how many living descendants (whether or not still in the U.S.) that family has today . I had nothing else to go on, so it was a rough seat-of-the-pants blue-sky back-of-the-envelope ballpark guesstimate. Just for fun I'd like to ask anyone interested in coming up with their own estimate to send it to me without posting it to math-fun. On Monday or so I'll post everyone's estimate (including mine). --Dan

1 0

Re: [math-fun] Sudoku levels
by Henry Baker 30 Jun '06

30 Jun '06

Dear Joshua & Mike: I see now what you're saying. No, I implemented a strictly weaker rule, but your rule is more elegantly stated. I'll run some tests. If it can solve "Diabolical" level Sudoku's, then it would be too strong. The intuition of your rule is that if one square isn't strong enough on its own (singleton set) to lay down suppressing fire & kill off pretenders to the digit, then groups of squares might be able to suppress some pretenders. At 08:51 AM 6/30/2006, Joshua Zucker wrote: >I'm not clear from your description of level 1 whether you look at >every set of k cells -- if a set of k cells out of 9 includes at most >k different digits, then those k digits can't appear anywhere else in >the set of 9. (I was very pleased when I realized that this rule with >k = 1 and k = 8 covered the two usual simplest rules, "if a cell can >contain only one digit..." and "if a digit can appear in only one >cell...") > >--Joshua Zucker

1 0

[math-fun] Re: genetics-fun question
by James Propp 30 Jun '06

30 Jun '06

>So figuring out who's mother and who's daughter is as easy as labelling >their genomes a,b and c,d and noticing which of them has the property >that, eg, ccccccccccccc is the same as aaaabbbaabbbb. Neat! (And not even all that subtle; if I'd thought a bit harder about what I supposedly learned in high school, I could've figured it out.) This fact about the asymmetry of the parent-child relationship suggests a more general question: How much can you deduce about the precise way in which two blood-relatives are related simply from looking at their genes? This can be a real-world issue ("And is it your sworn testimony before this court, as an expert in the field of genetics, that this man cannot possibly be the nephew of Howard Hughes?"), but I could imagine it also giving rise to some mathematically amusing albeit unrealistic puzzles ("Assume an infinite genome..."). Michael? Jim

6 7

Re: [math-fun] Sudoku levels
by Henry Baker 30 Jun '06

30 Jun '06

Dear Joshua: I don't understand the description of your rule. Do you mean _any_ k cells, whether or not they're in rows, columns or blocks? Furthermore, what do you mean by "at most k" ? At 08:51 AM 6/30/2006, Joshua Zucker wrote: >I'm not clear from your description of level 1 whether you look at >every set of k cells -- if a set of k cells out of 9 includes at most >k different digits, then those k digits can't appear anywhere else in >the set of 9. (I was very pleased when I realized that this rule with >k = 1 and k = 8 covered the two usual simplest rules, "if a cell can >contain only one digit..." and "if a digit can appear in only one >cell...") > >--Joshua Zucker

1 0