January 2020 - mathfun@mailman.xmission.com

[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

[math-fun] Not about primes
by Keith F. Lynch 05 Jan '20

05 Jan '20

I looked at the first million primes, excluding 2 and 3, to see how often a prime that's 1 mod 4 is followed by a prime that's 3 mod 4, and vice versa, as compared with the number of primes that are followed by another prime of the same 4-remainder. I noticed that there's a significant bias. A changed 4-remainder happens 281288 times in each direction. An unchanged four-remainder happens 218510 (1->3) and 218913 (3->1) times. So the total number of changes is 562576, which is well over the expected 499999.5. Next I checked how many changes there are between a prime and the prime *two* positions later, e.g. from 5 to 11, 7 to 13, or 11 to 17. Given that the changes between consecutive primes are unexpectedly high, I thought that changes between primes 2 positions apart would have to be low. The closer the sequence is to purely alternating, 1,3,1,3,1,3,..., the closer the second changes would have to be from unchanging, 1,1,1,1,1,... and 3,3,3,3,3,.... But that's not what I saw. The second changes are also well above half a million: 511084. Likewise with the third changes: 505466. And the fourth, fifth, etc. Not until the *29th* changes, i.e. whether a prime has the same 4-remainder as the prime 29 positions after it, is there a number of changes that is less than half a million, 499209. (Note that there are one-million-minus-n nth changes, e.g. 999971 29th changes, of which half, 499985.5 would by chance be different. Also note that if there's a bias, e.g. more primes 3 mod 4 than 1 mod 4, that ought to *reduce* the number of changes between primes n places different, for all n. In the limit, if all primes were 3 mod 4, there would be zero differences for every n.) I'm confused as to how this is possible. Given a long sequence containing just two numbers, e.g. the first million digits of pi in binary, if adjacent terms are less likely to be identical than chance would predict, how can the terms two apart also be less likely to be identical than chance? And just how large can these biases be? Is a million-term sequence possible in which there are 900000 differences between adjacent terms and 800000 differences between terms two places apart? If not, just how large can those numbers be, and how would one design a sequence to maximize them? Maybe it has something to do with Fourier transforms? Would the Thue-Morse sequence be an interesting example? As my subject line says, this is no longer about primes, but about changes in two-valued sequences in general.

3 3

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

04 Jan '20

I wrote, about the Thue-Morse sequence: > 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: ... I have now extended my table to 200 (f(n) vs. f(n+200)). I can easily push it much farther if anyone is interested. I list only the odd numbers, since for an even number the value is always the same as that of half that even number. So it's 2/3 for all powers of 2, 1/3 for all numbers that are 3 times a power of 2, 1/2 for all numbers that are 5 times a power of 2, etc. 1: 2/3 3: 1/3 5: 1/2 7: 1/2 9: 5/12 11: 7/12 13: 7/12 15: 5/12 17: 11/24 19: 13/24 21: 11/24 23: 13/24 25: 13/24 27: 11/24 29: 13/24 31: 11/24 33: 7/16 35: 9/16 37: 25/48 39: 23/48 41: 25/48 43: 23/48 45: 7/16 47: 9/16 49: 9/16 51: 7/16 53: 23/48 55: 25/48 57: 23/48 59: 25/48 61: 9/16 63: 7/16 65: 43/96 67: 53/96 69: 47/96 71: 49/96 73: 17/32 75: 15/32 77: 47/96 79: 49/96 81: 47/96 83: 49/96 85: 17/32 87: 15/32 89: 47/96 91: 49/96 93: 43/96 95: 53/96 97: 53/96 99: 43/96 101: 49/96 103: 47/96 105: 15/32 107: 17/32 109: 49/96 111: 47/96 113: 49/96 115: 47/96 117: 15/32 119: 17/32 121: 49/96 123: 47/96 125: 53/96 127: 43/96 129: 85/192 131: 107/192 133: 97/192 135: 95/192 137: 101/192 139: 91/192 141: 89/192 143: 103/192 145: 101/192 147: 91/192 149: 97/192 151: 95/192 153: 31/64 155: 33/64 157: 97/192 159: 95/192 161: 97/192 163: 95/192 165: 31/64 167: 33/64 169: 97/192 171: 95/192 173: 101/192 175: 91/192 177: 89/192 179: 103/192 181: 101/192 183: 91/192 185: 97/192 187: 95/192 189: 85/192 191: 107/192 193: 107/192 195: 85/192 197: 95/192 199: 97/192 > 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, Violated starting at 65, for which the proportion that differ is 43/96. > and the denominators are always either 2, or 3 times a (possibly > zero) power of 2. Still true. So, can anyone figure out the pattern? The nth term of the Thue-Morse sequence equals the parity of the number of 1-bits in the binary expression for n. For instance ten in binary is 1010, which has an even number of 1-bits, so the tenth term of the Thue-Morse sequence is zero. There's a similar sequence in which the nth term of the sequence equals the parity of the number of 1-bits in the *negabinary* (base minus two) expression for n; perhaps I'll try that sequence next. Everyone, please feel free to suggest other binary sequences to try. By binary I don't necessarily mean that all terms are 0 or 1, but that the terms only take two values.

1 0

Re: [math-fun] There are other kinds of corner reflector?
by Henry Baker 04 Jan '20

04 Jan '20

There are verified incidents of car engines cutting out when driving past certain U.S. DoD facilities. This hasn't been happening so much recently, so either DoD has stopped their high power operations near the ground surrounding these bases, or modern cars are more resistant. The U.S. DoD has recently resurrected these types of operations to disable drones (at least consumer-grade drones), although DoD must still be doing this somewhat higher than ground level to not harm personnel and ground vehicles. I doubt that corner reflectors will harm the radar itself, but might harm an unprotected human operator nearby. At 01:10 PM 1/4/2020, Mike Stay wrote: >Here's a picture taken by a guy holding a flashbulb and walking >towards a radar dish. It's a couple of feet away. No info on how >much power the radar was using. > >https://books.google.com/books?id=pWAzAQAAMAAJ&pg=PA138&lpg=PA138&dq=radar+… > >Here are power ratings for different kinds of radar and the hazards they pose: >https://www.who.int/peh-emf/publications/facts/fs226/en/ > >Apparently the danger of radar beams either heating metal hot enough >to ignite fuel vapors or to cause sparking is large enough that there >are regulations about it: > >https://books.google.com/books?id=yv1Zz_CGhU8C&pg=SA2-PA14&lpg=SA2-PA14&dq=… > >On Sat, Jan 4, 2020 at 10:17 AM Mike Stay <metaweta(a)gmail.com> wrote: >> On Sat, Jan 4, 2020 at 7:22 AM hbaker1 <hbaker1(a)pipeline.com> wrote: >> > Have you ever put metal into a microwave? >> >> Sure, but that's a small sealed metal box. Was he standing directly >> in front of the radar emitter? >> >> > Back in the 1950's, some of the soldiers stationed on the "DEW Line" >> > kept themselves warm by standing in front of the radars. Bad idea, but >> > Raytheon then converted the idea into the microwave oven... >> >> Reminds me of this old hoax from 20 years ago: http://www.nmsr.org/darwiner.htm >> >> > (One of my first jobs was helping the Public Health Service find >> > leaking microwave ovens which caused eye cataracts in restaurants where >> > they were used.) >> >> Yikes! >> >> Also see https://en.wikipedia.org/wiki/Peryton_(astronomy) >> -- >> Mike Stay - metaweta(a)gmail.com >> http://math.ucr.edu/~mike >> https://reperiendi.wordpress.com >-- >Mike Stay - metaweta(a)gmail.com >http://math.ucr.edu/~mike >https://reperiendi.wordpress.com

1 0

Re: [math-fun] There are other kinds of corner reflector?
by hbaker1 04 Jan '20

04 Jan '20

Have you ever put metal into a microwave? Back in the 1950's, some of the soldiers stationed on the "DEW Line" kept themselves warm by standing in front of the radars. Bad idea, but Raytheon then converted the idea into the microwave oven... (One of my first jobs was helping the Public Health Service find leaking microwave ovens which caused eye cataracts in restaurants where they were used.) -----Original Message----- >From: Mike Stay <metaweta(a)gmail.com> >Sent: Jan 2, 2020 2:21 PM >To: math-fun <math-fun(a)mailman.xmission.com> >Subject: Re: [math-fun] There are other kinds of corner reflector? > >On Thu, Jan 2, 2020 at 3:04 PM Bill Gosper <billgosper(a)gmail.com> wrote: >> loud. In the 60s, I >> worked at a naval air station where a visiting photographer was severely burned when >> all the flashbulbs >> <https://upload.wikimedia.org/wikipedia/commons/f/fa/Brownie_Hawkeye_with_Fl…> >> went off in his pockets. (That sparkly stuff is "magnesium wool"!)) > >The radar caused the flashes to go off? Wow! > >I'm not quite old enough to remember single-flash bulbs, though they >must have still been in use when I was a kid, but I do remember >flashcubes: >https://tinyurl.com/rldhhgv >-- >Mike Stay - metaweta(a)gmail.com >http://math.ucr.edu/~mike >https://reperiendi.wordpress.com

3 3

Re: [math-fun] Iterate, stop, restart
by Keith F. Lynch 04 Jan '20

04 Jan '20

Eric Angelini <eric.angelini(a)skynet.be> wrote: > Start with n, then let n=2n and iterate. When the string n > reappears, stop the iterations and restart the procedure with > the smallest integer not yet in S. > Question: > is there a new n that will restart S at some point and _not_ lead to > a new stop? No. Since no non-zero power of 2 equals a power of 10, i.e. log(10)/log(2) is irrational, any sequence in which each term is the double of the previous will start with every decimal number infinitely many times. Powers of 2 (or powers of 2 times a constant) are dense on the interval created by prepending every integer with a decimal point (.1, .2, .3, ... .8, .9, .10, .11, ...). For instance there's a power of 2 that begins with 2020: 2^4180. The American independence year, 1776, starts 2^2087, and the Belgian independence year, 1830, starts 2^1323. See A018856. You won't find a power of 2 that begins with all the decimal digits of pi, but you can always find one that begins with the first n decimal digits of pi: 5, 98, 872, 10871, 55046, etc. (not in OEIS).

1 0