September 2014 - mathfun@mailman.xmission.com

[math-fun] Sequence meeting
by rcs＠xmission.com 12 Oct '14

12 Oct '14

Looks like a fun weekend ahead! http://dimacs.rutgers.edu/Workshops/OEIS/abstracts.html A missing talk: How to look hard for sequence combinations? Neil must have addressed this in Superseeker, but I haven't seen any writeup. Suppose I have generated a new sequence M(n), and it's not in OEIS. Maybe it's some combination of OEIS sequences. What's a good way to proceed? I can look for M(n) = A(n) + B(n) reasonably efficiently (assuming I have a local copy), but trying A+B+C etc. rapidly outruns available computing resources. Also, automatically rejecting false positives looks hard. This seems like a natural area for research. Rich

4 4

Re: [math-fun] FullSimplify embarrassment contest
by Bill Gosper 07 Oct '14

07 Oct '14

JBuddenhagen>Don't know mathematica. Perhaps of interest, wolframalpha also fails to simplify to 0, see http://www.wolframalpha.com/input/?i=arccos%28-%287%2F9%29%29+-+2*arcsec%28… However my old maple 7 outputs 0 for simplify(arccos(-(7/9)) - 2*arcsec(3)); <JB GACK! Instead Malpha expresses the 0 in terms inverse Jacobi elliptic functions! And then asks me to pay for additional computation time. My Macsyma hasn't yet adapted to Mavericks, but I can pretty much predict the outcome. Macsyma's closest (not very) equivalents to the FullSimplify shotgun are rat, ratsimp, and radcan, which are for canonicalizing certain classes of expressions, e.g. rational and algebraic functions, logs, powers, etc. They wouldn't apply here, at least directly. Likewise trigsimp, which isn't for arctrigs. As with Mathematica, trigexpand(cos(%)), or ratsimp thereof, would surely work. But to get 0 directly, I would try radcan(logarc(%)), converting the arctrigs to complex logs. In fact, Mathematica's equivalent is In[99]:= TrigToExp[%97] Out[99]= -(\[Pi]/2) + I Log[-((7 I)/9) + (4 Sqrt[2])/9] - 2 I Log[I/3 + (2 Sqrt[2])/3] In[100]:= FullSimplify[%] Out[100]= 0 So it's pretty much a bug that FullSimplify forgot to try TrigToExp, or got scared by the intermediate swell. I'll bet I have somewhere some more egregious cases. Anyone else? --rwg On Sun, Sep 28, 2014 at 6:13 PM, Bill Gosper <billgosper(a)gmail.com> wrote: What is the "simplest" 0 FullSimplify can't see? Extra credit if FunctionExpand fails too. I'll start the bidding with In[97]:= FullSimplify[FunctionExpand[Subtract @@ %]] Out[97]= ArcCos[-(7/9)] - 2 ArcSec[3] In[98]:= TrigExpand[Cos[%]] Out[98]= 1 --rwg ________________________________

2 3

[math-fun] Multiplying repeating decimals
by James Propp 01 Oct '14

01 Oct '14

I had assumed that if you multiply an eventually repeating decimal of period m and an eventually repeating decimal of period n, you get an eventually repeating decimal whose period is bounded by some polynomial function of m and n. But today I learned from Henry Cohn that that's not true: the period length can be exponentially large in m and n. More specifically, 1/(10^n-1) repeats with period n, but its square repeats with period 10^n-1 or thereabouts. I'm sure someone has written about the repeat-length for 1/(10^n-1)^2; can anyone provide a reference? Jim Propp

5 7

[math-fun] Microsoft announces move to nonary numbers
by Henry Baker 01 Oct '14

01 Oct '14

Today Microsoft incremented "8" to "10". http://blogs.windows.com/bloggingwindows/2014/09/30/announcing-windows-10/

6 5

[math-fun] The shape of pebbles
by Warren D Smith 30 Sep '14

30 Sep '14

