October 2005 - mathfun@mailman.xmission.com

[math-fun] basketball shooting problem
by Chris Landauer 25 Oct '05

25 Oct '05

hihi, all - i think the answer is no for any ratio - irrational ones are easy, but it seems that you could easily get fractions smaller and larger than a given a/b c/d < a/b < (c+1)/(d+1) so that the value would never be exact Thane Plambeck asked Say you're shooting baskets and you keep track of your record as you shoot them, for example 0 for 1 1 for 2 1 for 3 1 for 4 1 for 5 2 for 6 etc, you get the idea Someone specifies a "target ratio" (I think it was 80% in the problem statement) and you're told that during the record of shots, the shooter was below the target ratio, but later was better than the target ratio. Is there necessarily a moment at which the shooter must have shot exactly that ratio up to that point? cal again - ok, so i' ve changed my mind - the above inequalities require bc < ad a(d+1) < b(c+1) which are equivalent to 0 < ad - bc < b - a so if b=a-1, there is no solution for c and d - if a and b have a common divisor, it is also a divisor of ad-bc, so we may assume that a and b are relatively prime so i now think that the answer is yes for 80% = 4/5 and any other a/(a+1) fraction, but no for any others more later, cal

1 0

[math-fun] sums of powers note
by Chris Landauer 25 Oct '05

25 Oct '05

