December 2011 - mathfun@mailman.xmission.com

Re: [math-fun] polynomials with lots of integer roots computed in few arithmetic operations (Phil Carmody?)
by rcs＠xmission.com 20 Dec '11

20 Dec '11

I wrote a sort of 'multigrade' search program (in 2004) to look for things like this. It found two degree 16 examples; I verified the smaller. N = 134810 = 2 5 13 17 61 = square-sum of 343 131, 353 101, 359 77, & 367 11 N = 1200890 = 2 5 29 41 101 = SqSm of 827 719, 953 541, 1049 317, 1087 139 the search to N=10M only found one more, 25*134810. [My search could be improved a lot, by concentrating on products of 4K+1 primes. I simply tried all N = 8K+2 not divisible by 3, 7, or 11; followed by the nested loops to require 4 reps as A^2+B^2; and then some additional checks.] The product of X +- 11,77,101,131,343,353,359,367 is the 16th degree poly (1 -539240 113112960316 -11446255449625880 557362201565582307046 -11360452056407446195762520 95576018314432876073784728956 -275534058738780661111020240872360 31960299178050105687332223346003681) with interspersed 0s. It can be calculated in 4 squarings: (((X^2 - 67405)^2 - 3525798096)^2 - 533470702551552000)^2 - 220156343572527011594632754626560000 factors: 67405 = (5 13 17 61) 3525798096 = (2.4 3.2 17 1049 1373) 533470702551552000 = (2.12 3.4 5.3 17 229 3304237) 469208209191321600 = (2.14 3.6 5.2 7.2 11.2 13 19 29 37) = sqrt(last subtrahend) coverage mod 17: 6 8 1 5 3 4 2 7. ---------- Quoting Warren Smith <warren.wds(a)gmail.com>: > In the book by Crandall & Pomerance, > Phil Carmody is mentioned as having found a > lot of polynomials of the form > Poly(x) = (((x^2-a)^2-b)^2-c)^2-d > with all 16 roots being integers. > [Is it possible to get 32 integer roots at the next stage?] > > Might Phil inform us more about how he did that and what are these > polynomials? > > > -- > Warren D. Smith > http://RangeVoting.org <-- add your endorsement (by clicking > "endorse" as 1st step) > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >

1 0

Re: [math-fun] Converting numbers with complex bases
by Bill Gosper 19 Dec '11

19 Dec '11

