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

RE: [math-fun] Re: math-fun Digest, Vol 17, Issue 9
by Schroeppel, Richard 14 Jul '04

14 Jul '04

This uses quite a bit of storage. It would probably qualify as the standard "dynamic programming" approach. Rich -----Original Message----- From: Phil Carmody [mailto:thefatphil@yahoo.co.uk] Sent: Wednesday, July 14, 2004 2:41 PM To: math-fun(a)mailman.xmission.com Subject: [math-fun] Re: math-fun Digest, Vol 17, Issue 9 From: Marc LeBrun <mlb(a)fxpt.com> > Subject: Re: [math-fun] Re: math-fun Digest, Vol 17, Issue 8 > >=Phil Carmody > > Surely the easiest algorithm would be Dijkstra's? > > I'm not sure; which algorithm of Dijkstra's do you refer to? Pretend your unit and your radical sqrt(t) are logs of some numbers n1 and n2. You want therefore to enumerate in order what you consider a.log(n1)+b.log(n2). Or log(n1^a.n2^b). This is easy to do if enumerating n1^a.n2^b in order is easy to do. Now /if/ {n1,n2} were {2,3} then you'd be enumerating 3-smooth numbers. Which is where Dijkstra comes in, as he has an algorithm for enumerating smooth numbers in order. Best of all, it really doesn't care what the 'primes' are, and therefore it works equally well with {2,3} as it does with {e,exp(sqrt(t))}. And it also doesn't care whether you calculate the smooth numbers by multiplication, or their logs by addition. So you can fall back into {1,sqrt(t)}-space, where you were originally looking. The algorithm is to assume you have a list in order, and have 2 pointers back into the list which tell you which are the least terms that when 1 and sqrt(t) are added to them yield numbers larger than the head of the list. Chose the one that yields the smaller result. Insert that result at the head, and step the pointer forward by one. Your assumption is preserved. Repeat. Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

1 0

[math-fun] Re: math-fun Digest, Vol 17, Issue 9
by Phil Carmody 14 Jul '04

14 Jul '04

From: Marc LeBrun <mlb(a)fxpt.com> > Subject: Re: [math-fun] Re: math-fun Digest, Vol 17, Issue 8 > >=Phil Carmody > > Surely the easiest algorithm would be Dijkstra's? > > I'm not sure; which algorithm of Dijkstra's do you refer to? Pretend your unit and your radical sqrt(t) are logs of some numbers n1 and n2. You want therefore to enumerate in order what you consider a.log(n1)+b.log(n2). Or log(n1^a.n2^b). This is easy to do if enumerating n1^a.n2^b in order is easy to do. Now /if/ {n1,n2} were {2,3} then you'd be enumerating 3-smooth numbers. Which is where Dijkstra comes in, as he has an algorithm for enumerating smooth numbers in order. Best of all, it really doesn't care what the 'primes' are, and therefore it works equally well with {2,3} as it does with {e,exp(sqrt(t))}. And it also doesn't care whether you calculate the smooth numbers by multiplication, or their logs by addition. So you can fall back into {1,sqrt(t)}-space, where you were originally looking. The algorithm is to assume you have a list in order, and have 2 pointers back into the list which tell you which are the least terms that when 1 and sqrt(t) are added to them yield numbers larger than the head of the list. Chose the one that yields the smaller result. Insert that result at the head, and step the pointer forward by one. Your assumption is preserved. Repeat. Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail

1 0

RE: [math-fun] perfect squares
by Schroeppel, Richard 14 Jul '04

14 Jul '04

