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

[math-fun] I just wrote out a "contingency pdf" of my G14 talk
by Bill Gosper 14 Jan '20

14 Jan '20

g14 talk <http://gosper.org/gosper-bill-talkproposal-dragon%20function,vs%20dragon%20…> . I hope I can get a big enough time slot to throw in some animations, or have time to remedy a technical catastrophe such as befell me at G13. —Bill

1 0

[math-fun] 99% accurate Kepler solution, e < 0.5
by Brad Klee 13 Jan '20

13 Jan '20

When e< 0.5, M = E - e*sin(E) is approximately solved by: E = M + e/(1-e)*sin(M)-(2*e^2)/(1-e^2)/Pi^2*M*(2*Pi-M)*sin(M), This seems to be the most simple three-term solution, which matches E(M) and E'(M) at integer multiples of Pi. The error increases with e, so the approximation becomes unusable after e = 0.5, where the error is still less than 1% of 2*Pi. All planets are well within this bound, but some bound comets are not. Check with the wiki-tabulation at: https://en.wikipedia.org/wiki/Orbital_eccentricity For worst-case planet Mercury with e=0.21, accuracy is better than 99.7%. The approximate E(M) is so simple, I think it would have been discovered hundreds of years ago, but this is the first time I've seen it. Anyone with a Reference? Or how about a simple 99% approximation for e > 0.5? --Brad (* Mma Accuracy Check *) Manipulate[Plot[Times[Subtract[ M + e/(1 - e)*Sin[M] - (2*e^2)/(1 - e^2)/Pi^2*M*(2*Pi - M)* Sin[M], InverseFunction[# - e Sin[#] &][M]], 100/2/Pi], {M, 0, 2 Pi}, PlotRange -> {-1, 1}], {e, 0.001, 0.5}]

2 2

[math-fun] When FindIntegerNullVector is too fussy
by Bill Gosper 13 Jan '20

13 Jan '20

For some stuffy reason, UnitConvert refuses to convert square degrees to steradians. An ill-chosen web page said there were 41253 square degrees in a sphere. (It didn't even say "approximately".) What is this number, exactly? It's pretty trivial to Google, but it's also easy just to guess. It's presumably some product of small rationals and π. FindIntegerNullVector[Log[{41253, 2, π, 3, 5, 7}]] FindIntegerNullVector::rnfu: FindIntegerNullVector has not found an integer null vector for {Log[41253],Log[2],Log[\[Pi]],Log[3],Log[5],Log[7]}. Don't underrate LatticeReduce! For N digit accuracy, you might want to keep this two-liner handy: LR[L_, N_] := Block[{$MaxExtraPrecision = N}, LatticeReduce[Transpose[Prepend[IdentityMatrix[Length[L]], Round[10^N*L]]]]] For six digits, In[114]:= LR[Log[{41253, 2, π, 3, 5, 7}], 6] Out[114]= {{3, 1, -6, 1, -4, -2, 0}, {10, 1, 3, -12, -7, 3, 2}, {9, 1, 12, 2, -4, -2, -7}, {-2, 1, -1, -4, 0, -13, 8}, {6, -1, -9, 1, 17, 3, -4}, {2, -5, 3, 4, -3, 14, 14}} The first vector is always shortest. Its first component, 3, is the error. This looks like the answer, since the exponents of 41253 and 7 are respectively 1 and 0: In[115]:= {2, π, 3, 5, 7}^{-6, 1, -4, -2, 0} Out[115]= {1/64, \[Pi], 1/81, 1/25, 1} In[117]:= Times @@ %% Out[117]= \[Pi]/129600 I.e., 1 ~ 41253 ⨉ π/360², a satisfying mixture of π, "degrees", and "square". —rwg

1 0

[math-fun] AnAgraM + aNAGram = AnagRAm
by Éric Angelini 12 Jan '20

12 Jan '20

Hello Math-Fun (Gilles E.-F. and Alexandre W. in BC copy), Let a + b = c and a < b < c and a, b, c = anagrams of each other. What is the smallest possible "a" with this property? Have all a's under one million been computed already? Two examples: a = 41904 b = 49140 c = 91044 and a = 164907 b = 604197 c = 769104 Sorry of this is old hat. Best, É.

4 5

[math-fun] Coordination sequences for polyhedra
by Tom Karzes 07 Jan '20

07 Jan '20

Neil, do you have coordination sequences for all of the Platonic/Archimedean/Catalan solids? Those seem like the most fundamental ones for polyhedra. I could probably generate them without too much trouble if needed. Tom

6 14

[math-fun] Regular Polygon Region Member Algorithm
by Brad Klee 06 Jan '20

06 Jan '20

Input: A regular N-gon P_N, and a point (x,y). Output: Membership of (x,y) relative to P_N. Description: Center P_N on the origin, and determine bounding lines as { (x,y) : L_n(x,y) = 0}, with n from 1 to N. The polynomial H(x,y) = L1*L2*...LN gives a height to any point (x,y). By simple bounds on the height and norm of (x,y), it is possible to tell whether or not (x,y) falls interior to the N-gon, or on a boundary ( either point-like or line-like ). The trade-off is that this algorithm requires ~N additional multiplications in order to replace ~N logical operations with only two or three. It is easy to program, but possibly non-optimal. For a use case see: Wolfram Community, "Fixing RegionMember & A302176 at once", https://community.wolfram.com/groups/-/m/t/1854034 --Brad

1 0

[math-fun] Unseasonal decorations
by Fred Lunnon 06 Jan '20

06 Jan '20

Tardy Christmas tree bauble, or maybe New Year detonation --- https://www.dropbox.com/s/6uiwzac2rwaoqwu/enneaconta_movie.8.gif (ignore any pop-ups; open in browser if static) Delayed owing to a technical hitch while packing polytope: see https://www.dropbox.com/s/otp534dy9gye0in/enneaconta_evert.gif Is it Anish Kapoor's latest wheeze to make Orbits great again? A fairground carousel with elf & sleighty issues? A wrecked novelty umbrella? No --- it's an everted enneacontahedron! Aren't you glad you asked ... WFL

3 8

[math-fun] Still not about primes
by Keith F. Lynch 06 Jan '20

06 Jan '20

Victor Miller <victorsmiller(a)gmail.com> wrote: > This phenomenon was dubbed "Chebyshev's bias" by Sarnak et. al. : > https://en.wikipedia.org/wiki/Chebyshev%27s_bias > Granville and Martin have an entertaining article in the Monthly > about it: https://dms.umontreal.ca/~andrew/PDF/PrimeRace.pdf Thanks. That's a very interesting paper. But it's not at all what I was talking about. I was looking, not at whether there are more primes congruent to 3 mod 4 than to 1 mod 4, but at whether there are more primes for which a 3 mod 4 prime follows a 1 mod 4 prime or vice versa than there are for which a 3 mod 4 prime follows another 3 mod 4 prime or a 1 mod 4 prime follows another 1 mod 4 prime. Similarly with 1 mod 3 vs. 2 mod 3 primes. The bias toward prime types changing appears to be much larger than the Chebyshev bias. Of the first million primes (other than 2 and 3) there are 499799 and 500201 primes congruent to 1 mod 4 and 3 mod 4 respectively, a difference indistinguishable from noise, but there are 562576 primes for which a 3 mod 4 prime follows a 1 mod 4 prime or vice versa, and 437423 primes for which a 3 mod 4 prime follows another 3 mod 4 prime or a 1 mod 4 prime follows another 1 mod 4 prime. But, as I said right in the subject line, that wasn't what my post was about either. It was about the fact that there's a similar bias, in the same direction, in whether 3 mod 4 prime follows a prime that follows 1 mod 4 prime or vice versa (i.e. two spaces apart). Intuitively, the bias ought to be in the *opposite* direction. Not because of anything to do with primes, but because of binary sequences in general. If f(n) is usually different from f(n+1), and there are only two possible values for f, then surely f(n) must usually be the same as f(n+2). That's what my post was about. I checked my code several times, and counted the numbers by a completely different method (using search and replace in Emacs) before I trusted my results. My idea that the Thue-Morse sequence (A010060) might be a good one to test was productive. (That binary sequence starts with 0, then in each step the complement of the sequence is appended to the sequence: 0, 01, 0110, 01101001, 0110100110010110, etc.) Adjacent terms (f(n) vs. f(n+1)) differ 2/3 of the time. Terms two steps apart (f(n) vs. f(n+2)) *also* differ 2/3 of the time! (So much for my intuition.) I also checked differences up to 20 apart (f(n) vs. f(n+20)). Here's a table of what (asymptotic) proportion of the time the terms differed: 1 2/3 2 2/3 3 1/3 4 2/3 5 1/2 6 1/3 7 1/2 8 2/3 9 5/12 10 1/2 11 7/12 12 1/3 13 7/12 14 1/2 15 5/12 16 2/3 17 11/24 18 5/12 19 13/24 20 1/2 For powers-of-two spaces apart, they always differ 2/3 of the time (e.g. f(n) vs. f(n+64)). For any even number of spaces apart, they differ the same proportion of the time as they do half that many spaces apart (e.g. f(n) vs. f(n+6) is the same as f(n) vs. f(n+3)). I don't see any other obvious patterns in the above table, except that the numerators are never more than 1 away from half the denominator, and the denominators are always either 2, or 3 times a (possibly zero) power of 2. Neither the numerators nor the denominators are in OEIS. If I convert all of the above numbers into 24ths, I get: 16 16 8 16 12 8 12 16 10 12 14 8 14 12 10 16 12 10 13 12 Again, no obvious pattern. Is it possible to contrive a sequence for which the first two rows (f(n) vs. f(n+1) and f(n) vs. f(n+2)) both exceed 2/3? If not, what is the limit, and why?

2 1

[math-fun] Recent factorization of RSA-240 & DLP
by Henry Baker 06 Jan '20

06 Jan '20

Re discrete logs: This email describes the recent attack on the discrete log problem. Q: this descrete log solution uses a 'safe' prime; does a 'safe' prime make the DLP harder or easier ?? https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;fd743373.1912 Subject: 795-bit factoring and discrete logarithms From: Emmanuel ThomÃ© <[log in to unmask]> Date: Mon, 2 Dec 2019 13:53:58 +0100 Dear number theorists, We are pleased to announce the factorization of RSA-240, from RSA's challenge list, and the computation of a discrete logarithm of the same size (795 bits): RSA-240 = 124620366781718784065835044608106590434820374651678805754818788883289666801188210855036039570272508747509864768438458621054865537970253930571891217684318286362846948405301614416430468066875699415246993185704183030512549594371372159029236099 = 509435952285839914555051023580843714132648382024111473186660296521821206469746700620316443478873837606252372049619334517 * 244624208838318150567813139024002896653802092578931401452041221336558477095178155258218897735030590669041302045908071447 Let p = RSA-240 + 49204 be the first safe prime above RSA-240. We chose as a target the encoding of the sentence "The magic words are still Squeamish Ossifrage" (in reference to the factorization of RSA-129 [1]): target_str="The magic words are still Squeamish Ossifrage" target_hex=`echo -n $target_str | xxd -p -c 256` target_hex=${target_hex^^} target=`echo "ibase=16; $target_hex" | BC_LINE_LENGTH=0 bc` target = 774356626343973985966622216006087686926705588649958206166317147722421706101723470351970238538755049093424997 we have with generator g = 5: log(target) = 92603135928144195363094955331732855502961099191437611616729420475898744562365366788100548099072093487548258752802923326447367244150096121629264809207598195062213366889859186681126928982506005127728321426751244111412371767375547225045851716 which can be checked with 5^926...716 = target mod p. The previous records were RSA-768 (768 bits) in December 2009 [2], and a 768-bit prime discrete logarithm in June 2016 [3]. It is the first time that two records for integer factorization and discrete logarithm are broken together, moreover with the same hardware and software. Both computations were performed with the Number Field Sieve algorithm, using the open-source CADO-NFS software [4]. The sum of the computation time for both records is roughly 4000 core-years, using Intel Xeon Gold 6130 CPUs as a reference (2.1GHz). A rough breakdown of the time spent in the main computation steps is as follows. RSA-240 sieving: 800 physical core-years RSA-240 matrix: 100 physical core-years DLP-240 sieving: 2400 physical core-years DLP-240 matrix: 700 physical core-years The computation times above are well below the time that was spent with the previous 768-bit records. To measure how much of this can be attributed to Moore's law, we ran our software on machines that are identical to those cited in the 768-bit DLP computation [3], and reach the conclusion that sieving for our new record size on these old machines would have taken 25% less time than the reported sieving time of the 768-bit DLP computation. Another estimation can be made with the rough complexity ratio given by the L_N(1/3,(64/9)^(1/3)) formula that, up to (1+o(1)) factors in the exponent, is customarily taken as an estimation of the expected hardness increase from one computation to the next. This would suggest that 795-bit computations should be 2.25 times harder than 768-bit computations. Taking this into account, and still using identical hardware, our computation was 3 times faster than the expected time that would have been extrapolated from previous records. The acceleration can be attributed to various algorithmic improvements that were implemented for these computations. The CADO-NFS implementation was also vastly improved. We used computer resources of the Grid'5000 experimental testbed in France (INRIA, CNRS, and partner institutions) [5], of the EXPLOR computing center at UniversitÃÂ© de Lorraine, Nancy, France [6], an allocation of computing hours on the PRACE research infrastructure using resources at the Juelich supercomputing center in Germany [7], as well as computer equipment gifted by Cisco Systems, Inc. to the University of Pennsylvania. More details will be given in a forthcoming scientific publication. Fabrice Boudot, Ãâ°ducation Nationale and UniversitÃÂ© de Limoges, France Pierrick Gaudry, CNRS, Nancy, France Aurore Guillevic, INRIA, Nancy, France Nadia Heninger, University of Pennsylvania and University of California, San Diego, United States Emmanuel ThomÃÂ©, INRIA, Nancy, France Paul Zimmermann, INRIA, Nancy, France [1] https://en.wikipedia.org/wiki/The_Magic_Words_are_Squeamish_Ossifrage [2] https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt [3] https://listserv.nodak.edu/cgi-bin/wa.exe?A2=NMBRTHRY;a0c66b63.1606 [4] http://cado-nfs.gforge.inria.fr/ [5] https://www.grid5000.fr [6] http://explor.univ-lorraine.fr/ [7] http://www.prace-ri.eu/prace-in-a-few-words/ [8] https://caramba.inria.fr/dlp240-rsa240.txt

1 0

[math-fun] Special pythagorean triples
by Mike Speciner 05 Jan '20

05 Jan '20

Someone on quora asked if there are Pythagorean triples of the form (x^2-1)^2 + (y^2-1)^2 = (z^2-1)^2, other than {x,y,z} = {10,13,14} and {265,287,329}. From a probabilistic standpoint it seems unlikely (and verified for z < 2^15), but is there a proof? Of course, without the -1s, there are no solutions--it's just n=4 of FLT.

1 0