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

[math-fun] Space for Sieve of Eratosthenes ~ O(n^(1/3))
by Henry Baker 27 Sep '16

27 Sep '16

FYI -- Can anyone provide a 30-second explanation of this algorithm? https://science.slashdot.org/story/16/09/26/2128254/researcher-modifies-sie… Researcher Modifies Sieve of Eratosthenes To Work With Less Physical Memory Space (scientificamerican.com) Posted by BeauHD on Monday September 26, 2016 @07:30PM from the ones-and-zeros dept. grcumb writes: Peruvian mathematician Harald Helfgott made his mark on the history of mathematics by solving Goldbach's weak conjecture, which states that every odd number greater than 7 can be expressed as the sum of three prime numbers. Now, according to Scientific American, he's found a better solution to the sieve of Eratosthenes: "In order to determine with this sieve all primes between 1 and 100, for example, one has to write down the list of numbers in numerical order and start crossing them out in a certain order: first, the multiples of 2 (except the 2); then, the multiples of 3, except the 3; and so on, starting by the next number that had not been crossed out. The numbers that survive this procedure will be the primes. The method can be formulated as an algorithm." But now, Helfgott has found a method to drastically reduce the amount of RAM required to run the algorithm: "Now, inspired by combined approaches to the analytical 100-year-old technique called the circle method, Helfgott was able to modify the sieve of Eratosthenes to work with less physical memory space. In mathematical terms: instead of needing a space N, now it is enough to have the cube root of N." So what will be the impact of this? Will we see cheaper, lower-power encryption devices? Or maybe quicker cracking times in brute force attacks? Mathematician Jean Carlos Cortissoz Iriarte of Cornell University and Los Andes University offers an analogy: "Let's pretend that you are a computer and that to store data in your memory you use sheets of paper. If to calculate the primes between 1 and 1,000,000, you need 200 reams of paper (10,000 sheets), and with the algorithm proposed by Helfgott you will only need one fifth of a ream (about 100 sheets)," he says. http://www.scientificamerican.com/article/new-take-on-an-ancient-method-imp…

5 4

Re: [math-fun] Space for Sieve of Eratosthenes ~ O(n^(1/3))
by Henry Baker 27 Sep '16

27 Sep '16

So at some increase in complexity, this could be (theoretically) improved through increased fragmentation? What is the theoretical lower space bound on sieving -- if known? (Does a lower space bound even make any sense relative to brute force?) At 08:57 AM 9/27/2016, Tomas Rokicki wrote: >From the professor's comment on slashdot, it appears it's an incremental sieve >that works on the span [N, N+N^(1/3)] and, rather than consider all potential >prime factors < N^(1/2), it figures out which potential prime factors cannot >possibly have multiples in the range [N, N+N^(1/3)] (which is the great >majority). > >-tom > >On Tue, Sep 27, 2016 at 8:51 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> FYI -- Can anyone provide a 30-second explanation of this algorithm? >> >> https://science.slashdot.org/story/16/09/26/2128254/ >> researcher-modifies-sieve-of-eratosthenes-to-work-with-less-physical-memory-space >> >> Researcher Modifies Sieve of Eratosthenes To Work With Less Physical >> Memory Space (scientificamerican.com) >> >> Posted by BeauHD on Monday September 26, 2016 @07:30PM from the >> ones-and-zeros dept. >> >> grcumb writes: Peruvian mathematician Harald Helfgott made his mark on the >> history of mathematics by solving Goldbach's weak conjecture, which states >> that every odd number greater than 7 can be expressed as the sum of three >> prime numbers. >> >> Now, according to Scientific American, he's found a better solution to the >> sieve of Eratosthenes: >> >> "In order to determine with this sieve all primes between 1 and 100, for >> example, one has to write down the list of numbers in numerical order and >> start crossing them out in a certain order: first, the multiples of 2 >> (except the 2); then, the multiples of 3, except the 3; and so on, starting >> by the next number that had not been crossed out. The numbers that survive >> this procedure will be the primes. The method can be formulated as an >> algorithm." >> >> But now, Helfgott has found a method to drastically reduce the amount of >> RAM required to run the algorithm: >> >> "Now, inspired by combined approaches to the analytical 100-year-old >> technique called the circle method, Helfgott was able to modify the sieve >> of Eratosthenes to work with less physical memory space. In mathematical >> terms: instead of needing a space N, now it is enough to have the cube root >> of N." >> >> So what will be the impact of this? >> >> Will we see cheaper, lower-power encryption devices? >> >> Or maybe quicker cracking times in brute force attacks? >> >> Mathematician Jean Carlos Cortissoz Iriarte of Cornell University and Los >> Andes University offers an analogy: >> >> "Let's pretend that you are a computer and that to store data in your >> memory you use sheets of paper. If to calculate the primes between 1 and >> 1,000,000, you need 200 reams of paper (10,000 sheets), and with the >> algorithm proposed by Helfgott you will only need one fifth of a ream >> (about 100 sheets)," he says. >> >> http://www.scientificamerican.com/article/new-take-on-an-ancient-method-imp… > >-- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --

2 1

Re: [math-fun] Space-filling curves again
by Bill Gosper 26 Sep '16

26 Sep '16

On 2016-09-26 11:51, James Propp wrote: > I just watched the "Space-Filling Curves" video on Numberphile (featuring > Henry Segerman and his interpolating surfaces), and it rekindled my desire > to see something similar that's a bit more canonical somehow. It kindles my desire to shout "Henry, how can you perpetrate such baloney?!" Most spacefilling apologists just resort to circular reasoning, but this isn't even reasoning! It's clear to me that Segerman fully understands this business, but his model is too hairy to articulate in terms sufficiently elementary for Numberphile. The key lemma: A continuous function is completely defined by its values on a dense set. If we choose for our dense set the dyadic rationals, then a simple finite state machine will convert two bits of t to one bit of x and one bit of y in x(t) + i y(t) = Hilbert(t). It is rather easy to show continuity. And that a dense subset of [0,1]⨉[0,i] is covered *four* times! If poor Henry had asserted this, no-one would believe him. If, instead, the dense set is the rationals, then the four-way branching recursive definiton of H(t) will inevitably loop some point, yielding an equation that we can solve for that fixed point. > > Is there a way to relax an approximation to a space-filling curve in > continuous time so that it works out its kinks and regresses to simpler > approximations? > > (No interim self-intersections please!) > > Jim Propp http://gosper.org/FDrags128.mp4 If people really want to see it, Julian's recent Fourier matrix product can produce the analogous animation for Hilbert's "curve". But it is a seductive thought crime to view a spacefilling function as some kind of limit of "spacefilling curves"! Those curves Henry sketches are mere schematics, of no mathematical consequence. This leads inevitably to embarrassed hemming and hawing about how the area jumps from 0 to 1 at the very last moment, when both interior and exterior suddenly disappear and become boundary. Successive partial sums of the Fourier series are even more seductive. But no matter how many terms you take, you're still infinitely far from the end. --rwg > > On Monday, December 28, 2015, James Propp <jamespropp(a)gmail.com> wrote: > >> Is there anything like this surface that has constant negative curvature? >> >> That is: Can a topological disk embedded in 3-space with constant negative >> curvature have a (2-)space-filling curve as its boundary?

2 1

Re: [math-fun] Question about base 3/2
by Don Reble 26 Sep '16

26 Sep '16

Dr. Propp spotted an error in my .pdf document: W should be 3^n V(.P) / 2, one-half of the old value. After repairing ensuing details, it all seems to work. Are there other criticisms from anyone? -- Don Reble djr(a)nk.ca

1 0

[math-fun] Space-filling curves again
by James Propp 26 Sep '16

26 Sep '16

I just watched the "Space-Filling Curves" video on Numberphile (featuring Henry Segerman and his interpolating surfaces), and it rekindled my desire to see something similar that's a bit more canonical somehow. Is there a way to relax an approximation to a space-filling curve in continuous time so that it works out its kinks and regresses to simpler approximations? (No interim self-intersections please!) Jim Propp On Monday, December 28, 2015, James Propp <jamespropp(a)gmail.com> wrote: > Is there anything like this surface that has constant negative curvature? > > That is: Can a topological disk embedded in 3-space with constant negative > curvature have a (2-)space-filling curve as its boundary? >

1 0

[math-fun] Fwd: Bar bet
by Bill Gosper 26 Sep '16

26 Sep '16

By "opposite" I think Julian means reflected in a horizontal plane. --rwg ---------- Forwarded message ---------- From: Julian Ziegler Hunts <julianj.zh(a)gmail.com> Date: Sun, Sep 25, 2016 at 7:55 PM Subject: Re: [math-fun] Bar bet To: Bill Gosper <billgosper(a)gmail.com> But don't we need to prove that it _is_ tetrahedral, i.e. the tetrahedron > and octahedron > dihedrals are supplementary? Easier to just intersect two tetrahedra and note that this gives an octahedron with all the symmetries of the regular octahedron. How do we know that the intersection is an octahedron? What we're actually doing is taking a regular tetrahedron and cutting off the vertices to get an octahedron, then noting that the planes we're using to cut them off have the same symmetries hence also form a regular tetrahedron, which by inspection is opposite to the original (so that you can swap them). Julian

