Vitanuova for 2001 December 20

Parties

Our party was covered by Wired (and I'm quoted). Thanks to Leonard for finding that.

The EFF holiday party was today, and we went to see Lord of the Rings, which was great. Hooray for parties! Now is the time for all good men to come to the aid of our partygoers.

I had a holiday party of my own last year, the invitations to which which mentioned a lot of holidays, and told when they would happen in 2000 -- in Unix time, not in the Gregorian calendar:

I know that some organizations use "holiday party" as a euphemism for "Christmas party" ("holiday vacations" rarely co-incide with Hanukkah, for example!). We can argue that they are being inconsiderate, or just showing a lack of imagination. For example, there are plenty of holidays this party could commemorate:

Party time = 977022000

Asara b'Tevet (start)          Time = 978570000; error = 1548000 (17.9 days)
Bill of Rights Day             Time = 976867200; error = 154800  (1.7 days)
Boxing Day                     Time = 977817600; error = 795600  (9.2 days)
Charles Babbage's birthday     Time = 977817600; error = 795600  (9.2 days)
Christmas                      Time = 977731200; error = 709200  (8.2 days)
Consualia                      Time = 976867200; error = 154800  (1.7 days)
Eid al-Fitr (if moon sighted)  Time = 977904000; error = 882000  (10.2 days)
Feast of St. Nicholas          Time = 976089600; error = 932400  (10.7 days)
Feast of St. Stephen           Time = 977817600; error = 795600  (9.2 days)
Hanukkah (mean)                Time = 977791800; error = 769800  (8.9 days)
Hanukkah (start)               Time = 977446200; error = 424200  (4.9 days)
Humphrey Davy's birthday       Time = 977040000; error = 18000   (0.2 days)
Isaac Newton's birthday        Time = 977731200; error = 709200  (8.2 days)
John von Neumann's birthday    Time = 977990400; error = 968400  (11.2 days)
Kwanzaa                        Time = 977817600; error = 795600  (9.2 days)
New Year's Day                 Time = 978336000; error = 1314000 (15.2 days)
Opalia                         Time = 977212800; error = 190800  (2.2 days)
Saturnalia (start)             Time = 977040000; error = 18000   (0.2 days)
Sighting of new moon (poss.)   Time = 977878200; error = 856200  (9.9 days)
Sol Invicta                    Time = 977731200; error = 709200  (8.2 days)
Srinivasa Ramanujan's birthday Time = 977472000; error = 450000  (5.2 days)
Third Sunday of Advent         Time = 977040000; error = 18000   (0.2 days)
Tycho Brahe's birthday         Time = 976780800; error = 241200  (2.7 days)
Winter Solstice                Time = 977405820; error = 383820  (4.4 days)
Wyoming Day                    Time = 976435200; error = 586800  (6.7 days)

(I don't think there is going to be a major industry popping up in Asara b'Tevet greeting cards, though. Nor Wyoming Day, I'm afraid.)

The party is actually _on_ St. Adelaide's Day, and one invitee's birthday, but those weren't intentional. It's also Jane Austen's birthday, and Arthur C. Clarke's.

Proof

I'm thinking of going to see Proof on Saturday.

The latest on Zoe-Dan numbers

I was thinking, in the proverbial shower, about the question of which permutation orders are possible over a given number of elements (not just which permutation has the largest order, but which permutations can be attained).

So one question is: what is the least n such that there is a permutation of order q over n elements? (It's easy to see that, if there is a permutation of order q over n elements, there is also a permutation with the same order over n+k elements for any non-negative k. You can just use the identity permutation to avoid permuting the k elements at all, so the old permutation works on a subset of the n+k elements.) I'll call this DZ(q).

Now DZ(q)<=q because there is always a permutation of order q over q elements (the ordinary cyclic permutation in which each element is shifted by one position). This means that, for example, DZ(180180)<=180180. But in fact DZ(180180)<=52 because ZD(52)=180180. But in fact DZ(180180)<52 and in particular DZ(180180)=49 because ZD(49)=ZD(50)=ZD(51)=ZD(52)=180180 and ZD(48)=120120<180180.

The interesting thing about these DZ numbers is that they don't necessarily increase monotonically. For example, DZ(p), for any prime p, necessarily equals p. But DZ(q+1) may be less than DZ(q), especially when q is prime.

DZ(1)=1
DZ(2)=2
DZ(3)=3
DZ(4)=4
DZ(5)=5
DZ(6)=5 [2, 3]
DZ(7)=7
DZ(8)=8
DZ(9)=9
DZ(10)=7 [2, 5]
DZ(11)=11
DZ(12)=7 [3, 4]
DZ(13)=13
DZ(14)=9 [2, 7]
DZ(15)=8 [3, 5]
DZ(16)=16

Another interesting result is that DZ(p^n)=p^n where p is prime (but never when p is not prime).

I realized that you can calculate DZ(q) in a straightforward way by calculating the prime factorization of q, combining like terms (e.g. 8 instead of 2*2*2, or 49 instead of 7*7), and then adding. Can you see why?

Using this method, the factorization of 180180 is 4*9*5*7*11*13, and the sum of those factors is 4+9+5+7+11+13=49, which is, in fact, DZ(180180). By contrast, both 180179 and 180181 are prime -- twin primes. So both have DZ values much greater than 49.

The DZ sequence turns out to be sequence A008475 at Sloane's Encyclopedia.

To phrase this in terms of card shuffling, if you want to find a shuffle which requires q repetitions in order to restore the original order of a deck, the deck must have at least DZ(q) cards in it.

What is the relationship between the DZ and ZD sequences? Are DZ numbers a more efficient way of calculating ZD numbers?