November 2002 - mathfun@mailman.xmission.com

[math-fun] Puzzle: Find limiting angle as dimension -> oo
by asimovd＠aol.com 18 Dec '02

18 Dec '02

Let v_n be the vector in R^(n-1) defined as (1/n, 2/n,...,(n-1)/n). Let w_n be the vector in R^(n-1) with the same coordinates in reverse order. Find the limit as n -> oo of the angle between v_n and w_n. (Try this without using numerical approximation or summation-of-powers formulae.) Is there a simple geometric reason for the answer? I don't know. --Dan

4 3

[math-fun] Maximum orbit of an n-bit register with monotonic update rule
by Allan C. Wechsler 06 Dec '02

06 Dec '02

Ooh, that subject line is so deliciously jargony. You are probably wondering what the hell I mean. Suppose you have an automaton consisting of an n-bit register, where each bit's next state is a boolean function of the states of all the other bits. We wish to find a rule (that is, an update function for each bit) and an initial state that maximizes the number of states that the automaton traverses before it repeats a state. The obvious maximum of a 2^n-state trajectory is easily achieved by creating a binary counter. Each bit will be on next time in two cases: if it is now on and some bit to its right is off; or if it is now off and all the bits to its right are on. (This is just the standard carry rule, "flattened" to a boolean function of the present bit values.) But note that this logic is required to take explicit notice that certain bits are off. Suppose we restrict the logic, and permit only monotonic boolean functions? We now expect that the 2^n maximum cannot be achieved, in general. We can still implement an n-bit counter with monotonic update rules, but it takes 2n actual bits. So a lower bound of the maximum achievable orbit of such an automaton is 2^[n/2]. Can anyone tighten these lower and upper bounds of 2^[n/2] and 2^n? -A

7 11

[math-fun] Square (& other) chains and necklaces.
by Richard Guy 05 Dec '02

05 Dec '02

I recently mentioned a problem of finding chains and necklaces in which adjacent links add to a square (or other things). Such problems can be restated as: Draw a graph having the numbers from 1 to n as vertices and an edge between any pair of vertices whose labels add to a square (or whatever). Is there a Hamilton path (circuit) in the graph? For example (requested by at least one listener), n = 32. 28 8 1 15 10 21 26 4 23 32 2 17 14 19 22 30 27 6 9 3 16 13 20 12 29 24 7 25 11 5 31 18 This can be upped to 33 by inserting ... 9 16 33 31 18 7 29 20 5 11 ... so we now have chains for n = 15 16 17 31 32 33 34 35 ... (and no smaller others??). This (and 32 33 ... for necklaces) seem to be in too much of an inchoate state for acceptance as sequences for OEIS ?? Finding Hamilton paths is NP-hard in general, but those of us who don't know about such things can often find them in particular cases. Any offers for contributions to knowledge, or references to existing knowledge that Ed Pegg hasn't told me about? R.

8 16

Re: [math-fun] Maximum orbit of an n-bit register with monotonic update rule
by Henry Baker 30 Nov '02

30 Nov '02

I don't know if this is relevant, but so-called 'Grey codes' have the property that they change only 1 bit for each 'increment'. I seem to recall that Grey codes can count through all 2^N states, although not in the usual order. Grey codes have another type of 'monotonic' property -- that, since only one bit changes on each increment, you don't need a clock to know when to sample the output of a 'counter' -- the change in any bit means that the output is available and stable. So these codes are 'self-clocking'.

2 1

Re: [math-fun] Puzzle: Find limiting angle as dimension -> oo
by clear.net.nz 29 Nov '02

29 Nov '02

I wrote, too late at night: > the dot product of the two vectors for n=12 (well, to within a power of 2): That should be n=13, and it's over n^2, not 2^n. -- Mike Stay staym(a)clear.net.nz

2 2

Re: [math-fun] combinatori(c)al
by asimovd＠aol.com 29 Nov '02

29 Nov '02

<< Which of the spellings is correct/usual, the one with or without the 'c'? At least in the U.S., one sees only "combinatorial" -- without the "c". P.S. A small request -- could you please sign your math-fun messages with your name, at least your first name? It would seem more friendly this way. Regards, Dan Asimov

1 0

[math-fun] combinatori(c)al
by Joerg Arndt 29 Nov '02

29 Nov '02

Which of the spellings is correct/usual, the one with or without the 'c'? -- p=2^q-1 prime <== q>2, cosh(2^(q-2)*log(2+sqrt(3)))%p=0 Life is hard and then you die.

1 0

Re: [math-fun] Puzzle: Find limiting angle as dimension -> oo
by Mike Stay 29 Nov '02

29 Nov '02

asimovd(a)aol.com wrote: > << A partridge in a pear tree? > > I have to cry fowl. The puzzle was posted before Xgiving, so would not have a > Xmas reference. > > << > Let v_n be the vector in R^(n-1) defined as (1/n, 2/n,...,(n-1)/n). > Let w_n be the vector in R^(n-1) with the same coordinates in reverse order. > Find the limit as n -> oo of the angle between v_n and w_n. > (Try this without using numerical approximation or summation-of-powers > formulae.) > >> I was referring to the number of gifts in the song, which matched the dot product of the two vectors for n=12 (well, to within a power of 2): 1*12 partridges 2*11 turtle doves 3*10 french hens 4*9 calling birds 5*8 gold rings 6*7 geese 7*6 swans 8*5 maids 9*4 ladies 10*3 lords 11*2 pipers 12*1 drummers -- Mike Stay staym(a)datawest.net

1 0

Re: [math-fun] Puzzle: Find limiting angle as dimension -> oo
by asimovd＠aol.com 29 Nov '02

29 Nov '02

<< A partridge in a pear tree? I have to cry fowl. The puzzle was posted before Xgiving, so would not have a Xmas reference. Incidentally, when I wrote << Let v_n be the vector in R^(n-1) defined as (1/n, 2/n,...,(n-1)/n). Let w_n be the vector in R^(n-1) with the same coordinates in reverse order. Find the limit as n -> oo of the angle between v_n and w_n. (Try this without using numerical approximation or summation-of-powers formulae.) >> I didn't mean to suggest the puzzle is solvable by guesswork. --Dan

1 0

Re: [math-fun] Puzzle: Find limiting angle as dimension -> oo
by asimovd＠aol.com 28 Nov '02

28 Nov '02

<< I'll guess the limit is 90 degrees on the grounds that random vectors in high dimensional spaces tend to be orthogonal. >> Maybe so, but these aren't random! Regards, Dan

2 1