February 2003 - mathfun@mailman.xmission.com

Re: [math-fun] Generalizing strong induction
by asimovd＠aol.com 14 Feb '03

14 Feb '03

<< This is the so-called epsilon induction, and it requires not the Axiom of Choice but the Axiom of Restriction. Suppose that for any set A, if P(a) holds for each a in A, then P(A) holds. Then P(A) holds for all sets. The theories of transfinite induction and well-founded relations both generalize induction; see Thomas Jech's book on set theory. >> I think we'd also have to suppose P(Ø) to conclude P(A) holds for all sets. Otherwise we could prove any P that's always false holds for all sets. --Dan

2 1

Re: [math-fun] Generalizing strong induction
by BobMayans＠aol.com 14 Feb '03

14 Feb '03

This is the so-called epsilon induction, and it requires not the Axiom of Choice but the Axiom of Restriction. Suppose that for any set A, if P(a) holds for each a in A, then P(A) holds. Then P(A) holds for all sets. The theories of transfinite induction and well-founded relations both generalize induction; see Thomas Jech's book on set theory. Bob Mayans

1 0

[math-fun] Prime names
by David Wilson 13 Feb '03

13 Feb '03

The primes in Q(sqrt(-1)) are the Gaussian primes. The primes in Q(sqrt(-3)) are the Eisenstein primes (is this right?) Are there types of primes with names in other imaginary quadratic extensions of Q?

1 0

[math-fun] Surprised, even briefly?
by R. William Gosper 13 Feb '03

13 Feb '03

For how many n in {0,1,...,999999} is n/2 + 1 2 sin(atan(sqrt(7)) n) ----------------------------- sqrt(7) an integer? An odd integer? --rwg

4 3

[math-fun] Generalizing strong induction
by David Wolfe 12 Feb '03

12 Feb '03

OOPS --- I misplaced a parenthesis. So sorry. Corrected version follows. I've growing fond of the following generalization of strong induction: ________________________________________________________________ Let universe U be a partially ordered set with the property that every subset of U has a MINIMAL element. If, forall n, (forall m<n, P(m)) => P(n) <=THIS LINE HAD MISPLACED PARENS then, forall n, P(n) ________________________________________________________________ (Proof requires axiom of choice. U generalizes the well-ordering principle where minimum is replaced by minimal.) I haven't seen this before, but I'm confident that's only because I'm ignorant. Could someone point me references to where induction is stated this way. Or can someone tell me if the property that every subset has a minimal element has a name? Thanks, David

1 0

Re: [math-fun] Ulam(1,2)
by Dan Hoey 12 Feb '03

12 Feb '03

