February 2012 - mathfun@mailman.xmission.com

[math-fun] computing products like (1 - 2/p^2)
by Warren Smith 04 Feb '12

04 Feb '12

This is quite nice. For my particular products Prod[p prime] (1 - J/p^K) you can get faster convergence by dividing by Prod[p prime] (1 - 1/p^K)^J = Zeta(K)^J and then the new product converges faster, since the discrepancy from 1 no longer is dying like 1/p^K but rather like a higher power of p. Then at the end you divide out your Zeta power (which you already knew to high precision) to reconstitute the original. However, the papers by Moree, Nivasch, and Cohen go beyond that trick. As far as I can tell from not reading them (reader software: no deal), that was only the first trick in an infinite set of tricks. You can then do it again to cancel out the next-most-dominant term to get even faster convergence, and so on forever. Thus after the infinite number of tricks are applied, your product gets re-expressed as a certain product of integer powers of zeta functions at integer arguments. So, all these kinds of prime products are evaluable to ultrahigh precision.

1 0

[math-fun] computing products like (1 - 2/p^2)
by rcs＠xmission.com 04 Feb '12

04 Feb '12

The tidbit below is extracted from a post by Victor Miller that got caught in the mailing list filter. The Cohen paper is a good manual for computing zeta-ish products. http://www.math.u-bordeaux.fr/~cohen/hardylw.dvi I also liked the Niklasch paper mentioned in Veit Elser's note. http://oeis.org/A001692/a001692.html "Some number-theoretical constants arising as products of rational functions of p over primes" (Niklasch). Unfortunately, the internal link explaining details is broken. P. Moree, Approximation of singular series and automata, to appear in Manuscripta Math. (1999); preprint available (DVI). http://web.inter.NL.net/hcc/J.Moree/wrench.dvi Rich PS: reminder: the mailing list is configured to drop attachments, and to detain messages over 40KB. ----- Date: Sat, 4 Feb 2012 11:09:11 -0500 Subject: Re: [math-fun] number theory puzzle about squarefree number density From: Victor Miller <victorsmiller(a)gmail.com> To: math-fun <math-fun(a)mailman.xmission.com> As Warren pointed out the Euler product converges *really* slowly. That's why I didn't give a numeric value. However, you should look at Henri Cohen's unpublished (it certainly deserves to be published) paper on "High Precision computation of Hardy-Littlewood Constants" http://www.math.u-bordeaux.fr/~cohen/hardylw.dvi which deals with how to get very accurate approximations to such Euler products. It is (not surprisingly) implement in pari, I believe as the function eulerprod. I don't know why the IT newsletter was unreadable. Attached is the page with Golomb's column. Victor

1 0

[math-fun] number theory puzzle about squarefree number density
by Warren Smith 04 Feb '12

04 Feb '12

> From: Victor Miller <victorsmiller(a)gmail.com> > > Here's some answers (in addition you should look at Sol Golomb's > Puzzle column in the Dec 2011 issue of the IEEE Information Theory > Society Newsletter: > http://www.itsoc.org/publications/newsletters/nits_NL_1211-Web.pdf/view > which has a bunch of problems like this in even greater generality). --thanks, Miller's were the solutions I had in mind, though I was not aware of Golomb column. In fact I'm still not aware of it since my computer refuses to open the pdf file, says it is "damaged." Anyway, I will now say what I worked out on this puzzle. If we choose n random uniformly from {1,2,...,N} in limit N-->infinity, then probability that the j-tuple n, n-1, n-2 ..., n+1-J (for some fixed J>=1) all are simultaneously free of Kth powers (for some fixed K>=2) is prf(J,K) = prod(primes p) (1 - J / p^K) or in MAPLE notation prf := (J,K,N) -> product( 1 - J / ithprime(m)^K, m=1..N ); in the limit N-->infinity. This is rigorous since the "probabilistic independence" is a rigorously valid statement in this case (e.g. see M.Kac's book if you don't understand what I mean by that). In the case J=1 we get prf(1,K) = 1/RiemannZeta(K) so prf(1,2) = 6/Pi^2 = 0.6079271016. The problem I posed was prf(2,2)=0.32263405 as best I've been able to determine (computed up to the 16000th prime and extrapolation to infinity). Also, ct:=0; for n from 1+10^6 by -1 to 2 do if( issqrfree(n) and issqrfree(n-1) ) then ct:=ct+1; fi; od; print(ct); prints 322619. Unfortunately I do not have any closed forms or rapid-convergent expressions except in the J=1 cases, although it is possible (albeit it seems to be hurting not helping) to transform the product to an interesting sum. One might dream that some of the loveliness of the zeta function, such as reflection formula, Riemann-Siegel integral formula, etc, has analogs for the more general prf function. I have no evidence for that, but since the Zeta function is a special case you would have at least a foothold to try to work on that. And as Miller noted, the chance that either n OR n-1 (or both) is squarefree is 2*prf(1,2) - prf(2,2) = 0.89322015.