Andy Latto> On Tue, Jul 12, 2011 at 11:22 AM, Kerry Mitchell < lkmitch(a)gmail.com> > wrote: >> Hi, >> >> Using the digits {0, 1} and the complex base -1+i, it's straightforward >> to >> show that 1010 = 1+3i. �Is there an easy way to go backward? �That is, >> given >> a complex number in the form a+bi, recover its "binary" representation? >> �I'm >> immediately interested in the case for bases -1+i and -1-i (digits {0, >> 1}), >> but also interested in the general case. > > The standard procedure for converting a number to another base works > fine. If we want to express a number N in base B, divide N by B, > finding Q and R such that > > (*) N = B.Q + R > > where R is a digit. Then find the base-B representation of Q, and add > an R on the end. If (*) always has a solution, then any number can be > represented in that base with that digit set. If the solution of (*) > is always unique, the representation is unique. > > Andy Hey, that's pretty neat. (1+3i)/(i-1) =1-2i comes out integral, so the low digit is 0. But (1-2i)/(i-1) = i/2-3/2, so you have no choice but 1, which you subtract with the assurance of an integer quotient. The process *must* converge to 0 for all Gaussian integers! Out[65]= 69 + 105 I In[66]:= {%, % - 1}/(I - 1) Out[66]= {18 - 87 I, 37/2 - (173 I)/2} In[67]:= {%[[1]], %[[1]] - 1}/(I - 1) Out[67]= {-(105/2) + (69 I)/2, -52 + 35 I} In[68]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[68]= {87/2 + (17 I)/2, 44 + 9 I} In[69]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[69]= {-(35/2) - (53 I)/2, -17 - 26 I} . . . Out[76]= {3, 7/2 + I/2} In[77]:= {%[[1]], %[[1]] - 1}/(I - 1) Out[77]= {-(3/2) - (3 I)/2, -1 - I} In[78]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[78]= {I, 1/2 + (3 I)/2} In[79]:= {%[[1]], %[[1]] - 1}/(I - 1) Out[79]= {1/2 - I/2, 1} In[80]:= {%[[2]], %[[2]] - 1}/(I - 1) Out[80]= {-(1/2) - I/2, 0} So, reading backwards, the [[2]] branches mean 1 and the [[1]] branches mean 0, and 69+105i = {1,0,1,0,...,1,1,0}. When there are more than two possible digits, can we simply try subtracting them all and have exactly one quotient come out even? Converting pure fractions might be trickier. After Knuth Vol 2, the B=i-1 figure is http://gosper.org/basei-1.png . How do you choose Q and R? R=0 in the red and yellow region, 1 in the blue and green region. Or we could regard this as the base (i-1)^2 region divided into four R, 01,00,11,10 top to bottom. In ordinary base conversion, this is the easier case--just multiply by the base and take floor. But what is floor here? Note that the problem extends to *real* bases with complex digits. Inscribe http://www.tweedledum.com/rwg/rad2Image4.gif in the unit circle and rotate pi/3. This is the subset of the complex plane representable base 2 with digits 0 and the three cube roots of 1. Throw a dart toward 0 and the first digit depends on which subregion it's in. If it's in a white area (are you sure?), you'll need a minus sign. Julian and I noticed that the boundary of the overall region is six Sierpinski gaskets around a hexagon, pointing alternately inward and outward. Julian found its Fourier series. --rwg

3 4

Re: [math-fun] q^20? Convolution and continued fractions
by Bill Gosper 19 Dec '11

19 Dec '11

>> his paper, web.maths.unsw.edu.au/~mikeh/webpapers/paper12.pdf< http://web.maths.unsw.edu.au/%7Emikeh/webpapers/paper12.pdf>gives alternative expressions >> for the geometric denominators CF below (which include the >> Rogers-Ramanujan CF). > > [...] > In which case my sum quotient lhs developed a rash of q^(1/4), leading to > this peculiarity: > > Sum[q^n^2/QPochhammer[q, q, 2*n], {n, 0, Infinity}]/ > Sum[q^(2*n + n^2)/QPochhammer[q, q, 1 + 2*n], > {n, 0, Infinity}] == (QPochhammer[q^8, q^20]* > QPochhammer[q^12, q^20])/(QPochhammer[q^4, q^20]* > QPochhammer[q^16, q^20]) > > q^20? --rwg > (Much aided by Julian) > [...] > According to PSLQ, Sum[q^n^2/QPochhammer[q, q, 2*n],{n, 0, Infinity}]== 1/(QPochhammer[q, q^20]* QPochhammer[q^3, q^20]*QPochhammer[q^4, q^20]* QPochhammer[q^5, q^20]*QPochhammer[q^7, q^20]* QPochhammer[q^9, q^20]*QPochhammer[q^11, q^20]* QPochhammer[q^13, q^20]*QPochhammer[q^15, q^20]* QPochhammer[q^16, q^20]*QPochhammer[q^17, q^20]* QPochhammer[q^19, q^20]) and therefore Sum[q^(2*n + n^2)/QPochhammer[q, q, 1 + 2*n],{n, 0, Infinity}]== 1/(QPochhammer[q, q^20]* QPochhammer[q^3, q^20]*QPochhammer[q^5, q^20]* QPochhammer[q^7, q^20]*QPochhammer[q^8, q^20]* QPochhammer[q^9, q^20]*QPochhammer[q^11, q^20]* QPochhammer[q^12, q^20]*QPochhammer[q^13, q^20]* QPochhammer[q^15, q^20]*QPochhammer[q^17, q^20]* QPochhammer[q^19, q^20])} Are these known? (They could simplify slightly.) --rwg More than slightly. Noodling just now with Julian, Sum[q^n^2/QPochhammer[q, q, 2*n],{n, 0, Infinity}]== QPochhammer[q^2, q^2]/ (QPochhammer[q, q]*QPochhammer[q^4, q^20]* QPochhammer[q^16, q^20]) Sum[q^(2*n + n^2)/QPochhammer[q, q, 1 + 2*n], {n, 0, Infinity}] == QPochhammer[q^2, q^2]/ (QPochhammer[q, q]*QPochhammer[q^8, q^20]* QPochhammer[q^12, q^20]) Still, no word from the toldyasos. --rwg

