- mathfun@mailman.xmission.com - mailman.xmission.com

[math-fun] Re: Marriage theorem generalization
by Thomas Colthurst 27 Jan '05

27 Jan '05

Well, here's a reduction to what is hopefully a well-studied graph theory problem. Add two special sets: S, which contains only the interval [0,0], and E, which contains only [n+1,n+1]. Now make a graph G with a vertex for every interval and an edge between two intervals iff (1) the union of the two intervals is itself an interval and (2) the two intervals come from different sets. Thus, if there were k sets of intervals in the beginning, G is (k+2)-partite graph. The problem now becomes: find a path in G from [0,0] in S to [n+1,n+1] in E that visits each part of G at most once. As I said, I hope this is a well-studied problem, because all I know are bad solutions to it. (For example: starting at [0,0] and continually growing a list of valid paths to each vertex until you grow a valid path to [n+1,n+1].) Speaking of bad solutions, here's an algorithm for your general problem that isn't at all guaranteed to find a solution, but might often do so in practice. Let c(i) be the number of sets that don't contain i in one of the set's subsets. Pick the subset that maximizes sum_{j in subset} c(j)^N for some N >> k, and then recalculate all the c(i) with the picked set removed and c(i)=0 if i was in the picked subset. Repeat. (The exponent is there simply to turn sum into a "soft max" function, and can be replaced with an equivalent ordering on vectorized counts if you like.) -Thomas C

1 0

RE: [math-fun] covering all N with squares (2nd degree polynomialswithinteger coeffs.).
by Daniel Asimov 27 Jan '05

27 Jan '05

What I wrote is nonsense, but what does make sense is the following: Let Q_k(x) = x^2 + kx for all k in Z. Then: S+ = {Q_k(p) : p prime, k = 1,2,3,... } contains for each prime p all multiples of p greater than p^2, S- = {Q(-k)(p) : p prime, k = 1,2,3,...} contains for each prime p all multiples of p less than p^2, and S0 = {Q_0(n) : n = 1,2,3,...} contains all squares. So S- u S0 u S+ = Z. So I'm guessing that Simon wants a family of polynomials { P_k(x) : k = 1,2,3,... } with all coefficients positive integers with { P_k(n) : k = 1,2,3,... and n = 1,2,3,...} = Z+ exactly. -------------------------------------------------------------------------------- Of course, as long as we can use countably many polynomials, for each k we can always design P_k(x) so that P_k(1) = [the least positive integer not contained in the union of {P_j(n) : n = 1,2,3,...} for 1 <= j < k.] But I suppose this would be considered too trivial. --Dan ------------------------------------------------------------------ I wrote: << Let Sq denote {1,4,9,16,...}. But if say for each k in Z, we let P_k(x) = x^2 + kx , then . . . . . . . . . >>

2 1

[math-fun] Marriage theorem generalization
by Michael Kleber 27 Jan '05

27 Jan '05

Suppose you have a collection of sets of integers from the range [1,n]. Then the question "Can you cover all of [1,n] by choosing one integer from each set?" is answered by Hall's Marriage Theorem -- yes, provided any size k subset of [1,n] intersects at least k of the sets in my collection. Moreover it is computationally efficient to make an actual choice of which integer to use from each set, or to list all the possible choice functions: the proof of Hall's is essentially an argument that if you pick one a a time without doing anything stupid, you never need to backtrack. What if instead you start with a collection of sets of *intervals of integers* in [1,n]? I want to know whether it's possible to pick one interval from each set in such a way that their union is all of [1,n]. And if so, I'd like to know the same constructiveness facts: can I find one or all such assignments efficiently? The full generalization, of course, is where you start with a collection of sets of *subsets* of [1,n]. But without thinking about it much at all, it seems overwhelmingly likely to me that this will turn out to be NP-complete. So the question is, does restricting to intervals tame the situation enough to make it feasible? --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

1 0

RE: [math-fun] covering all N with squares (2nd degree polynomials withinteger coeffs.).
by Daniel Asimov 27 Jan '05

27 Jan '05