3 2

Re: [math-fun] number theory puzzle about squarefree number density
by Victor Miller 04 Feb '12

04 Feb '12

I realized that attachments are stripped out. I had transcribed the column into TeX. Here it is: Sol Golomb's column in the December 2011 of the IT Newsletter: The Sequence $n^3-n$ For every $n>1$ each term of the sequence $[n^3-n]$ is the product of the three consecutive positive integers, $n-1,n,$ and $n+1$. the sequence begins $[6,24,60,12-,240,336,\dots]$. Here are some questions about this sequence. 1) For which values of $n>1$ is $n^3-n=k!$ for some integer $k$? 2) For $n>3$, prove that $n^3-n$ must have at least three different prime factors. 3) What are all the values of $n>1$ for which $n^3-n$ has (only) three different prime factors? (The same prime factor is allowed to occur more than once in $n^3-n$). 4) What three different conditions on one of the $(n-1,n,n+1)$ may make it possible for $n^3-n$ to have (only) four different prime factors? (The same prime factor is allowed to occur more than once). The number of cases of each type appears to be infinite, but thsi cannot be currently proved. 5) Try to list all $n, 3 < n < 10^6$, for which $n^3-n$ has exactly four different prime factors. The same prime factor is allowed to occur more than once. (A computer program may be used, but the number of examples is not huge). >From here on, we consider only those $n > 1$ for which $n^3- n$ is {\em square-free}; i.e. that each prime factor of $n^3-n$ occurs only to the first power. 6) Which two prime numbers must divide $n^3-n$ for every $n>1$? What can you say about which factors, among $n-1,n$ and $n+1$, each of these two prime will divide? 7) Asymptotically, what fraction of integers $n, 1< n \le x$, give square-free values of $n^3-n$? (Give an infinite product expression and a numerical value). 8) Show that if $n^3-n$ is square-free, it can have $k < 5$ distinct prime factors only finitely many times. 9) List all values of $n>1$ for which $n^3-n$ is square-free with $k$ distinct prime factors, $1 < k < 5$. 10) List the first three occurrences of square-free $n^3-n$ having exactly $k$ distinct prime factors for each $k, 5 \le k \le 10$. (The smallest cases for $k=5,6,8,$ and $9$ are remarkable for the number of different small prime factors found among three consecutive integers).

1 0

[math-fun] The Catalan sequence decimal
by Robert Munafo 04 Feb '12

04 Feb '12

Yesterday I found the far easier-to-remember: 500 - sqrt(499*501) which also has secondary advantages of giving you 6 digits for each Catalan number, and being far easier to expand to an 8-digit or longer version if you want. - Robert mrob.com/pub/math/seq-digits.html#irrational On Sun, Jan 29, 2012 at 10:39, Warren Smith <warren.wds(a)gmail.com> wrote: > Jorg Arndt's example generating Pascal's triangle and a Fibonacci-like > sequence was considerably cooler... > another I invented quite a while back was > > 1000 / (500 + sqrt(249990)) > = > 1.00001000020000500014000420013200429014300... > > where the sequence 1,2,5,14,42,... is the Catalan numbers > (which easily give you the central binomial coefficients). > > How did I do that? Well, again, one way is using generating functions. > > But the continued fraction of quadratic irrationals is ultimately periodic > and once you know its period you can easily solve for the surd, so > again, this is easy to construct from the desired sequence without > any intelligence. > -- Robert Munafo -- mrob.com Follow me at: gplus.to/mrob - fb.com/mrob27 - twitter.com/mrob_27 - mrob27.wordpress.com - youtube.com/user/mrob143 - rilybot.blogspot.com