1 1

[math-fun] Maximally Symmetric Heron Simplices. Some impossible, some not, some computer-sought.
by Warren Smith 19 Dec '11

19 Dec '11

Maximally symmetric Heron simplices ====Warren=D=Smith===Dec=2011====== A "Heron" simplex is one with all edge lengths, triangle-areas, ..., and volume, all integer. Heron simplices "don't want to exist" because many quantities need to be integer that "want" to be irrational algebraic numbers. Thus when searching for Heron simplices, symmetry is your friend. For a symmetric Heron simplex, the search is simpler (fewer parameters describe the simplex) and also there are fewer quantities that we need to force "against their will" to be integers (since the symmetry causes many of them to automatically be equal). TRIANGLES: Obviously a Heron triangle cannot be equilateral. (Area would then be irrational.) The most symmetric it can be is isoceles, i.e. 2-symmetric. And there are an infinity of isoceles Heron triangles, as you can see by gluing together two identical mirrored pythagorean right triangles at a common leg. Result: legs=m*m+n*n, base=2*(m*m-n*n)=2*(m-n)*(m+n) or legs=m*m+n*n, base=4*m*n are two 2-parameter families of isoceles Heron triangles, showing the number of such triangles with diameter<N is at least of order N. I elsewhere proved that the number of (general) Heron triangles with diameter<N is of order N^(1+o(1)) so we see that the isoceles ones constitute a goodly fraction (perhaps even a nonzero constant fraction?) of all Heron triangles. TETRAHEDRA: It is not hard to see that the most symmetric a Heron tetrahedron could hope to be is 8-symmetric. This would be achieved if it had 2 edge lengths a and b with "the a's forming a quadrilateral and the b's its two diagonals." However, apparently no 8-symmetric Heron tetrahedra exist... or at least, computer says there are none with diameter<500000... Let's prove that: In order for one to exist, it would be necessary and sufficient for a and b to obey: a=odd b=even 2<=b<=2*a-2 a>=3 (2*a*a - b*b)/2 = SquareInteger <==> 2*a*a-b*b = EvenSquare ((2*a+b)*(2*a-b))/4 = SquareInteger <==> 4*a*a-b*b=EvenSquare Can that happen? By Euclid's characterization of Pythagorean triples http://en.wikipedia.org/wiki/Pythagorean_triple we have from the last condition that for any primitive solution (a,b) that b=4*m*n and a=m*m+n*n with m,n of opposite parity wlog [or anyway with m and having different numbers of 2s in their factorizations] and hence from the penultimate condition we'd see 2*(m*m+n*n) = 16*m*m*n*n + evensquare which is impossible since the right hand side contains an even number of 2s in its factorization and the left hand side contains an odd number. Hence THEOREM: An 8-symmetric Heron tetrahedron cannot exist! [A different proof of this nonexistence theorem was also given, shortly before his table 2, by Ralph Heiner Buchholz: Perfect Pyramids, Bulletin Australian Mathematical Society 45 (1992) 353-368, and Buchholz also classifies all possible "types" of tetrahedra...] Given that an 8-symmetric Heron tetrahedron cannot exist, it is not hard to see that the most symmetric a Heron tetrahedron could hope to be is 4-symmetric. One way this can be achieved by having 2 edge lengths a, b, c with "the a's forming a quadrilateral and b and c its two diagonals." I constructed a 2-parameter infinity of this kind of Heron tetrahedra previously, showing at least order N^(1/14) of primitive 4-symmetric Heron tetrahedra exist with diameter<N. The number of 4-symmetric Heron tetrahedra with diameter<=16384 is 25, which is 6.3% of the 394 general Heron tetrahedra in that range. It would not surprise me if the 4-symmetric Heron tetrahedra constitute a nonzero constant fraction of all Heron tetrahedra; indeed perhaps they and tetrahedra derived from them constitute asymptotically a 100% fraction of all Heron tetrahedra. I made the following CENSUS: diameter #of [a,c,c,c,c,b]-type primitive Heron tets with diam<that ---------------------------------------------------------------------- 1024 0 2048 5 4096 8 8192 14 16384 25 32768 46 65536 57 131072 103 and the count seems to be growing proportionally to diam^0.7 roughly. A different kind of 4-symmetric tetrahedron has 4 faces, all of which are congruent Heron triangles with sides a,b,c. (Fred Lunnon calls these "isohedral" although I think that is a bad name. That bad name has already been used to mean something else in the world of tilings.) There are known to be an infinity of this other kind of 4-symmetric Heron tetrahedron also. [Theorem 1 of Buchholz shows this using elliptic curves -- getting an exceedingly weak lower bound of order lnln(Diameter) on the count -- but apparently, unknown to Buchholtz, this infinitude via the same proof was actually already understood by E.Haentzschel: Sitzungsber. Berlin Math. Gesell. 12 (1913) 101-108 and 17 (1918) 37-39 following up on groundwork by R. G:untsche: Sitzungsber. Berlin Math. Gesell. 6 (1907) 38-53 and Archiv Math. Phys.(3) 11 (1907) 38-53.] The isohedral Heron tetrahedra seem far less numerous than the [a,c,c,c,c,b] type. Here is a CENSUS: diameter #of [a,b,c,c,b,a]-type primitive Heron tets with diam<that ---------------------------------------------------------------------- 256 1 512 1 1024 2 2048 3 4096 6 8192 7 16384 10 32768 12 and the count seems to be growing proportionally to diam^0.6 very roughly. All the [a,b,c,c,b,a]-type primitive Heron tetrahera with diam<32768: a b c ------------------------ 203 195 148 888 875 533 1804 1479 1183 2431 2296 2175 2873 2748 1825 3111 2639 2180 5512 5215 1887 8484 6625 6409 11275 10136 8619 14637 10933 10100 19695 16448 13073 32708 31493 24525 4D-SIMPLICES: Considering permutations of the vertices... There would be one and only one way a 4-simplex could have an order-5 symmetry (or any multiple of 5): if it had 2 squared edge lengths a and b with the a's forming a pentagon and the b's the "inscribed pentagram." However, the 4-volume of such a beast for Heronity would need to be integer, which would be equivalent to demanding 5*(b^2-3*b*a+a^2)^2 = square which is impossible since the "square" would contain an odd number of 5s in its factorization. Hence THEOREM: a 5-symmetric Heron 4-simplex is impossible! Given that, the most symmetric a Heron 4-simplex could hope to be is if at least one vertex is uninvolved in the symmetry, so it is really a lower-dimensional symmetry. One possible way to build a 4-symmetric 4-simplex would be to make one 3D face be an isohedral Heron tetrahedron with edge lengths a,b,c; then join all 4 of its vertices to a 5th vertex via 4 equal edges of length d. (If d were odd this would require a,b,c all to be even.) I did a computer search up to diameter 263000 for this kind of 4-simplex (Heron tetrahedra of type [a,b,c,c,b,a]+dddd) and found nothing. Here is a Cayley matrix for a different possible 4-simplex (squared edge lengths as entries) which also would be 4-symmetric if it existed. [0 a a b b 1] [a 0 c e e 1] [a c 0 e e 1] [b e e 0 d 1] [b e e d 0 1] [1 1 1 1 1 0] And my computer undertook a search for those up to diameter 133000 and found nothing. Based on heuristic "probability" arguments I suspect there are no 4D Heron simplices. However, I'd be a lot more convinced of that if anybody carried out an exhaustive search up to diameter 10^9, which might now be feasible with a good implementation of my N^(1+o(1))-time exhaustive generation algorithm. But it is not trivial to implement that algorithm and there are many games you can play within that framework to "prune the search." -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