I think DTs formula below isn't quite right; taking each clause as a 50:50 coin flip, the conjunctions are 1/8 true, and the disjunction only 1/4, while I'd expect 50%. Looking at the last couple of lines of MLBs listing of a+bsqrt2 in order, there seem to be 2 steps: add either -7+5sqrt2 or 3-2sqrt2 to the current number. Presumably, the good algorithm will have three or four candidate steps, to be tried in order, and the first step that keeps all the coordinates non-negative is accepted. Messy details to fill in: the rules for using the continued fraction expansion to create the step list, when to introduce new steps and discard old ones, and the appropriate generalization to 3D. Rich -----Original Message----- From: Marc LeBrun [mailto:mlb@fxpt.com] Sent: Monday, July 12, 2004 10:34 AM To: math-fun Subject: Re: [math-fun] perfect squares >=Dylan Thurston > What's wrong with > (p-r > 0 && q-s > 0 && (p-r)^2 < k*(q-s)^2) || > (p-r < 0 && q-s < 0 && (p-r)^2 > k*(q-s)^2) > ? [As before, x = sqrt(k)] Nothing's wrong, but is there any "good" reason for why it's so complicated? By comparison, p/q < r/s is much simpler. The forms p+qx seem in some sense "morally equivalent" to p/q (for example they "induce" the reals similarly). Square testing, simple ordering, whatever: p+qx always seems to get "casey". >=Marc LeBrun > Heck, I'd even pay $50 for an easy way to generate a+bx in > increasing order for a,b >=0 (if you think you have one contact me > to negotiate the definition of "easy"<;-). >=Dylan Thurston > Err, it is easy once you have the continued fraction expansion, right? > Is the issue getting the continued fraction expansion? No, getting a CF is of course "solved". For example say k=2 so it's 1,2,2,2,... Maybe I've just been dense on seeing how to use that to nicely generate the a+bx. If you can tell me a truly easy way, then you've made an easy $50! "Easy" would be something like the so-called "BRM" raster line drawing algorithm, where you step directly to the next a,b without maintaining a whole bunch of state. (The best I've got so far maintains a sorted list of all a+bx with the same floor). Even funner would be directly computing the Nth a,b. Or, the number below some C+Dx. Here's the ordered forty-four k=2 pairs for a+bx < 10, then their a and b components: 0,0 1,0 0,1 2,0 1,1 0,2 3,0 2,1 1,2 4,0 0,3 3,1 2,2 5,0 1,3 4,1 0,4 3,2 6,0 2,3 5,1 1,4 4,2 7,0 0,5 3,3 6,1 2,4 5,2 8,0 1,5 4,3 7,1 0,6 3,4 6,2 9,0 2,5 5,3 8,1 1,6 4,4 7,2 0,7 0 1 0 2 1 0 3 2 1 4 0 3 2 5 1 4 0 3 6 2 5 1 4 7 0 3 6 2 5 8 1 4 7 0 3 6 9 2 5 8 1 4 7 0 0 0 1 0 1 2 0 1 2 0 3 1 2 0 3 1 4 2 0 3 1 4 2 0 5 3 1 4 2 0 5 3 1 6 4 2 0 5 3 1 6 4 2 7 _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

5 4

[math-fun] polygonal sets of numbers
by Edwin Clark 13 Jul '04

13 Jul '04

A friend of mine is seeking a name for a set (or multiset) of numbers that has the property (*) every number in the set is no larger than the sum of the other numbers in the set. It is easy to see that these numbers (assumed real) are those that arise as the lengths of a (possibly degenerate) polygon. I know that polygonal numbers sometimes refer to triangular, square, pentagonal,..., integers. But we cannot think of a better name for a set or multiset satisfying (*). Hoping to find something in the OEIS: I wrote a program to compute for positive integer n the number of non-empty subsets of {1,2,...,n} satisfying (*) and obtained the following sequence for n from 3 to 14. 1, 4, 13, 35, 85, 194, 425, 904, 1885, 3878, 7904, 16008 This is not in the OEIS. However, the sequence a where a(n) is the number of 3-element subsets of {1,...,n} satisfying (*) is in the OEIS as http://www.research.att.com/projects/OEIS?Anum=A002623 We welcome comments. --Edwin

3 3

[math-fun] Re Dictatorial Sets?
by N. J. A. Sloane 13 Jul '04