2 2

Re: [math-fun] Pseudorandom number generators
by Steve Witham 04 Feb '12

04 Feb '12

Jumping in at random... which I guess is appropriate in this case... >From: Marc LeBrun <mlb(a)well.com> > >>="J.P. Grossman" <jpg(a)alum.mit.edu> >> There's a good paper on parallel random number generation here: > > http://www.thesalmons.org/john/random123/papers/random123sc11.pdf > >Very interesting, thanks for the link! I will plan to read it more >carefully, but already I'm intrigued that one of the authors is *that* David >Elliot Shaw: http://en.wikipedia.org/wiki/David_E._Shaw Small valley! >... > >I don't know yet how this compares to what's in the cited paper, but another >thing Bill Gosper noted about the word-vector shift-register upstream >(Algorithm A) part of generator I described is that each step is effectively >a multiplication of the vector by a sparse 01 matrix whose non-zero entries >are simply the coefficients of the primitive polynomial (or the feedback >taps in the delay line, to use signal-processing lingo). >Thus one can jump n steps simply by multiplying by the n-th power of that >matrix instead. Done that part! ... >Of course the downstream (Algorithm M) part is specifically intended to mess >up even this vestigial "autocorrelation". Not that part. Anyway, I have on and off thought about the problem of random-access randomness for virtual worlds. This is probably a separate problem from the parallel-generation problem unless that includes nodes being recruited in an unpredictable, local-communication, spreading way. In the virtual world or unpredictable spreading case one would like (I think) unlimited, repeatable drill-down without weakening the randomness. An obvious but wrong approach is to treat nodes in a tree as seeds for their subtrees, but this has a kind of fixed-point problem. It would shrink the space of seeds at every downward step. The last I was thinking about this, the solution seemed to be to take a strong hash (like maybe one of the SHA's) of the full path from the root. So thanks J.P., Marc, and Joerg, I will read the paper. --Steve

1 0

[math-fun] number theory puzzle about squarefree number density
by Warren Smith 03 Feb '12

03 Feb '12

If you pick a random uniform number n with 0<n<=N then the probability n will be squarefree goes to 6/pi^2=60.79% in the limit N-->infinity. You probably already knew that. Result by Euler. Kind of a very inefficient way to calculate pi. Now, which are somewhat harder: PUZZLE #1: what is the probability that both n and n-1 are squarefree? PUZZLE #2: what is the probability that at least one of {n,n-1} is squarefree? (Actually, if you solve one puzzle, I think you'll find it very easy to solve the other...) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Philox random number generator. Not as smart as they think.
by Warren Smith 03 Feb '12

03 Feb '12

>JP Grossman: Hi Warren, the paper doesn't give the details of the "Threefish N-word P-box" transformation, but it's more complicated than swap(R1,R2) for exactly the reasons you mention (better mixing of low and high bits). --they had a footnote sating in the 4-word case it was just swapping the Rs. > A single 4-word philox round actually looks like this: (L1, R1, L2, R2) => (low(R2*M2), high(R2*M2) xor L1 xor K2, low(R1*M1), high(R1*M1) xor L2 xor K1) Changing some of the "xors" to adds to shave a cycle using madd instructions is a good idea. Also, you can indeed get rid of K altogether and still pass BigCrush with 7 rounds; the key was included just to show how one could be introduced if desired. --actually, the key really may be needed, because otherwise the original L's and R's being almost entirely 0s could make it take longer for philox to get going to generate randomness. (I suspect their bigcrush tests were conducted with initial counter far away from all-0.) >Incrementing a counter really is just fine; it doesn't matter that the high bits are the same. In fact, any single-bit mutation of the input produces a statistically uncorrelated output (that is, there is no correlation that BigCrush is able to detect), so you don't get any additional advantage from more complicated counter schemes. --yes, but that is the problem. They had to do a lot of philoxing, enough so any single bit change in the input produced random output. If their input already was pretty random and changed already by itself in lots of bits, then they could have gotten away with less philoxing. Their whole theme was that you can (a) do a complicated iteration and a simple output, or you can (b) do a simple iteration (a counter, the simplest) and a complicated state--> output transform. My point is, why go to silliness-extremes? There is no good reason we should use the incredibly simple state-iteration of just counting. We could do a somewhat more complicated state-transform, taking it looks to me the same amount of time as a plain +1 counter, thus enabling us to save work on the output transform by doing less philoxing. --Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