Simon asks: << Here is the problem. How to cover all N (natural numbers) with simple poynomials of the second degree even with some overlaps. We all know that it is possible to do it with a beatty sequence when 1/a + 1/b = 1, with a,b irrationals. [a*n] and [b*n] covers N with no overlab and no holes. if a = 1/2 + sqrt(5)/2 and b = 0.38196601125 then it works. Of course it is possible to do it with 2 or more ordinary arithmetical progressions. But how to do it with 2nd degree polynomials? Is it possible? For example (a tentative sieve that does not work), n^2 = 1, 4, 9, 16, 25, ... n^2+1 = 2, 5, 10, 17, 26, ... n^2+2 = 3, 6, 11, 18, 27, ... etc does cover many integers but I do not think it does work. It does not matter if there are some overlaps. of course, in the above example, n^2+k at n=1 will eventually reach any number but let's say : can it be done non-trivially? I am just wondering if the problem has a solution. >> I'm not sure I understand just what the question is. Since for any polynomial P(x) over Z of degree > 1 we have density( { P(n) : n = 1,2,3,... } ) = 0, this clearly can't be done with finitely many polynomials. ---------------------------------------------------------------------- Let Sq denote {1,4,9,16,...}. But if say for each k in Z, we let P_k(x) = x^2 + kx , then { P_k(n) : n,k = 1,2,3,... } = Sq + { kn : k,n = 1,2,3,... } then since every positive integer is a square plus a number of the form kn, this is certainly Z (with abundant overlap). So, I'm not sure if I'm understanding the question. --Dan

1 0

[math-fun] covering all N with squares (2nd degree polynomials with integer coeffs.).
by Simon Plouffe 27 Jan '05

27 Jan '05

Hello, the title is a little short and not fully descriptible, Here is the problem. How to cover all N (natural numbers) with simple poynomials of the second degree even with some overlaps. We all know that it is possible to do it with a beatty sequence when 1/a + 1/b = 1, with a,b irrationals. [a*n] and [b*n] covers N with no overlab and no holes. if a = 1/2 + sqrt(5)/2 and b = 0.38196601125 then it works. Of course it is possible to do it with 2 or more ordinary arithmetical progressions. But how to do it with 2nd degree polynomials? Is it possible? For example (a tentative sieve that does not work), n^2 = 1, 4, 9, 16, 25, ... n^2+1 = 2, 5, 10, 17, 26, ... n^2+2 = 3, 6, 11, 18, 27, ... etc does cover many integers but I do not think it does work. It does not matter if there are some overlaps. of course, in the above example, n^2+k at n=1 will eventually reach any number but let's say : can it be done non-trivially? I am just wondering if the problem has a solution. simon plouffe

3 3

[math-fun] Re: Rotor-router article
by James Propp 24 Jan '05

24 Jan '05

If folks are interested in finding out more about the topics discussed in Michael's very nice article, check out http://www.math.wisc.edu/~propp/quasirandom.html and the links contained therein. Jim Propp

1 0

[math-fun] Lots of neat stuff about e^(pi sqrt(n))
by Mike Stay 24 Jan '05

24 Jan '05

http://www.geocities.com/titus_piezas/Ramanujan_a.htm -- Mike Stay staym(a)clear.net.nz http://www.cs.auckland.ac.nz/~msta039

2 1

[math-fun] ~s mor(e)on units
by R. William Gosper 24 Jan '05

24 Jan '05