13 Jul '04

Edwin said: Thinking of John McCarthy's suggestion, I just submitted the following sequence to the OEIS 1, 3, 6, 11, 18, 28, 42, 61, 86, 119, 162, 217, 287, 375 The nth term is the number of subsets S of {1,2,...,n} which contain a number that is greater than the sum of the other numbers in S. Perhaps someone can find a nice formula for the nth term. Me: Consider the sequence %I A000009 M0281 N0100 %S A000009 1,1,1,2,2,3,4,5,6,8,10,12,15,18,22,27,32,38,46,54,64,76,89,104,122,142, %T A000009 165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,1260, %U A000009 1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718 %N A000009 Expansion of Product (1 + x^m), m=1..inf; number of partitions of n into distinct parts; number of partitions of n into odd parts. ... Take partial sums: %I A036469 %S A036469 0,1,2,3,5,7,10,14,19,25,33,43,55,70,88,110,137,169,207,253,307,371, %T A036469 447,536,640,762,904,1069,1261,1483,1739,2035,2375,2765,3213,3725, %U A036469 4310,4978,5738,6602,7584,8697,9957,11383,12993,14809,16857,19161 %N A036469 Partial sums of A000009 (partitions into distinct parts). ... Take partial sums again: 0, 1, 3, 6, 11, 18, 28, 42, 61, 86, 119, 162, 217, 287, 375, 485, 622, 791, 998, 1251, 1558, 1929, ... (Thanks to Superseeker). Proof? NJAS

1 0

[math-fun] Re: math-fun Digest, Vol 17, Issue 8
by Phil Carmody 13 Jul '04

13 Jul '04

> > > BTW I've shared RCS's interesting experience of the surprising messiness > of > > > such algorithms, such as determining whether p+qx < r+sx for signed > p,q,r,s > > > using only integer operations. Heck, I'd even pay $50 for an easy way to > > > > generate a+bx in increasing order for a,b >=0 (if you think you have one > > > contact me to negotiate the definition of "easy"<;-). > > > > Fool's errand, if I understand correctly. [SNIP foolishness] > I think you missed the constraint 'a,b >= 0'. That I did. Ooops. Surely the easiest algorithm would be Dijkstra's? Very quick, very easy, and not requiring anything more than integer maths if you're paranoid about roundoff errors or are very tight on space. Your "same floor" algorithm may very well nearly be Dijkstra's already though. Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________ Do you Yahoo!? Yahoo! Mail - You care about security. So do we. http://promotions.yahoo.com/new_mail

2 1

[math-fun] sets of numbers with no 3 in arithmetic progression
by Schroeppel, Richard 13 Jul '04

13 Jul '04

I was revisiting an old problem: Find the size of the largest subset of the numbers [1...N] which doesn't contain a 3-term arithmetic progression. I calculated the first few values and did a lookup in the sequence database: ID Number: A003002 (Formerly M0275) URL: http://www.research.att.com/projects/OEIS?Anum=A003002 Sequence: 1,2,2,3,4,4,4,4,5,5,6,6,7,8,8,8,8,8,8,9,9,9,9,10,10,11,11, 11,11,12,12,13,13,13,13,14,14,14,14,15,16,16,16,16,16,16,16, 16,16,16,17,17,17 Name: Number of 3-free sequences. References S. S. Wagstaff, Jr., On k-free sequences of integers, Math. Comp., 26 (1972), 767-771. Author(s): njas (My hand data goes through the first "9", at N=20. Enough terms match that I'm guessing the "Name" is not quite right.) There's a simple construction that gives a set of size 2^K for N = (3^K+1)/2. A kind of Cantor Set picture: xx_xx____xx_xx_____________xx_xx____xx_xx ... This gives sizes around N^(log2/log3), or N^.63... . I believe Erdos showed N^(1-eps) is the true answer, but haven't seen the paper. If nothing more has been done since 1972, the problem should be ripe for new computing efforts, even if no new algorithms exist. larger relevance: If we could show size < N/logN, we'd have a simple proof that primes have infinitely many 3-term APs. A harder theorem (K-term APs) was recently proved, but it was a major work. Rich