hihi, all - ok, i have run the program to find solutions to n = a^2 + b^3 + c^4 + d^5 + e^6 for non-negative n and a, b, c, d, e at least s, for s=2 up to n=336807, for s=1 up to n=100000, and for s=0 (the usual problem statement) up to n=404219 the program prints for each n how many representations there are (and a flag can be set to print them also, but i didn't do that) the program for s=0 took about 48 hours, and the time complexity appears to be roughly quadratic i plotted the growth of the number of solutions, and it appears to be much less than linear, but with very wide variation - i don't really have time to do the data analysis, but i'd be happy to send the output file to anyone who wants it (it is a little over 4MB, or 1.4MB as a gzipped tar file - this is just the s=0 output, which i gather is the most interesting, though the others have very similar shapes) more soon, cal

1 0

Re: [math-fun] Re polyanygons
by dasimov＠earthlink.net 25 Oct '05

25 Oct '05

David writes: << Oh yeah, and all those polyominoes that don't have names are anonymominoes. Anonymominoes? How many Nonnas does your momma know? --Dan

1 0

RE: [math-fun] Re polyanygons
by dasimov＠earthlink.net 24 Oct '05

24 Oct '05

Neil wrote: << I'm adding this to the OEIS, OK? %I A111189 %S A111189 1,2,3,9,20,75 %N A111189 Number of polyanygons with score n. . . . . . . >> Rich gets naming rights, for sure. But before the name for such a thing is carved in stone, I propose calling it a heteromino. --Dan

2 2

[math-fun] another Stirling's tweak
by R. William Gosper 23 Oct '05

23 Oct '05

At 20:50:54 Mon, Dec 8 1997, I gave an improved Sirling's approximation - z - y z 2 1 z! ~ S(z) := sqrt(2 pi) e (z + y) sqrt(z + y + -) 6 where y is somewhat arbitrary. The case y=0 closely resembles (and thoroughly trounces) the traditional formula. However, there is a clearly best value of y, ~.96841318776609465, that minimizes max |log(S(z)/z!)|. 0<=z<oo The worst cases are at z=0 and z = w :~ .7662945329650573, [w,y] being a solution of | 2 1 | log (z + y + -) | d 6 | [-- (log(z!) - ---------------- - z log(z + y) + z + y) | , dz 2 | |z = w 2 1 2 1 log((y + -) (y + w + -)) 6 6 w! - -------------------------- - w log(y + w) + 2 y + log(-----) + w]. 2 2 %pi S(0)/0! ~ 1.00021756216683 ~ w!/S(w), i.e., .02% max error. z! = round(S(z)) for z = 0..7. S(8) ~ 40319.05, which could be fixed by a parity argument. It might be possible to combine this S(z) approximation with fancier divisibility arguments (and a slightly different, possibly variable y) to get a competitive (exact) algorithm for large integer z. For a numerical Gamma function, one can choose the y (e.g. .545525525713106) that minimaxes error (in this case, 3e-7) over, in this case, 9 <= z < oo. Then for small z use the standard trick, z! = (z+9)!/(z+9)/.../(z+1). Strangely, there is another, minutely inferior y ~ .9523531774380170, with max error near w=15.79 vs 15.45 . --rwg

3 2

[math-fun] Re polyanygons
by N. J. A. Sloane 23 Oct '05

23 Oct '05

I'm adding this to the OEIS, OK? %I A111189 %S A111189 1,2,3,9,20,75 %N A111189 Number of polyanygons with score n. %C A111189 These are similar to polyominos, except you can use any regular polygons of side = 1, as long as there's no overlapping. %C A111189 A regular polygon of N sides has a score of N-2: triangles score 1, squares 2, etc. The score for a polyanygon is the total of its components. %C A111189 These are with all symmetries (rotations, reflections) removed. %C A111189 Note that higher scoring polyanygons can have partially offset edges, so the perimeter might not always be an integer. %C A111189 The regular hexagon is regarded as different from the same shape made out of six triangles. It's also possible to make a dodecagon by adding a fringe or alternating triangles and squares to a regular hexagon. I think these are the only ambiguous cases. %e A111189 The 3 polyanygons of score 3 are the triamond (three regular triangles), a square stuck to a triangle (a house), and the pentagon. %O A111189 1,2 %K A111189 nonn,more %Y A111189 Initially this agrees with A001004 but will eventually diverge from it. %A A111189 Richard Schroeppel (rschroe(AT)sandia.gov) Oct 23 2005 NJAS

2 1

[math-fun] a little more on power sums
by Chris Landauer 20 Oct '05

20 Oct '05

hihi, all - this morning, neil asked me about the non-representable integers, so here is what i know so far (though i'd be happy if somebody would confirm the program, since i wrote it so long ago) my program counts the number of representations of a non-negative integer n in the form n = a^2 + b^3 + c^4 + d^5 + e^6, with a, b, c, d, e non-negative, or more generally, with a, b, c, d, e >= s (for various small s >= 0 that i call the strictness constraint) after that, i can extract the integers not representable in the given form (among other things) this program is relatively dumb and slow, though, since it starts by fitting the largest square under n, not the largest sixth power (which has many fewer choices for a given n, obviously) - i imagine it would be MUCH faster with the reverse search order, but i didn't write it that way (it appears from the graphs i have that the program takes more than quadratic time but less than cubic time to compute and count all representations from 0 up to n) case s=0 0 misses up to n = 282551 (this program is still running, and will run up to a million) case s=1 first count > 0 is 1 for n = 5 first count > 1 is 3 for n = 20 47 misses up to n = 100000: 0-4 6 7 9 10 11 14 16 17 18 19 21 22 24 25 26 32 33 37 38 41 45 48 50 52 56 57 63 64 69 72 74 87 89 96 108 113 115 202 206 232 256 656 case s=2 first count > 0 is 1 for n = 124 first count > 1 is 3 for n = 220 534 misses up to n = 336807: 0-123 125 126 127 128 130 131 132 133 134 135 137 138 139 140 141 142 144 146 147 149 150 151 152 153 154 157 158 159 160 161 162 163 165 166 167 168 170 171 172 173 174 176 177 178 179 181 182 183 186 187 190 191 193 195 196 197 198 199 200 202 204 205 206 207 209 211 214 215 216 217 218 219 222 223 224 226 227 228 230 231 232 233 235 236 237 238 242 243 244 247 248 251 252 254 255 256 258 259 261 263 265 267 269 270 271 272 274 275 278 279 280 281 282 284 287 288 291 292 293 294 295 296 298 299 300 302 303 307 309 310 312 313 314 315 317 319 321 323 324 326 328 330 331 333 334 336 339 342 343 346 349 350 352 355 357 360 361 363 365 368 370 371 374 378 379 382 384 387 389 390 393 394 398 407 408 411 413 416 417 422 426 427 430 434 435 438 439 447 448 453 454 455 458 467 469 470 476 478 482 483 485 489 490 492 495 499 503 505 506 507 510 511 518 521 525 532 534 535 542 544 547 550 551 554 557 563 566 567 568 570 571 574 578 579 581 582 586 590 595 597 600 605 609 610 614 619 622 625 627 630 638 642 647 650 656 658 659 661 662 665 666 667 679 681 686 687 694 695 700 701 706 707 710 718 719 722 723 726 729 732 736 742 746 749 751 755 758 762 763 774 775 781 782 785 790 792 798 799 803 805 806 807 811 814 818 819 822 825 826 830 836 841 842 847 865 867 870 872 876 887 888 897 901 902 903 912 919 921 924 930 934 937 940 943 947 952 957 958 959 974 982 993 996 998 999 1011 1014 1022 1030 1043 1047 1054 1087 1099 1118 1123 1132 1154 1160 1168 1183 1190 1216 1222 1243 1251 1255 1262 1270 1290 1351 1366 1383 1414 1427 1446 1470 1491 1495 1603 1605 1622 1623 1659 1667 1763 1779 1814 1839 1875 1967 1974 2003 2014 2051 2079 2091 2211 2366 2783 2814 2851 2854 2986 3107 3155 3302 3423 3443 3471 more later, cal

1 0

[math-fun] a little more on sums of powers 2,3,4,5,6
by Chris Landauer 19 Oct '05

19 Oct '05

hihi, all - there are 534 non-negative integers not expressable as a sum n=a^2+b^3+c^4+d^5+e^6 with a, b, c, d, e all at least 2 (i call this the strict 2 constraint), and the last few of them are 2003 0 2014 0 2051 0 2079 0 2091 0 2211 0 2366 0 2783 0 2814 0 2851 0 2854 0 2986 0 3107 0 3155 0 3302 0 3423 0 3443 0 3471 0 (pending some independent real checking; these are just what the program puts out) up to 320000, the largest count in this case is 250 for 294282 (the largest count for n <= 77317 is 113 for n=76554, and the largest count for n <= 10000 is 34 for 9905) similarly, there are 47 non-negative integers not expressable as a sum of the same form with a, b, c, d, e at least 1 (this is the strict 1 constraint), and the last of them are 108 0 113 0 115 0 202 0 206 0 232 0 256 0 656 0 up to n=10000, the largest count is 64 for 8258 in the strict 0 case, every non-negative integer can be represented, and the largest count for n <= 77317 is 268 for n=68122 (the largest count for n <= 10000 is 109 for n=9882) more soon, i think, though my program appears to have fallen into combinatoril oblivion - if it doesn't stop in a few days, i'll quit the search at 500000 (or maybe even 350000 - it's only gone 2000 in the last several hours) more later, cal

1 0

[math-fun] sums of powers 2,3,4,5,6
by Chris Landauer 19 Oct '05

19 Oct '05

hihi, all - a few days ago, rich wrote: Chris Landauer worked on the 2...6 problem long long ago; I think his program got up to a million or so. i sort of remembered it, so i went back to look - in july of 1984, i ran a program to count how many representations there were for non-negative integers of the form n = a^2 + b^3 + c^4 + d^5 + e^6 with a, b, c, d, e non-negative i only ran it up to a few thousand, but i did run it for scattered values near a million i ran it last night and it is up to about 300000 so far - i am using the "strict" formulation, in which a, b, c, d, e all have to be at least 2, and still getting many representations for each rechable number (obviously, low values are not representable that way all the time), and i'll run it again with strict bound 1 when this one finishes (which should be about aweek or so) more soon, cal

1 0

[math-fun] napkin problem
by James Propp 19 Oct '05

19 Oct '05

I learned last month that the "napkin problem" that I've attributed to Margulis (an attribution that seems to be widespread: see for instance www.ics.uci.edu/~eppstein/junkyard/napkin.html) was actually introduced by Vladimir Arnold. Or at least, this is what Arnold says; see page viii of the book "Arnold's Problems". So unless Margulis has claimed credit for the problem, we should all start attributing it to Arnold. This problem asks whether it is possible to fold a square napkin into a flat shape whose outline has larger perimeter than the original unfolded napkin. Serge Tabachnikov tells me that the problem has a positive solution if arbitrary origami-type folding is allowed (I'd seen this claimed before, and saw a preprint that purported to give the construction, but I never checked the details to see if I really believed it), and it has a negative solution if each successive fold is required to be of the form "Take the existing flat shape and fold it over a line that cuts all the way through it to obtain another flat shape". Serge did not provide me with citations, though, so if any of you can provide them, I'd be grateful. Jim Propp

1 0