I hacked my units package to accept descending lists of target units, e.g., (c517) uconv(2*mph+inch/sec,[fps,furlong/fortnight]) 336 furlong (d517) ------------ + 3 fps 11 fortnight so you can have a pretty arbitrary mixed radix: (c520) uconv((furlong+inch)^2,[acres,feet,inch]) 2 2 (d520) inch + 110 feet + 10 acres The function anglicize contains a capricious (and negotiable) set of units lists: (c521) anglicize(13) (d521) bakersdozen (c523) anglicize(1000) (d523) thousand (c525) anglicize(1730) (d525) pair + greatgross (c560) anglicize(halfcrown) (d560) sixpence + 2 shilling (c526) anglicize(guinea-2*farthing) (d526) twopence + pound + ninepence + halfpenny (c535) anglicize(1.0*litre) (d535) 1.0 quart + 1.81388 fluidounce (c536) anglicize(mi^3-floz) 3 3 3 3 (d536) 166 yard + 63 rod + 3 quart + pint + 511 furlong + 10 foot 515 fluidounce 3 + -------------- + 999 chain 77 (c537) anglicize(d536+floz) 3 (d537) mile Now a question: my Webster's Unabridged gives sidereal day : the interval between two successive transits of the March equinox over the upper meridian of a place that is equal to 23 hours, 56 minutes, 4.09 seconds of mean solar time sidereal year : the time in which the earth completes one revolution in its orbit around the sun measured with respect to the fixed stars : 365 days, 6 hours, 9 minutes, and 9.54 seconds of solar time (c553) uconv(siderealyear,[days,hours,minutes,seconds]) 477 seconds (d553) ----------- + 9 minutes + 6 hours + 365 days 50 tropical year : the period occupied by the sun's center in passing from one equinox to the same again and having a mean length of 365 days, 5 hours, 48 minutes, 45.5 seconds (c551) anglicize(tropicalyear) 459747 second (d551) ------------- + 48 minute + 5 hour + 26 fortnight + day 10000 which differs by 10^-8 and is claimed to be better. I would think a sidereal day would be (c556) (1.d0/(1/siderealyear+1/day),%%=anglicize(%%)) 1.0d0 (d556) ------------------ = 4.09965986199637d0 second + 56.0d0 minute 1 1 ------------ + --- siderealyear day + 23.0d0 hour but (c555) (1.d0/(1/tropicalyear+1/day),%%=anglicize(%%)) 1.0d0 (d555) ------------------ = 4.09053820802342d0 second + 56.0d0 minute 1 1 ------------ + --- tropicalyear day + 23.0d0 hour agrees better with Webster. Is this because the March equinox is precessing? If so, what is the name of the interval required for the stars to complete one circle of Polaris? --rwg PS, the difference between the two notions of year (c557) anglicize(siderealyear-tropicalyear) 235653 second (d557) ------------- + 20 minute 10000 is called NECROPSIES of the equinoxes: tidal effects on Earth's nonsphericities hurry the seasons by 20+ minutes each orbit. Presently, the Northern Hemisphere is closer to the Sun in winter. In about (c558) canon(180.*days/d557) (d558) 12710.4 orbits, this ENCOPRESIS will switch this climatic moderation to the Southern Hemisphere, which also enjoys a higher %age of oceans. Go south, young carbophobe. (Sorry if I permuted a few letters, here.-) PPS, What a great language we have; "vulgar establishment" is a celestial term, and "celestial telescope" is a goldfish.

4 5

[math-fun] Numb3rs
by Daniel Asimov 24 Jan '05

24 Jan '05

I'm between TV sets, but would love to be able to (eventually) watch the premiere of this new show, Numb3rs, involving a detective, and his "math genius" brother who helps him solve cases by using math. It's on CBS tonight at 10 pm ET, 7pm PT; after tonight's premiere it will be at the same time on Fridays. If anyone's willing to tape it (or DVD it) and send me a copy, I'd be very grateful, and more than happy to overcompensate you for parts, labor, and postage. Among other things, I'd like to to see if the math is totally, completely bogus -- as in Good Will Hunting -- or not. Tx in advance. --Dan

4 3

[math-fun] Re: A100832: What exactly are amenable numbers?
by Eric Angelini 24 Jan '05

24 Jan '05

Hello seqfans and math-fun, I've just published A101246 in Sloane's OEIS (see below). Could someone calculate for me the last term of the sequence (which, I'm sure, is finite) ? best, E. -------- 1,3,7,605,607,1446,1538,1608,2545,2618,3027,4616,4903, (...) « Insert the first differences between every pair of integers; this new sequence has it's first 10 digits all different one from another ; and so for the next 10 ; and for the next 10, etc. To construct the above sequence, start with 1 and add the smallest available integer which doesn't lead to a contradiction. » Example : 1 3 7 605 607 1446 1538 1608 2545 2618 (seq. A101246) 2 4 598 2 839 92 70 937 73 409 (first differ.) **10*dig**--10-dig--**10*dig**--10-dig--**10-dig** (10 digit boxes)

1 0