Re: [math-fun] Number of representations of N as sum of two squares
by Dan Asimov 17 Dec '11

17 Dec '11

Nifty formulas. By coincidence, earlier this morning I just happened to be scanning the last section (7-5) of Topics in Number Theory*, vol. II. by William LeVeque, where a related issue is addressed with a rather hairy proof: Let B(x) := the number of positive integers <= x that are each representable as the sum of two squares. Then B(x) is asymptotic to b*x/sqrt(log(x)) as x -> oo, where b is the constant b := sqrt(1/2) * Prod 1/sqrt(1-1/p^2) over all primes p == 3 (mod 4). --Dan _________________________________________________________________________________________________________________________________________________________ *A terrific and deep 2-volume set, where vol. II proves Kummer's theorem, the Tbue-Siegel-Roth, theorem, the (Hilbert-)Gelfond-Schneider theorem, and the Prime Number theorem. Gene wrote: << Warren wrote: << N=a^2+b^2>0 where a,b are integers (of either sign) #representations = 4*sum(over all divisors d of N) ( [1 if (d mod 4)=1 else 0] - [1 if (d mod 4)=3 else 0] ) I am not sure who first invented this nifty formula (Gauss?). It makes it clear, though, that #representations(N) < #divisors(N) < exp(log(2+o(1))*lnN/lnlnN). >> Let r[s](n) be the number of representations of n as the sum of s squares. This is counted as the number of distinct s-tuples (x[1], ..., x[s]) such that x[1]^2 + ... + x[s]^2 = n. Then sum(r[s](k), n = 0 ... n) ~ (πn)^(s/2) / (s/2)! . Proof: The sum is the number of integer lattice points in an s-dimensional ball of radius sqrt(n). >> ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] Number of representations of N as sum of two squares
by Warren Smith 17 Dec '11