With the first 5 million elements of Ulam(1,2) I've added a new significant figure: The Ulam(1,2) density period is P=21.6015845, plus or minus a few e-7s. It's too far away to be 2765/128, and I don't see anything very attractive in the ISC. Here's a plot of u(n) versus u(n-1), mod P. I took out the bucket elements less than 100, and coded 100-999 and 1000-9999 as 1-9 and a-j. I've noted the common gaps in parentheses, though I may have made some errors with that. Note that the density is blank for residues between 9.0 and -8.0 (or between 0.37 and 0.58 if you prefer normalized mods). \ u(n-1) (mod P) u(n) \-8.0 -4.0 0.0 4.0 8.0 (mod P)\ + + + + + -8.0 + + + + + + + + + + + +(56,34,12) + + + + + + + + (61,39,17) + \\\ + (29,7)+ + + \\\ + \ 3 + \\+ + + \21 + \ 6 + 11 +(44,22) + 133 + 119 + 11 + \\ + 154 + 11b+ +1 + \1 +(83) 266 + 11b + + \2 + \ 287+ 12b + + \4 + 1 2b9 13b + + 2 \6 + 1 3bb +13b + -4.0 + + 47+ + \8+ + + + + 3bb + + + + 13b + + + + + + 9b 1b +3bb 1 + 113b + + bb 2b 2 + 2bb 23+ 113b + + bb +2b 16 + 3bb 55 13b + + bb 1+ 3b 39 + 2bb 66 13b + + 1bb 5 3b 3b+ 3bb +66 39+ (7,27,5) 2bb1b 2b 5b 3bb + 55 36 + \\\ 3cb1c 1b 5b 3b8+ 65 13 + \11 4cb1d 1b +7b 296 55 +11 + \11 5cb1e 7 + 8b 164 55 + 0.0 ++++++++\11++6cb+f+++5+++7b+++++142+++55++++++ + \ \+16bb g 2 7c + 21 54 + + \11 16bb h + 7b + 53+ + \11 17bb h + 7b + 33 + \32 17bb h+ 7b + 21 + 1 +\32 17b8 i 6b+ +11 + 2 + 142 27b7+i 7b + \\ + 2 + 31 27b6 h 6b (37,15) + 13 + 12 16b5 h +5b + + 24+ 1 15b4 h + 59 + 4.0 + + + + + +25 + + + + \594 g+ + + +48 + + + + + + 25 +\473 g + 26 + + +34 + \473 g + 25 + + + 35 + \462 f + 14 + + + 24 + \352 e+ 13 + + + 23 + \341 e \2+ + + 11 + \22 d \1 + + \\ + \1 d \\ + + (30,8)+ \ d (20,42) + + + \ c + 8.0 + + + + + + + + + + + + + + + + \ c+ + + + + \ b \ 5 \\\\ \ (69,47,25,3,2) There definitely seems to be more going on than just a density attractor near 0 mod P--why are the the dense areas not centered in the basin? I'm considering a try of this with u(n) versus u(a(n)), where u(n) = u(a(n)) + u(b(n)) is the canonical decomposition. (I suppose a(n) < b(n), but I wonder if sometimes the other choice would be better.) By the way, I'll warn anyone who wants to work with this period to be numerically careful. Calculating u(n) mod 21.6015845 in floating point gets significantly imprecise when u(n) goes above a few million (Allegro CL on an Ultra). I was about ready to report some curious granularity effects modulo P/256 but fortunately I checked with rational arithmetic first. Things got smooth. Dan

1 0

[math-fun] Ulam number list
by Jud McCranie 12 Feb '03

12 Feb '03

I've sent out my list of the 740,368 Ulam numbers <= 10,000,000 to those who requested it. If I forgot to send one to you, or if you would like a copy, let me know. +---------------------------------------------------------+ | Jud McCranie | | | | Programming Achieved with Structure, Clarity, And Logic | +---------------------------------------------------------+

1 0

Re: [math-fun] Ulam(1,2)
by Dan Hoey 12 Feb '03

12 Feb '03

Oops, let's stick with: Second, letting f(n) = (u(n)/21.6) - floor(u(n)/21.6), for what n in 1000...1999 is .5 <= f(n) < .55? There should only be four or five answers. Dan Hoey

5 8

Re: [math-fun] Ulam(1,2)
by Dan Hoey 12 Feb '03

12 Feb '03

Oops, from Jud McCranie's small gaps data, I my guess about 2 or 3 dying out is wrong. Something more than a sparse space is at work here. Dan

1 0

Re: [math-fun] Ulam(1,2)
by Dan Hoey 12 Feb '03

12 Feb '03

"David Wilson" <davidwwilson(a)attbi.com> writes: > Here's another idea to consider: > Each Ulam number u(n), n >= 2 (zero index) is a unique sum a(n) + > b(n) of distinct earlier Ulam numbers a(n) < b(n). Tabulate a(n) > for 2 <= n <= 2000. There are only 47 distinct values of a(n). It > seems like certain Ulams, starting with 2, 3, 47, 69, etc, are much > more likely to be involved in the sums for subsequent Ulams. Presumably the ones that appear often are the ones in the "sparse space". But something's off with the definition, since your observation would imply that 1, 2, and 3 were all in S, and so the whole sequence would be in S. So I suspect that one of {2,3} will die out as a common addend, and the other will be in the sparse space. Or maybe I need to rejigger the sparse space analysis. If a sparse space can be found that has only finitely many elements of the sequence in it, the sequence can be generated in linear time instead of quadratic. Dan

1 0