1 0

Re: [math-fun] perfect squares
by Marc LeBrun 12 Jul '04

12 Jul '04

>=Bill & Rosemary Cordwell > Is there an easy way to tell when a + b*sqrt(k) is a perfect square in the > extension field Q(sqrt(k))? [...] > I'm particularly interested in when a, b, k are integers... For some value of "easy": With JHC's x=sqrt k, if a+bx = (c+dx)^2 then b=2cd, so first off b must be even, and then you could run through factorizations to see if any give you the right value of a=cc+kdd. Or maybe you could do something by implementing Newton's method in Q(x)? BTW I've shared RCS's interesting experience of the surprising messiness of such algorithms, such as determining whether p+qx < r+sx for signed p,q,r,s using only integer operations. Heck, I'd even pay $50 for an easy way to generate a+bx in increasing order for a,b >=0 (if you think you have one contact me to negotiate the definition of "easy"<;-).

3 3

Re: [math-fun] perfect squares
by Phil Carmody 12 Jul '04

12 Jul '04

--- math-fun-request(a)mailman.xmission.com wrote: > From: Marc LeBrun <mlb(a)fxpt.com> > Subject: Re: [math-fun] perfect squares [snip] > BTW I've shared RCS's interesting experience of the surprising messiness of > such algorithms, such as determining whether p+qx < r+sx for signed p,q,r,s > using only integer operations. Heck, I'd even pay $50 for an easy way to > generate a+bx in increasing order for a,b >=0 (if you think you have one > contact me to negotiate the definition of "easy"<;-). Fool's errand, if I understand correctly. For any terms p+qx < r+sx, there exists an u s.t. frac(qx) < frac(ux) < frac(sx) And therefore there exists a t, s.t. p+qx < t+ux < r+sx. (p,q,r,s,t,u integers, x irrational) To lift from mathworld: <<< A consequence of Weyl's criterion is that the sequence {frac(nx)} is dense and equidistributed in the interval [0,1) for irrational x, where n = 1, 2, ... (Finch 2003). ... Finch, S. R. "Powers of 3/2 Modulo One." §2.30.1 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 194-199, 2003. >>> Phil ===== When inserting a CD, hold down shift to stop the AutoRun feature In the Device Manager, disable the SbcpHid device. http://www.cs.princeton.edu/~jhalderm/cd3/ __________________________________ Do you Yahoo!? Yahoo! Mail - 50x more storage than other providers! http://promotions.yahoo.com/new_mail

4 3

[math-fun] Even Jeb Bush is smarter than the NYT
by Eugene Salamin 11 Jul '04

11 Jul '04

Lest anyone be under the illusion that the New York Times has even the slightest degree of credibility in their scientific articles, I quote from the July 7, 2004 issue, page A17. FLORIDA: MATH QUESTION STUMPS JEB BUSH. At a speech to high school students in Orlando, Gov. Jeb Bush was stumped on a math question from the Florida Comprehensive Assessment Test, which he has championed. A student, Luana Marques, 18, posed the question: "What are the angles on a three-four-five triangle?" The governor gave a steely grin. "The angles would be -- if I was going to guess," he said. "Three-four-five, Three-four-five. I don't know, 125, 90, and whatever remains on 180?" Ms. Marques had the correct answer: 30, 60, 90. "The fact that a 51-year old man can't answer a question is not really relevant," Mr. Bush, a Republican, said. "You're still going to have to take the FCAT and you're still going to have to pass it in order to get a high school degree." (AP) (So blame the AP for this one.) Gene __________________________________ Do you Yahoo!? Yahoo! Mail is new and improved - Check it out! http://promotions.yahoo.com/new_mail

12 14