17 Dec '11

N=a^2+b^2>0 where a,b are integers (of either sign) #representations = 4*sum(over all divisors d of N) ( [1 if (d mod 4)=1 else 0] - [1 if (d mod 4)=3 else 0] ) I am not sure who first invented this nifty formula (Gauss?). It makes it clear, though, that #representations(N) < #divisors(N) < exp(log(2+o(1))*lnN/lnlnN).

2 2

Re: [math-fun] q^20? Convolution and continued fractions
by Bill Gosper 17 Dec '11

17 Dec '11

On Fri, Dec 9, 2011 at 5:04 AM, Bill Gosper <billgosper(a)gmail.com> wrote: > Mike Hirschhorn points out that since a regular CF with geometrically > progressing terms can be normalized to have geometrically progressing > numerators and constant denominators, e.g., > > > 1 > c + ----------------- > c 1 > - + ------------- > q c 1 > -- + -------- > 2 c 1 > q -- + --- > 3 . > q . > . > = > q > (--) > 2 > c > c (1 + ------------) > 3 > q > (--) > 2 > c > 1 + -------- > 5 > q > (--) > 2 > c > 1 + ---- > . > . > . > his paper, web.maths.unsw.edu.au/~mikeh/webpapers/paper12.pdf<http://web.maths.unsw.edu.au/%7Emikeh/webpapers/paper12.pdf>gives alternative expressions > for the geometric denominators CF below (which include the > Rogers-Ramanujan CF). In which case my sum quotient lhs developed a rash of q^(1/4), leading to this peculiarity: Sum[q^n^2/QPochhammer[q, q, 2*n], {n, 0, Infinity}]/ Sum[q^(2*n + n^2)/QPochhammer[q, q, 1 + 2*n], {n, 0, Infinity}] == (QPochhammer[q^8, q^20]* QPochhammer[q^12, q^20])/(QPochhammer[q^4, q^20]* QPochhammer[q^16, q^20]) q^20? --rwg (Much aided by Julian) The general > formula in the mitslides.pdf allows denominator(k) = a/q^k + b, which > seems neither fish nor fowl. > --rwg > > On Thu, Dec 8, 2011 at 1:43 PM, Bill Gosper <billgosper(a)gmail.com> wrote: > >> MikeS> >> >> Great! I'd love to see the rest of the slides. >> >> >> They're pretty cryptic: http://gosper.org/mitslides.pdf >> >> MikeS> I take it the >> denominator in each sum is the generalized q-Pochhammer symbol >> described at the bottom of the page here:http://mathworld.wolfram.com/q-PochhammerSymbol.html >> >> Precisely. (eqn 18) Here's the lhs written out: >> >> [bagbiting wrap-happy GMail.] > > > >> >> Numerically, for c=1, q=1/2, >> >> (c107) CF(RECTFORM(APPLY_NOUNS(POCHSIMP(APPLY_NOUNS(SUBST([Q = 5.0b-1,C = >> 1,INF = 15],D94[1])))))); >> >> (d107) [1, 2, 4, 8, 16, 32, 64, 128, 260] >> >> (This container was filled at the manufacturing facility, but some >> settling may have occurred during shipping.) >> [...] >> >> On Thu, Dec 8, 2011 at 5:46 AM, Bill Gosper <billgosper(a)gmail.com <http://gosper.org/webmail/src/compose.php?send_to=billgosper%40gmail.com>> wrote:> I just stumbled upon slides from some forgotten talk containing a matrix> sketch of> an identity which specializes to> 2> n> inf 2 -- - n/2> ==== n n 2> \ (- 1) %i q> (c + %i) > ---------------------> / n %i> ==== c (- --, - q; - q)> n = 0 c n> ------------------------------------> 2> n> inf 2 -- + n/2> ==== n 2> \ %i q> > --------------------> / n %i q> ==== c (- q, ----; - q)> n = 0 c n>> => 1> c + -----------------> c 1> - + -------------> q c 1> -- + --------> 2 c 1> q -- + ---> 3 .> q .> .>>> (Sorry, no Mma. It was being unusably, inconceivably stupid on this.)> --rwg >> >[...] >> >>