Here's a fairly simple mathematical model which could be looked at numerically (but I haven't). Suppose the probability (at any time) your pebble has some orientation above a flat tabletop it rest on, is proportional to exp(-K*GravitationalEnergy) for some constant K>0. This hypothesis is suggested by max-entropy considerations. You also could consider, e.g, not resting it on a flat tabletop, but rather the pebble is inside, say, a spherical bowl of some fixed radius. Assume the lowest point on the pebble (or anyhow the point in contact with whatever it rests on) is eroded at some rate (normal to the surface there) proportional to (1/R1+1/R2)^P where R1, R2 are the principal radii of curvature of the surface there and 1/2<=P<=1, in fact I think P=2/3. This hypothesis is suggested by "Hertzian contact theory" (see http://en.wikipedia.org/wiki/Contact_mechanics and http://www.nist.gov/calibrations/upload/nbsir_73-243.pdf for bad introductions) and the approximate law of wear ("tribology") that wear rate (as surface thickness loss per unit time) is proportional to normal pressure times sliding speed. I'm assuming (perhaps wrongly) sliding speed is distributed independently of orientation. Anyhow, under the above assumptions plus a further assumption of constant pebble mass due to continual rescaling to fixed volume... There would be transition rates between any shape 1 and any shape 2 infinitesimally far away in shape-space. Thus we would be defining a Markov chain in shape space. This Markov chain would have some stationary distribution, which would correspond to the predicted shape distribution of mass-M pebbles in the world. (The distribution would depend upon M and K.) Various simulation methods, including Monte Carlo, could be used. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Tall Towers
by Henry Baker 30 Sep '14

30 Sep '14

Project at Arizona State 20km Tower http://hieroglyph.asu.edu/project/the-tall-tower/ The tower project began when Neal Stephenson started asking a simple question: how tall can we build something? As he started working with structural engineer Keith Hjelmstad, it turned out that this question has some surprising answers. To learn more about the project or get involved, check out the Tower Group. http://hieroglyph.asu.edu/?gpages=tower-project High Altitude Launch for a Practical SSTO Existing engineering materials allow the constuction of towers to heights of many kilometers. Orbital launch from a high altitude has significant advantages over sea level launch due to the reduced atmospheric pressure, resulting in lower atmospheric drag on the vehicle and allowing higher rocket engine performance. High altitude launch sites are particularly advantageous for single stage to orbit (SSTO) vehicles, where the payload is typically 2% of the initial launch mass. An earlier paper enumerated some of the advantages of high altitude launch of SSTO vehicles. In this paper, we calculate launch trajectories for a candidate SSTO vehicle, and calculate the advantage of launch at launch altitudes 5 to 25 kilometer altitudes above sea level. The performance increase can be directly translated into increased payload capability to orbit, ranging from 5 to 20% increase in the mass to orbit. For a candidate vehicle with an initial payload fraction of 2% of gross lift off weigh t, this corresponds to 31% increase in payload (for 5 km launch altitude) to 122% additional payload (for 25 km launch altitude). http://scitation.aip.org/content/aip/proceeding/aipcp/10.1063/1.1541305 Mass of Extremely Tall Truss Towers http://alnaspaceprogram.org/towers.html http://alnaspaceprogram.org/studies/towers/mass_of_extreme_towers.html http://www.newscientist.com/blogs/culturelab/2012/09/making-science-fiction… Space tower: could we build a stratosphere scraper? 15:39 10 September 2012 Jim Giles, consultant Could a fictional tower that reaches far into the stratosphere really get built? The new Center for Science and the Imagination at Arizona State University brings novelists and engineers together to push the boundaries of science NEAL STEPHENSON has a big idea. He imagines a 20-kilometre-high steel tower that reaches into the stratosphere. From that height, weather patterns would be distant swirls. Planes could save fuel by docking at the tower rather than landing, and space missions could do the same by launching from it. A science-fiction novelist, Stephenson is not just using his idea as the basis for a story. The author of the critically acclaimed Snow Crash is taking the unusual step of teaming up with a structural engineer, Keith Hjelmstad at Arizona State University (ASU) in Phoenix, to work out how to actually build the tower. The project is not a one-off. This month will see the launch of the Center for Science and the Imagination, an ASU project that will bring together scientists, engineers, artists and writers and encourage them to think big. The idea is to team artists and authors with ASU researchers to turn science fiction into reality. In the first half of the 20th century, pulp science fiction, with its focus on intergalactic exploration, helped inspire a generation of children who grew up wanting to be astronauts and rocket engineers. By contrast, contemporary sci-fi is often far more dystopian. This project aims to find that inspiration again, not only for future scientists, but also for those who already have the skills to carry out such projects. "A well-written sci-fi story can obviate a lot of PowerPoint presentations and meetings," says Stephenson. Hjelmstad is now analysing the feasibility of Stephenson's tower. Preliminary modelling suggests that it could support its own weight, but many questions remain. Hjelmstad must determine, for instance, whether the tower can support the payload associated with each of the uses that Stephenson imagines. "The tower pushes well beyond anything anyone has ever done in structural engineering," says Hjelmstad. "Building [it] would be the biggest project ever undertaken by humans." The tower story will be published by Hieroglyph, a joint project between the centre and Stephenson, which will host online forums for further discussion. Other writers can also use Hieroglyph to contribute new stories and collaborate with ASU scientists. Author Cory Doctorow, for example, has a story and accompanying research project based around the idea of sending 3D printers to the moon, where the devices would build a base for humans to inhabit later. The idea of focusing on tangible outcomes, albeit ones that will probably not be realised for a decade or more, has not been a major part of previous collaborations between artists and scientists. "It has been a one-way door a lot of the time," says Tami Spector, a chemist at the University of San Francisco who writes about sci-art. "Scientists tend to view art as in service of science and artists tend to view science as a tool for doing art." The Wellcome Trust, a London-based biomedical research funder, spent close to Â£3 million on art-science collaborations between 1996 and 2006. When independent reviewers examined the programme in 2009, they praised the art it produced but also noted that it had little impact on scientific practice. Things may now be changing. In one recent project, for example, fashion designer Helen Storey teamed up with chemist Tony Ryan to treat clothes with compounds that purify the air. The pair are now developing a product for home use. The Wellcome Trust's arts adviser MeroÃ« Candy sees a wealth of such possibilities. She says artists can help scientists visualise data to reveal previously unseen patterns or ask questions that lead research in unexpected directions. If Candy is right, the ASU centre may mark a new attitude towards sci-art collaboration. For Ed Finn, who will direct the centre, success will be measured in part by a change in thinking about "audacious moonshot ideas" that are seen as too ambitious for the incremental process of contemporary science. "I'll know we have succeeded if in five years we have lots of scientists and engineers clamouring to get involved in our seminars," he says.

4 4

[math-fun] First polynomial time algorithm to output Ramanujan's "highly composite numbers."
by Warren D Smith 30 Sep '14

30 Sep '14

First polynomial time algorithm to output Ramanujan's "highly composite numbers." =========Warren D. Smith==========Sept. 2014====================== Ramanujan defined a number N to be "highly composite" is it has more divisors than any lesser number. These are the "opposite" of the primes. I discovered for the first time, that there are algorithms to output the first K of Ramanujan's "highly composite numbers" (HCNs), or to output all HCNs N with lnN<K, or to decide whether a given K-bit number N is an HCN (all three goals work, in fact the first two can be shown to be computationally polynomially equivalent) each in time bounded by polynomial(K). I also found a very fast algorithm to output SHCNs (Ramanujan's "superior highly composite numbers," a sparse but infinite subset of the HCNs)... the ratio between successive SHCNs is always a prime, and so by outputting that sequence of prime ratios you can keep the output much shorter... and to output the first K SHCN ratios can be done in about O(logK) steps per SHCN, which note is much smaller time than would be required to output the SHCNs themselves (purely because they are bulky). I prove the Kth SHCN is K^([1-o(1)]K). I have been for some time trying to work on a paper about HCNs and SHCNs, but in case I never manage to finish it, here is a quick but reasonably complete sketch of how the HCN algorithmic results established. I rest heavily on the paper S.Ramanujan: Highly composite numbers, Proc. London Math. Soc. (2) 14 (1915) 347-409 which is available online here: http://ramanujan.sirinudi.org/Volumes/published/ram15.pdf but a goodly part of this 1915 paper was not published at that time due to financial difficulties. We will not need the missing part, but it was reconstructed (with annotations & corrections) from old notes by Ramanujan and was then published in The Ramanujan Journal I (1997) 119-153 (thus totalling 98 pages) available online here: http://math.univ-lyon1.fr/~nicolas/ramanujanNR.pdf The more I look at these Ramanujan papers, the more I appreciate them. Although Ramanujan was famous for finding mysterious identities with no explanation, when he did set his mind to delivering explanations, as here, result was very nice. FIRST TRICK: The numbers N will be represented in "fancy staircase form." That is, if the prime factorization of N is N = 2^a 3^b 5^c ... Q^z then Ramanujan showed a>=b>=c>=...>=z and that z=1 or z=2, with z=2 happening only when N=4 or 36. Thus the exponents a,b,c,...,z form a descending "staircase." Further important lemmas about this staircase (proved by Ramanujan and/or me): 1: The maximum prime is Q ~ lnN. 2: The maximum exponent is a ~ lnQ /(ln2)^2 ~ (lnlnN)/(ln2)^2. 3. Also a is an upper bound on the number of stairstep down-jumps. 4. If P^2 * (lnP)^3 < (lnQ)/8 then the primes 2,3,5,...,P all have distinct exponents. The exponent e of the greatest such P obeys e ~ (ln2)^(-2) * 2 * lnQ / lnlnQ. 5. lnN = a*ln2+b*ln3+c*ln5+...+*lnQ. 6. ln(d(N)) = (a+1)*(b+1)*(c+1)*...*(z+1). where d(N) is the number of divisors of N. 7. The exponent f of any prime R with 2<=R<=Q obeys floor( lnQ / lnR ) <= f <= 2*floor( ln(Q+) / lnR ) where Q+ is the least prime greater than Q. The "exponent list" representation of N is to state all the exponents a,b,c,...,z. This requires stating ~ lnN / (lnlnN) numbers. The "plain staircase" representation of N is to state, for each integer j=1,2,3,...,a, the greatest index of any prime P such that the exponent of P is >=j. This requires stating a ~ lnlnN / (ln2)^2 numbers. The "fancy staircase" representation of N is to state, for each integer j=1,2,3,...,e, the greatest index S[j] of any prime P such that the exponent of P is >=j, plus also state the stairstep heights (exponent differences) for the exponents of the primes 2,3,5,...,P. This requires stating <=e+P ~ (ln2)^(-2) * 2 * lnlnN / lnlnlnN numbers. It may be shown that the S[j] approximately equal Q^lg(1+1/j) where lg(x)=ln(x)/ln(2). In view of this, the total number of bits you need to write down all these numbers, is about lgQ * (1+1/2+1/3+1/4+...+1/e) i.e. O(lgQ * lglnQ) bits. Although the fancy staircase representation is much more concise than more-naive representations of N, this still by itself is not small enough to make a brute force search be a polynomial time algorithm. SECOND TRICK: Write it as an "integer convex program." Specifically, let T[j]=S[j-1]-S[j]>=0 now be regarded as the (non-negative integer) variables for j=1,2,3,...,e. (The remaining T[j] for j=e+1,e+2,...,a can be dealt with by brute force trial of all possible staircase-chunks, because the total number of bits needed to describe this remaining part of the staircase is small enough.) The T[j]>=0 are linear inequalities. ln(d(N)) = SUM_j T[j] * ln(j+1) is a linear function of the T[j], so it we have some HCN N' and want to find the next greater HCN N, we can demand d(N) >= d(N')+1 as a linear inequality. Finally lnN = SUM_j ln(primorial(S[j]) where primorial(k) is the product of the first k primes, is a concave-U function of the S[j]'s and hence of the T[j]'s. So finding the next HCN N is minimizing a concave-U function of v=O(lnlnN/lnlnlnN) variables subject to linear inequality constraints, and integrality constraints. This is exactly an "integer convex program." THIRD TRICK: I invented a new algorithm for integer convex programming. Ravi Kannan: Minkowski's convex body theorem and integer programming, Mathematics of Operations Research 12,3 (Aug. 1987) 415-440 available online here: http://repository.cmu.edu/cgi/viewcontent.cgi?article=2568&context=compsci showed how to solve v-variable integer programs in v^O(v) time. [He also found v^O(v)-time procedures for shortest nonzero vector in a lattice, and closest lattice vector, in for v-dimensional lattices, but these two algorithms have been obsoleted by later authors with 2^O(v)-time methods. It remains an important open problem as of year 2014 whether integer programming can be done in 2^O(v) time.] Strangely enough, Kannan and other authors never mentioned the fact -- but I claim it is true -- that ideas very much like his will solve CONVEX integer programs, a wider class than LINEAR IPs, still in v^O(v) time, where the convex objective function, and convex-membership constraints, both can be specified by a "weak membership oracle." I sketch the method to accomplish this. In the HCN application, there will be an outer binary search over N, trying to find the least N with d(N)>=d(N')+1. The search will continually ask yes/no existence questions of an integer convex programming subroutine, of the form "does an N exist with N'<N<X?" (If "no" then increase X. If "yes" then decrease X.) To build the existence-deciding subroutine, we first perform a rational linear transformation to "well round" the region we are asking about whether it contains an integer point. Such "well roundings" can be found in polynomial time using methods discussed in M.Gr"otschel, L.Lovas, A.Schrivjer: Geometric algorithms and combinatorial optimization, Springer 1988 based on the "ellipsoid algorithm" for polynomial time convex programming (for rationals, NOT for integers). Well rounding also can be done by by a different method (if you are willing to use nondeterministic algorithms) in U. Faigle, N. Gademann, W. Kern: A random polynomial time algorithm for well-rounding convex bodies, Discrete Applied Mathematics 58 (1995) 117-144. After rounding transform, the convex region is now spherical to within radial factors of v^O(1). We now find the shortest nonzero vector in the integer lattice (in the new linearly transformed space) and indeed a "good basis" for said lattice, using the methods by Kannan or his successors, in v^O(v) or 2^O(v) time. We then find all lattice vectors at most v^O(1) times longer than shortest. There are at most v^O(v) such vectors. One of them will yield an N solving our integer convex program existence question if any solution exists. That answers the yes/no question. FINAL RESULT: Since v=O(lnlnN/lnlnlnN) in the HCN application, v^O(v) is bounded by polynomial(lnN). Hence we can, given any HCN N', find the next HCN N, in time < polynomial(lnN). QED. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Stupid number theory Q re quadratic residues
by Henry Baker 29 Sep '14

29 Sep '14

The following question occurred to me on a long bike ride (?!?) yesterday: Suppose I know the quadratic character of a wrt N for lots of different N's. Under what conditions can I reconstruct N ? I.e., is there a "Chinese Remainder Theorem" for quadratic residues?

6 7

Re: [math-fun] quadratic characters
by Henry Baker 29 Sep '14

29 Sep '14

Interesting! Thx. Here's some links: https://en.wikipedia.org/wiki/Lehmer_sieve Wooding 2003 Master's Thesis: Development of a High-Speed Hybrid Sieve Architecture http://pintday.org/kjell/msc/cassiethesis.pdf Wooding 2010 PhD Thesis: The Sieve Problem in One and Two Dimensions http://people.ucalgary.ca/~hwilliam/files/wooding10thesis.pdf At 11:21 AM 9/29/2014, Warren D Smith wrote: >Baker's question was exactly what Lehmer's bicycle-chain sieve and >related later machines (Univ. of Manitoba machine based on shift >registers) were intended to solve.

1 0

Re: [math-fun] FullSimplify embarrassment contest
by Axel Vogt 29 Sep '14

29 Sep '14

> From: James Buddenhagen <jbuddenh(a)gmail.com> > Subject: Re: [math-fun] FullSimplify embarrassment contest ... > However my old maple 7 outputs 0 for simplify(arccos(-(7/9)) - 2*arcsec(3)); Concurrent Maple 18 needs conversion to arctan, then simplify works to give 0.

1 0