1 1

Re: [math-fun] Question about base 3/2
by Don Reble 25 Sep '16

25 Sep '16

> Is it possible to write 1/3 as an infinite sum of the form a_1 (2/3)^1 + > a_2 (2/3)^2 + ... where the sequence of nonnegative integer coefficients > a_1, a_2, ... is eventually periodic? No, I figure. Here's why http://www.graysage.com/djr/propp.pdf -- Don Reble djr(a)nk.ca

1 0

Re: [math-fun] Bar bet
by Bill Gosper 25 Sep '16

25 Sep '16

On 2016-09-25 16:18, James Propp wrote: > Kate Fractal should be invited to join math-fun! > > Jim Propp > > On Sunday, September 25, 2016, Andy Latto <andy.latto(a)pobox.com> wrote: > >> On Sun, Sep 25, 2016 at 12:01 PM, Hans Havermann <gladhobo(a)bell.net >> <javascript:;>> wrote: >> >> "The volume of a regular tetrahedron (triangular pyramid with unit >> edges) >> >> is exactly half the volume of a square pyramid with unit edges." >> > >> > This is (I think) equivalent to stating that the volume of an octahedron >> is four times the volume of a tetrahedron (unit edges assumed). >> >> Yes because you can slice an octahedron into two square pyramids. >> >> The geometrical "proof" of this is that you can assemble 4 unit >> tetrahedrons and a unit octahedron to produce a tetrahedron with edge >> length two, and therefore area equal to 8 tetrahedrons. >> >> I don't have the ability to draw a picture of this here, but start >> with an equilateral triangle of side 2, and divide it into 4 >> equilateral triangles of side 1. Place tetrahedrons on the 3 of these >> that are in the same orientation, and then add as a second layer a >> fourth tetrahedron whose bottom three vertices are the points of the >> first 3 tetrahedrons. These four tetrahedrons outline the shape of a >> side-2 tetrahedron, and the space in the large tetrahedron that isn't >> in any of the small ones is exactly a unit octahedron. >> >> Thanks to Kate Fractal for the idea of this construction. >> >> Andy https://en.wikipedia.org/wiki/Tetrahedral-octahedral_honeycomb#/media/File:… (Stick a tetrahedron onto the foremost face to complete a double size tetrahedron.) But don't we need to prove that it _is_ tetrahedral, i.e. the tetrahedron and octahedron dihedrals are supplementary? ("Behold!") Hans Moravec designed a version of hashlife based on this recursive partitioning of space. Time ran vertically, and the "initial" conditions were the lower faces, which completely determined the interiors and upper faces. I think he even got some unfortunate grad student to implement it. It was awkward because you normally start with a horizontal square grid initial condition. I think their scheme was to treat this as a "waffle iron" of minimal octahedra and then fill in the next layer of tetrahedra to make an "endo waffle iron", which then determined the next layer of octahedra. But this needs to be done cleverly, so as to halve the spatial frequency at each step, to get the crucial geometric growth of cell sizes, and hopefully, running speed. The hash table records upper faces as results of lower ones. I have no idea by how much this beats my inelegant scheme of overlapping frusta: https://www.lri.fr/~filliatr/m1/gol/gosper-84.pdf --rwg

1 0

[math-fun] Bar bet
by Bill Gosper 25 Sep '16

25 Sep '16

"The volume of a regular tetrahedron (triangular pyramid with unit edges) is exactly half the volume of a square pyramid with unit edges." True or false? --rwg

5 4

Re: [math-fun] Question about base 3/2
by Dan Asimov 25 Sep '16

25 Sep '16

As for periodic expansions in the most obvious sense: Let S = (2/3)^n + (2/3)^(n+k) + (2/3)^(n+2k) + ... = (2/3)^n / (1 - (2/3)^k) = 2^n / (3^k - 2^k). Not much thought went into this, but can S = 1/3 be achieved by some choice of n and k positive integral? We'd need 3^k = 2^k + 3*(2^n) which is impossible with n, k in Z+. —Dan Allan wrote: ----- ... It is entirely conceivable that there exists a *non-canonical* but *periodic* expansion. Jim provided one for 4/5 -- I'm sure the canonical expansion is completely chaotic in this case too. Jim was asking whether there was *any* periodic expansion. -----

2 1