1 0

[math-fun] Wilson's theorem on primes (no, not that one, the one about decimals)
by Warren Smith 03 Feb '12

03 Feb '12

>rcs at xmission.com rcs at xmission.com David Wilson and Warren Smith batted about the side puzzle: When can the reciprocal of a composite N contain every digit combination of length floor[log10(N)]? Smith (roughly) argued 'never', and Wilson pointed out that some prime powers worked. Adding a bit more fuel: The reciprocals of 343 (7^3), 841 (29^2), and 799 (17*47) each contain all two-digit combinations. Rich --plainly, I was wrong. But why?

1 0

[math-fun] Philox random number generator. Not as smart as they think.
by Warren Smith 03 Feb '12

03 Feb '12

In that "best paper award" paper, John K. Salmon, Mark A. Moraes, Ron O. Dror, and David E. Shaw: Parallel Random Numbers: As Easy as 1, 2, 3 http://www.thesalmons.org/john/random123/papers/random123sc11.pdf they recommend random number generators based on 1) increment a counter 2) encrypt the counter via multiple rounds of "philox" transformations. A philox transform (which is a bijection) inputs two w-bit machine words L and R and outputs L' and R' where L' = R*M mod 2^w R' = floor(R*M / 2^w) XOR L XOR K where M is an odd constant and K is a constant (M and K can vary in different philoxes and they choose their Ms and Ks via a search for good ones that cause high "avalanching"). If we have a 64-bit machine and use L1,R1,L2,R2 for 256 bits in all in 4 words, then philox(L1,R1); //uses M1 which is fixed and K1 which increments by a constant philox(L2,R2); //uses M2 which is fixed and K2 which increments by a constant swap(R1,R2); is a "round". They find 7 rounds suffices to get immunity to the "crush U01" randomness test suite. One nice feature is you can tell it to use more rounds for less speed but more randomness (tunable). They also have other PRNGs based on the threefish and AES ciphers, but they are much more complicated to describe. CRITICISMS: Unfortunately, the flow of information in a philox transformation exhibits unidirectionality from the least- toward the most-significant bits. That is: Hi bits of R cannot affect lo bits of L'. Hi bits of L cannot affect lo bits of R'. Bits of L cannot affect any bits in L'. Therefore, the least-signif bits of L and R are going to be "less random" than its most-sig bits. Fortunately hi bits of R can affect lo bits of R' preventing complete death, but this gets the job done too slowly: it pathetically takes 3 rounds for hi bits of L to affect lo bits of (the new) L! To address this stupid deficiency, one might therefore consider interspersing philox transforms with these other kind of bijective transform: R = R XOR shiftright(R, H); and/or L = L XOR shiftright(L, H); and/or R = R XOR shiftright(L, H); where the H are (possibly varying) constants between 0.4 and 0.9 times the wordsize in bits. Furthermore to take advantage of multiply-and-accumulate when your computer has it, I'd recommend slightly redefining philox as L' = R*M mod 2^w R' = (floor(R*M / 2^w) + K mod 2^w) XOR L which is still a bijection. Furthermore, the idea of "increment a counter" is a bit too extreme (it leaves hi order bits almost always the same); we instead could increment one word by any odd constant (not 1) and increment a second word by a different odd constant (except not when the first word happens to equal 0). Something like this still has the same period as a counter but it changes a lot more bits every whack. Given that, you might want to dispense with K. AND SO.... My "better than best paper" award please? :)

2 1