1 1

[math-fun] Optimum algorithms for generating Heron triangles; better count bounds & generators for d-simplices
by Warren Smith 17 Dec '11

17 Dec '11

Unfortunately my post was wrong. I now explain the (stupid) problem and correct it. It all was valid for Heron triangles a,b,c which happen to be generated by Bucholtz's parameterization: a = (n^2 + k^2)m, b = (m^2 + k^2)n, c = (m + n)(m n - k^2), semiperimeter = s = (m + n)m n, area = d = k m n(m + n)(m n - k^2); However, stupidly, I forgot that Heron triangles often arise from this parameterization only in nonprimitive form and then you'd need to divide a,b,c by gcd(a,b,c) to primitivize. To try to recover from my error, we can employ this 4-parameter description of ALL heron triangles a,b,c [now no need to divide by GCDs to primitivize, in the sense that the primitive ones already are represented directly] stated by Derrick N Lehmer: Rational triangles, Annals of Maths 2ser 1 (1899-1900) 97-102 and as he says also known to various previous authors: a = p q (r^2 + s^2) b = (p s +- q r) (p r -+ q s) c = r s (p^2 + q^2) area = p q r s (p s +- q r) (p r -+ q s) circumradius = (p^2 + q^2) (r^2 + s^2) / 4 semiperimeter = (a+b+c)/2 inradius * semiperimeter = area Now, attempt to recapitulate my old argument, basically. >From a, we can factor it into 3 factors in a^o(1) ways at most and represent the 3rd factor as sum of 2 squares in a^o(1) ways at most. Hence there are at most a^o(1) heron triangles with side a. Similar argument for side c. [Similar argument for circumradius!] For side b it is trickier. Focusing on the first sign choice wlog, b = X*Y where X=(p s + q r) and Y=(p r - q s) we can factor b=X*Y in all possible ways namely <b^o(1) ways. Then solving for p,q in terms of X,Y,r,s we find q = (r*X-s*Y)/(r^2+s^2) p = (r*Y+s*X)/(r^2+s^2) or similarly r=(p*Y+q*X)/(p^2+q^2) s=(p*X-q*Y)/(p^2+q^2). or we can solve for other pairs of variables instead. If we solve for {p,r} then we find r = X/(2*q) + squareroot( X^2 - 4*q*Y*s - 4*q^2*s^2 )/(2*q) p = X/(2*s) - squareroot( X^2 - 4*q*Y*s - 4*q^2*s^2 )/(2*s) for example. Thus a rational solution {p,r} only exists if X^2-4*Y*q*s-4*(q*s)^2 is a square. Similarly for {q,s} to exist we need X^2+4*Y*p*r-4*(p*r)^2 to be square. Similarly for {q,r} to exist we need Y^2+4*X*s*p-4*(s*p)^2 to be square. Similarly for {p,s} to exist we need Y^2+4*X*q*r-4*(q*r)^2 to be square. By "completing the square" on the last quadratic(q*r), i.e. rewriting it as Y^2 + X^2 - (2*q*r-X)^2 we can express this as a demand that Y^2+X^2 be a sum of two squares. We can proceed similarly for all the other 3 quadratics. Thus the ways in which Y^2+X^2 is a sum of 2 squares yield the values of p,q,r,s. More precisely: By first factoring b=X*Y all possible ways and then finding all possible ways to write X^2+Y^2 as sum of two squares, and then considering each unsquared square as 2*q*r-X and the like, we deduce q*r, s*p, p*r, and q*s. Then by factoring them in all possible ways we deduce p,q,r,s. Hence we realize the number of possibilities is b^o(1) and we can find them all in this time bound. So-- now without the error I made last time-- THEOREM: the number of Heron triangles with side=n [or area=n, or circumradius=n, apparently also work! And I do not need to demand n be the LONGEST side either!], is bounded by n^o(1) and all of them may be found by algorithm in time n^o(1). And now everything I said last post -- all of which are corollaries of this theorem-- are restored to validity. (Until another bug is found...:)

