May 2016 - mathfun@mailman.xmission.com

[math-fun] Squarefribonacci sequences
by James Propp 05 May '16

05 May '16

Must every sequence of squarefree positive integers satisfying the recurrence f(n) = SquarefreePart(f(n-1)+f(n-2)) eventually enter the cycle 1, 2, 3, 5, 2, 7, 1, 2, 3, 5, 2, 7, ...? E.g., 7, 4, 11, 15, 26, 41, 67, 3, 70, 73, 143, 6, 149, 155, 19, 174, 193, 367, 35, 402, 437, 839, 319, 1158, 1477, 2635, 257, 723, 5, 182, 187, 41, 57, 2, 59, 61, 30, 91, 1, 23, 6, 29, 35, 1, 1, 2, 3, 5, 2, 7, ... (This probably isn't new, but you never know.) Jim

6 9

[math-fun] Nyquist sampling
by Henry Baker 05 May '16

05 May '16

FYI -- Shouldn't we use at least 6 data points for this particular Triple Crown? :-) https://www.washingtonpost.com/news/fancy-stats/wp/2016/05/05/why-you-shoul… "The field for the 2016 Kentucky Derby is set and Nyquist, at 3-to-1 odds, is the favorite to win the 142nd running of the roses." https://en.wikipedia.org/wiki/Nyquist_rate

1 0

[math-fun] Yet another irritating elementary geometry puzzle
by Fred Lunnon 04 May '16

04 May '16

I finally wrote up properly all the stuff I've been doing about inspheres and exspheres of a simplex. Finished. Done & dusted. Off my plate. But as I sat down again to start writing up P*nc*l*t's perishin' p*r*sm, an obnoxious inspiration intruded. Why shouldn't a simplex in Euclidean space also sport an ` m-fold' exsphere, tangent to m facets on their exterior side, and to n-m+1 on their interior side, where perhaps m > 1 ? In particular, show (A) That m = 2 is impossible when n = 2 (for a triangle); (B) That m = 2 is impossible when n = 3 (for a tetrahedron); (C) What happens for m = 2 and n = 4 (for a pentatope); (D) What happens for general 0 <= m <= n+1 ? Fred Lunnon

4 10

[math-fun] TRAPPIST-1: three earthlike planets orbit one red dwarf star
by Warren D Smith 03 May '16

03 May '16

TRAPPIST, a 60cm telescope in Chile designed to detect planets round small red dwarfs via the transit method, found a jackpot. The ultracool dwarf star, 2MASS J23062928-0502285, now known as TRAPPIST-1, is thought to be about 80 Jupiter masses (1/13 of the mass of our sun) and about the same diameter as Jupiter; about half the temperature of our sun; about 1/2000 of the luminosity of our sun; and about 40 light years from here. It has 3 planets of size comparable to Earth with orbital periods 1.5 days, 2.4 days, and somewhere between 4 to 79 days. The two inner planets are almost certainly tidally locked with only 1 side exposed to sunlight. They receive about 4 and 2 times the irradiation as Earth and have about same size as Earth. Due to the tidal locking it seems certain the night side will be cold and the day side hot and therefore a large "belt" must exist on its surface with temperatures in the liquid water range. The outer planet's temperature is less clear since its orbit needs to be worked out, but it quite possibly also has temperatures within the liquid water range. The whole TRAPPIST system is miniature compared with our solar system, about 0.1% of its size, indeed is more like Jupiter & its moons in scale. This sort of star is the longest-lived kind of star and I would expect TRAPPIST-1 to have lifetime of about 1500 gigayears as opposed to 10 Gyr for our sun. If there is life on a planet orbiting this class of tiny star, it therefore would enjoy the longest possible time to evolve. http://www.eso.org/public/archives/releases/sciencepapers/eso1615/eso1615a.… -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Sol Golomb
by Victor Miller 02 May '16

02 May '16

I just read that Sol Golomb died yesterday. Very sad. Victor

3 3

Re: [math-fun] Sol Golomb
by Hilarie Orman 02 May '16

02 May '16

Services for Sol Golomb will be held Thursday, May 5, 3:00 pm at Mount Sinai Hollywood Hills, 5950 Forest Lawn Drive, Los Angeles, CA 90068 Directions: http://mountsinaiparks.org/parks/directions/

2 1

Re: [math-fun] Sol Golomb
by Hilarie Orman 02 May '16

02 May '16

USC's president has announced the death, it is, sadly, true. Hilarie

1 0

[math-fun] recognizing an even permutation
by Warren D Smith 01 May '16

01 May '16

Yes, Arndt & Miller both had the same "cycle chasing" idea although Miller made the nice point the extra array of bits can be stored in the sign bits of the f(n) integer array, then reset to "+" afterwards. That runs in O(n) time and O(n) extra bits worth of storage. Also, it can be done in O(n^2) time and O(1) words storage by for(i=1 to n){ find cycle size for i, f(i), f(f(i))... } and then the sum of the cycle (cardinality-1) values, summed over all non-last elements in all cycles, has the same parity as the permutation. (You are the "last" cycle element if the maximum over all elements in your cycle. Keep track of running max.) Also, it can be done in T time and S words storage for any T with n<T<n^2 with T*S=n^2. ["Word" means order log(n) bits.] You find the first S elements of cycles longer than S. Then alter the permutation to shorten that cycle to length S, storing the alteration so can later undo it. In this way in storage<=n/S and time O(n) we shorten all cycles to lengths<=S. Then we do the above algorithm, with runtime<=n*S. Then we unalter the alterations. [There are also other ways to rethink that same algorithm involving use of hash tables for "memoization" instead of perm-alterations, etc; for example in the Arndt/Miller method, do not mark with a bit every guy; instead just mark every Kth guy round a cycle, then you can use K times less storage but each bit-lookup costs K times more. If we pre-choose a random-like function that is 1 a fraction 1/K of the time, and 0 the rest, and only mark bits where magicfunction(n)=1 we can avoid the log(n) storage factor and perhaps still get runtime n*K in some randomized expected sense.] It seems to me it is not possible to determine permutation parity if examine only n-2 entries of the f() array, since the other 2 entries could be crux. So linear time is best possible. However, that lower bound argument may have been too facile. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

3 2

Re: [math-fun] Simple finite group problem
by Keith F. Lynch 01 May '16

01 May '16

I finished my program to find all mutiplicative groups mod N through N=1000, and added the results to OEIS. It's A265165. Apparently nobody is happy with my name, saying that it ought to be reserved for only those groups whose identity element is 1. (That's another sequence which I plan to add as soon as I better understand how to work with OEIS.) I think the name is perfectly descriptive, and that the example makes it clear that I mean *all* such groups. But if people are unhappy, does anyone have any alternative ideas for a short descriptive name? Thanks. Everyone has strengths and weaknesses. One of my weaknesses is graphical user interfaces. I've always found them profoundly unintuitive and difficult to work with. I'm very good at a Unix shell prompt, or in the Emacs editor. In the Lynx browser, I can invoke Emacs in any text-entry box. But apparently I can't log onto OEIS (unlike Wikipedia) with Lynx. And apparently I'm not supposed to discuss a draft OEIS entry except within OEIS, by typing into a text box in a graphical browser, which I find to be about as primitive and difficult to edit as 1960s punched cards. For instance why does it remove all my formatting and paragraph breaks? Also, now that my sequence is no longer in draft, there isn't even a text box for me to reply to the latest "don't reply to this email" emails about the sequence. (Also this weekend I've been trying to get a printer working with my Ubuntu laptop, and have been getting nowhere. I'm so frustrated I'd just as soon write my own printer driver (I've done it before), except that Lexmark doesn't document the necessary internals. I'm sick and tired of getting high-resolution images of frowny face icons in lieu of useful information.) I also have a b file, at http://KeithLynch.net/b265165.txt I've read the OEIS documentation on contributing a b file, but I can't see where it says how to upload it into OEIS. Do I use sftp? That doesn't seem to work. Thanks to N.J.A. Sloane for manually uploading my a file. I'd be glad to upload my b file myself if someone can tell me how it's done. Anyhow, here's a description of the algorithm I use: For every N (modulus), 1 through 1000, I try every I, 1 through N-1, to see if it equals its own square (mod N). If it does, it's an identity element for at least one multiplicative group mod N. For instance for mod 10 the identity elements are 0, 1, 5, and 6. For each I, I try every J, 1 through N-1, to see if repeatedly multiplying J by itself ever gets back to I. If it does, I've found a cyclic group, which consists of the successive powers of J. If it doesn't reach I within N steps, I know it never will, and that there's no group containing both I and J. With each "new" cyclic group, I put the elements in numerical order and add them to the table after making sure it's not a duplicate. After I've found all cyclic groups for that N and that I, I take the union of each pair of them. In general the union of two groups isn't a group, so I complete the new group by including the product of each pair of elements of the union in the group if it wasn't there already. I may have to do that multiple times, as the product of the newly added element with another element may not be in the union. (Apparently, I never have to do it more than twice.) Once the new group is complete, I put its elements in numerical order and add the new group to the the table if it's not a duplicate. I then take the union of each cyclic group with each of these new groups, in the same way. This too I need to do multiple times, until in one such step I find nothing but duplicates. The most times I've had to do it (for N through 1000) is five. I then output the table to what became the a file, http://oeis.org/A265165/a265165.txt (The trivial group with 0 as its element, I don't compute, but just "forcibly" include for every N.) The format of that a file should be obvious: N, I: The elements of the group in numerical order. There are 90754 groups in total. If anyone can find a flaw in that algorithm, speak now or forever hold your peace. It does agree with the groups I computed by brute force (by testing every possible subset to see if it's a group) through N=36. Unfortunately, the brute-force algorithm isn't practical much beyond N=36, which took more than a day. My new algorithm is much faster, taking only ten minutes to get up to N=1000. I could easily push it as far as N=10,000 if anyone is interested. To get the elements of the sequence, I use the following Unix command: grep : a265165.txt | cut -f 1 -d\ | uniq -c > b265165.txt That actually gets me a reverse b sequence. The right two numbers are on each line, but they're in the wrong order. It's easy to fix with Emacs or whatever your preferred editor is. Or if you want the (reverse) b sequence for just the number of groups with 1 as an identity element: grep \ 1: a265165.txt | cut -f 1 -d\ | uniq -c > bwhatever.txt By popular request, I'll also upload my 120-line C program. But not until I've added comments. For good mental exercise, I wrote it entirely without comments.

2 1