1 0

Re: [math-fun] mental factoring
by Dan Asimov 16 Dec '11

16 Dec '11

What got me started on this was trying to factor 2257, and after finding no small prime factors, noticing that 2257 = 37 + 2220 = 37 + 20*111 = 37 + 20*3*37 = 37*61. But that was just a lucky break, and I was wondering if there are better ways than routinely checking each prime in order (or relying on luck). --Dan ________________________________________________________________________________________ It goes without saying that .

1 0

[math-fun] mental factoring
by Warren Smith 16 Dec '11

16 Dec '11

so, just to make FH's point clearer, the amazing fact that 1001=7*11*13 allows you to check N for divisibility by 11, 13, or 7 all at once as follows. 1. compute N mod 1001 by subtracting the most-sig 3-digit block of N (assumed 6 digits long) from the least-sig 3-digit block. Then take absolute value. 2. Result is a 3-digit number abc. 3. Check divisibility by 11 by computing a-b+c and if result is 0 (or divisible by 11) then N was divisible by 11. Otherwise not. 4. You're on your own about dividing the 3-digit number by 7 and 13, but you could just memorize all multiples of 7 and 13 up to 999 for instant result or just subtract out some obvious multiple like 130, 260, and then you only need to memorize multiples of 13 up to 130. --- Also of course divisibility by 2 and 3 and 5 are trivial to check (for 3, sum of digits must be divisible by 3; for 5 and 2, the last digit alone reveals). Not bad. Personally, though, I think trying to go further is pretty stupid in the modern age. I used to know John Conway and he was very impressive, but his interest in doing this kind of mental-calculation trick to amaze people, actually struck me as the least-impressive thing about him.

3 2