September 2016 - mathfun@mailman.xmission.com

[math-fun] Julian has constructed a spacefill dense with sextuple points
by Bill Gosper 26 Jan '17

26 Jan '17

using a 25-way conditional. ClearAll[piecewiserecursivefractal]; piecewiserecursivefractal[x_, f_, which_, iters_, fns_] := piecewiserecursivefractal[x, g_, which, iters, fns] = ((piecewiserecursivefractal[x, h_, which, iters, fns] := Block[{y}, y /. Solve[f[y] == h[y], y]]); Union @@ ((fns[[#]] /@piecewiserecursivefractal[iters[[#]][x], Composition[f, fns[[#]]], which, iters, fns]) & /@which[x])); (I cannot praise this function enough.) In[363]:= trifil25[t_] := piecewiserecursivefractal[t, Identity, Piecewise[{{{1}, #1 == 0}, {{Ceiling[25*#1]}, Inequality[0, Less, #1, LessEqual, 1]}}, {}] & , {25*#1 + 0 & , -25*#1 + 2 & , 25*#1 - 2 & , 25*#1 - 3 & , 25*#1 - 4 & , 25*#1 - 5 & , 25*#1 - 6 & , 25*#1 - 7 & , 25*#1 - 8 & , -25*#1 + 10 & , -25*#1 + 11 & , 25*#1 - 11 & , -25*#1 + 13 & , -25*#1 + 14 & , 25*#1 - 14 & , -25*#1 + 16 & , 25*#1 - 16 & , -25*#1 + 18 & , 25*#1 - 18 & , 25*#1 - 19 & , -25*#1 + 21 & , -25*#1 + 22 & , 25*#1 - 22 & , -25*#1 + 24 & , 25*#1 - 24 & }, {#1/5 & , (1/10)*(3 + I*Sqrt[3] + (-1 - I*Sqrt[3])* #1) & , (1/10)*(3 + I*Sqrt[3] + #1 - I*Sqrt[3]*#1) & , (2 + #1)/5 & , (1/10)*(6 + #1 + I*Sqrt[3]*#1) & , (1/10)*(7 + I*Sqrt[3] + I*(I + Sqrt[3])*#1) & , (1/5)*(3 + I*Sqrt[3] - #1) & , (1/10)*(4 + 2*I*Sqrt[3] + (-1 - I*Sqrt[3])*#1) & , (1/10)*(3 + I*Sqrt[3] - 2*#1) & , (-(1/10))*I*(-I + Sqrt[3])*(-2 + #1) & , (1/5)*(2 + I*Sqrt[3] - #1) & , (1/5)*(2 + I*Sqrt[3] + #1) & , (1/10)*(5 + 3*I*Sqrt[3] + #1 - I*Sqrt[3]*#1) & , (1/10)*(4 + 2*I*Sqrt[3] + #1 + I*Sqrt[3]*#1) & , (1/10)*(4 + 2*I*Sqrt[3] + I*(I + Sqrt[3])*#1) & , (-(1/10))*I*(-I + Sqrt[3])*(-4 + #1) & , (1/5)*(2 + 2*I*Sqrt[3] + #1) & , (1/10)*(5 + 3*I*Sqrt[3] + #1 + I*Sqrt[3]*#1) & , (1/10)*(5 + 3*I*Sqrt[3] + 2*#1) & , (1/10)*(7 + 3*I*Sqrt[3] + (-1 - I*Sqrt[3])*#1) & , (1/5)*(4 + I*Sqrt[3] - #1) & , (1/10)*(9 + I*Sqrt[3] + I*(I + Sqrt[3])*#1) & , (1/10)*(9 + I*Sqrt[3] - 2*#1) & , (1/10)*(8 + I*(I + Sqrt[3])*#1) & , (4 + #1)/5 & }][[1]] E.g., In[361]:= trifil25[2/25 + 2/75] // ComplexExpand Out[361]= {1/2 + (I Sqrt[3])/10} In[367]:= Graphics[{Hue@#, Line[ReIm@{trifil25@#, trifil25[# + 5^-5]}]} & /@ Range[0, 1 - 5^-5, 5^-5]] gosper.org/trifil25.png (Those little white hexagons are sextuple points.) The inverse fractal, constructed more or less automatically: In[380]:= untrifil25[t_] := piecewiserecursivefractal[t, Identity, If[0 <= Re[#1] <= 1 && 0 <= Im[#1] <= Sqrt[3]/2, {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25}, {}] &, {ComplexExpand[5 #1] &, ComplexExpand[1/4 (6 - 2 I Sqrt[3] - 10 #1 + 10 I Sqrt[3] #1)] &, ComplexExpand[1/4 (-4 I Sqrt[3] + 10 #1 + 10 I Sqrt[3] #1)] &, ComplexExpand[-2 + 5 #1] &, ComplexExpand[1/4 (-6 + 6 I Sqrt[3] + 10 #1 - 10 I Sqrt[3] #1)] &, ComplexExpand[1/4 (4 + 8 I Sqrt[3] - 10 #1 - 10 I Sqrt[3] #1)] &, ComplexExpand[3 + I Sqrt[3] - 5 #1] &, ComplexExpand[1/4 (10 - 2 I Sqrt[3] - 10 #1 + 10 I Sqrt[3] #1)] &, ComplexExpand[1/2 (3 + I Sqrt[3] - 10 #1)] &, ComplexExpand[1/4 (8 - 10 #1 + 10 I Sqrt[3] #1)] &, ComplexExpand[2 + I Sqrt[3] - 5 #1] &, ComplexExpand[-2 - I Sqrt[3] + 5 #1] &, ComplexExpand[1/4 (4 - 8 I Sqrt[3] + 10 #1 + 10 I Sqrt[3] #1)] &, ComplexExpand[1/4 (-10 + 2 I Sqrt[3] + 10 #1 - 10 I Sqrt[3] #1)] &, ComplexExpand[1/4 (-2 + 6 I Sqrt[3] - 10 #1 - 10 I Sqrt[3] #1)] &, ComplexExpand[1/4 (16 - 10 #1 + 10 I Sqrt[3] #1)] &, ComplexExpand[-2 - 2 I Sqrt[3] + 5 #1] &, ComplexExpand[1/4 (-14 + 2 I Sqrt[3] + 10 #1 - 10 I Sqrt[3] #1)] &, ComplexExpand[1/2 (-3 I Sqrt[3] + 5 (-1 + 2 #1))] &, ComplexExpand[1/4 (16 - 4 I Sqrt[3] - 10 #1 + 10 I Sqrt[3] #1)] &, ComplexExpand[4 + I Sqrt[3] - 5 #1] &, ComplexExpand[1/4 (6 + 10 I Sqrt[3] - 10 #1 - 10 I Sqrt[3] #1)] &, ComplexExpand[1/2 (9 + I Sqrt[3] - 10 #1)] &, ComplexExpand[1/4 (8 + 8 I Sqrt[3] - 10 #1 - 10 I Sqrt[3] #1)] &, ComplexExpand[-4 + 5 #1] &}, {#1/25 &, (2 - #1)/25 &, (2 + #1)/ 25 &, (3 + #1)/25 &, (4 + #1)/25 &, (5 + #1)/25 &, (6 + #1)/ 25 &, (7 + #1)/25 &, (8 + #1)/25 &, (10 - #1)/25 &, (11 - #1)/ 25 &, (11 + #1)/25 &, (13 - #1)/25 &, (14 - #1)/25 &, (14 + #1)/ 25 &, (16 - #1)/25 &, (16 + #1)/25 &, (18 - #1)/25 &, (18 + #1)/ 25 &, (19 + #1)/25 &, (21 - #1)/25 &, (22 - #1)/25 &, (22 + #1)/ 25 &, (24 - #1)/25 &, (24 + #1)/25 &}] Here it finds the preimages of the simplest sextuple point: In[381]:= untrifil25[1/2 + I Sqrt[3]/10] Out[381]= {8/75, 11/75, 14/75, 17/75, 4/15, 23/75} --rwg

3 5

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

19 Oct '16

The animation I intended was perhaps too computationally ambitious. Meanwhile, gosper.org/FHilbert.gif is just conventional plots of the first 288 approximations. I dislike such plots due to the finite line thickness, which someone might imagine contributed to spacefilling. If you read all the frames into Preview, say, you can see that the texture of frame n repeats at frame 4n. This gives us a way to interpolate the nonexistent frame n+1/4 from frame 4n+1. Also uploaded: gosper.org/outcirc.gif made by flipping a sign in incirc.gif. --rwg Stay tuned for a Ptolemaic Hilbert sweep from a multi-hour computation. On 2016-09-26 18:42, James Propp wrote: > I hope Bill will write a lively document (or create a lively video) that > explains what's wrong with so many accounts of spacefilling curves. > > (I myself wish that more accounts started in a "Not Knot"-ish vein, > explaining why the "kindergartner's space-filling curve" --- scribbling > one's crayon back and forth until the square is filled --- isn't a solution > to the mathematician's problem.) > >> >> > 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". > > > I would like to see it. > > 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 > > > That's one way to look at it. But it depends on the notion of path-space > you use and what metric you put on it, doesn't it? In particular, it's > crucial to look at paths equipped with a parametrization. Then you really > can get convergence to a limit. And the limiting object is a continuous > function from a line segment onto a square. If you just look at the range > of a path and not the parametrization, you can't describe the square as the > limit in any meaningful way. Which I gather is part of Bill's point. > > Jim Propp > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

2 4

Re: [math-fun] The largest twin-primes known today...
by Bill Gosper 02 Oct '16

02 Oct '16

On 2016-09-21 04:29, Adam P. Goucher wrote: > I personally like Pollard's rho factorisation. Easy to implement (no > fancy sieves) and offers a quadratic speedup over trial division (so a > worst-case time complexity of sqrt(sqrt(N)) for factorising N). It's easy to like: fast, terse, and clever. But it just finds a factor rather than the full factorization, and doesn't prove primality. How tersely can we do *all* this if we settle for √n time complexity? --rwg > >> Sent: Wednesday, September 21, 2016 at 1:20 PM >> From: "Bill Gosper" <billgosper(a)gmail.com> >> To: math-fun(a)mailman.xmission.com >> Subject: Re: [math-fun] The largest twin-primes known today... >> >> On Wed, Sep 21, 2016 at 2:14 AM, Bill Gosper <billgosper(a)gmail.com> wrote: >> >> > I think Allan means 3^2, not 3^12. This would have been an extremely easy >> > factorization even for Lehmer's optical contraption >> > <https://en.wikipedia.org/wiki/Lehmer_sieve>. Or Macsyma back when it >> > trial-divided by consecutive odd numbers. Which is pretty much like >> > GCDing with >> > their product, now that we can store big numbers. I just wrote a tiny >> > (and >> > very untested) recursive program in a similar vein: >> > >> > In[832]:= Clear[dumfac]; dumfac@1 = {}; >> > dumfac[n_Integer] := (dumfac@n = {n}; >> > dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ >> > GCD[n, Binomial[#, Floor[#/2]] &@Floor[Sqrt[n]]]) >> > >> > In[833]:= dumfac[2996863034895] // tim >> > >> > During evaluation of In[833]:= 0.188517 sec, 5 >> > >> > Out[833]= {5, 3, 3, 18583, 3583757} >> > >> > In[834]:= PrimeQ /@ % >> > >> > Out[834]= {True, True, True, True, True} >> > --rwg >> > >> > Phew, that doesn't even slightly work! >> >> In[342]:= dumfac@11111111111111111 // tim >> >> During evaluation of In[342]:= 12.903538,1 >> >> Out[342]= {11111111111111111} >> >> Mindlessly changing a 2 to a 3, >> In[338]:= Clear[dumfac]; dumfac@1 = {}; >> dumfac[n_Integer] := (dumfac@n = {n}; >> dumfac@n = Join[dumfac[#], dumfac[n/#]] &@ >> GCD[n, Binomial[#, Floor[#/3]] &@Floor[Power[n, (2)^-1]]]) >> >> In[339]:= dumfac@11111111111111111 // tim >> >> During evaluation of In[339]:= 11.772568,2 >> >> Out[339]= {2071723, 5363222357} >> >> But 12 seconds! >> On 2016-09-21 03:04, Tom Karzes wrote: >> > Or you could just invoke the factor program that's part of GNU coreutils >> > and is part of a standard Ubuntu Linux install: >> > >> > % factor 2996863034895 >> > 2996863034895: 3 3 5 18583 3583757 >> > % >> > >> > See the info file for details. >> > >> > Tom >> > >> But the elephant in the room is Mathematica: >> In[320]:= FactorInteger[(10^59 - 1)/9] // tim >> >> During evaluation of In[320]:= 0.035899 sec, 2 >> >> Out[320]= {{2559647034361, 1}, >> {4340876285657460212144534289928559826755746751, 1}} >> --rwg >> >> > >> > On 2016-09-20 16:05, Allan Wechsler wrote: >> > > Factoris says the coefficient factors to 3^12.5.18583.3583757. >> > > >> > > On Tue, Sep 20, 2016 at 6:55 PM, Dan Asimov <asimov(a)msri.org> wrote: >> > > >> > >> P.S. I'm puzzled by this statement about these twin primes at that link: >> > >> >> > >> ----- >> > >> They will enter Chris Caldwell's “The Largest Known Primes Database” >> > >> (http://primes.utm.edu/primes) ranked 1st for twins, and each entered >> > >> individually ranked 4180th overall. >> > >> ----- >> > >> >> > >> Why do they have the same ranking overall? Does it not matter that >> > >> one is bigger than the other? >> > >> >> > >> —Dan >> > >> >> > >> >> > >> > On Sep 20, 2016, at 3:35 PM, Dan Asimov <asimov(a)msri.org> wrote: >> > >> > >> > >> > Is anything known about the factorization of that coefficient >> > >> > >> > >> > (other than its divisibility by 5 and 9)? >> > >> > >> > >> > Was it chosen as part of some algorithm that singled out relatively >> > >> > likely candidates? Or was it just stumbled on at random from a >> > >> > massive search? >> > >> > >> > >> > >> > >> > Or maybe one of our factoring experts can factor it? (You know who you >> > >> are.) >> > >> > >> > >> > —Dan >> > >> > >> > >> > >> > >> >> On Sep 20, 2016, at 3:18 PM, Eric Angelini <Eric.Angelini(a)kntv.be > >> > >> wrote: >> > >> >> >> > >> >> >> > >> >> ... are: >> > >> >> 2996863034895*2^1290000-1 >> > >> >> and >> > >> >> 2996863034895*2^1290000+1 >> > >> >> >> > >> >> http://www.primegrid.com/download/twin-1290000.pdf >> > >> >> > >> >

2 1

[math-fun] Iteration question
by David Wilson 02 Oct '16

02 Oct '16

Let f(n) = sigma(n) - n = sum of proper divisors of n. If you iterate f on positive integer n, some trajectories end at 0 (where you cannot continue, since 0 is not in the domain of f), some trajectories loop (e.g. 6 -> 6... or 220 -> 284 -> 220...). For other numbers, like 138, the trajectory seems to diverge. Can we prove that there exist divergent trajectories?

3 2

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

28 Sep '16

Symbolic computing environments (sometimes invisibly) provide prime streams, i.e. bursts of consecutive primes. Note that it is possible to compute detached chunks of Eratosthenes's sieve near a trillion, say, from a dense sieve reaching only a million. I wonder if for this new sieve there's a visually satisfying cellular automaton analogous to Dean Hickerson's http://www.conwaylife.com/w/index.php?title=Primer (with video) or Adam Goucher's remarkable #C 10-state rule that supports a 2-cell prime number generator. #C It uses a similar principle to Dean Hickerson's "Primer" pattern, #C only 60 times faster. The sieves remove every multiple of #C each integer, except for that integer: #C Calcyman (Adam P. Goucher), 18 May 2009 x = 1, y = 3, rule = Primer H2$I! color=1 255 0 0 color=2 0 255 0 color=3 255 128 128 color=4 128 255 128 color=5 128 128 128 color=6 192 192 192 color=7 128 128 255 color=8 128 255 255 color=9 255 255 128 n_states:10 neighborhood:Moore symmetries:none #State 0: Empty Space #State 1: Up spaceship #State 2: Down spaceship #State 3: Up spaceship on reflector #State 4: Down spaceship on reflector #State 5: Reflector #State 6: Reflector in initial state #State 7: NW spaceship #State 8: E puffer #State 9: SE puffer var a={0,1,2,3,4,5,6,7,8,9} var b={0,1,2,3,4,5,6,7,8,9} var c={0,1,2,3,4,5,6,7,8,9} var d={0,1,2,3,4,5,6,7,8,9} var e={0,1,2,3,4,5,6,7,8,9} var f={0,1,2,3,4,5,6,7,8,9} var g={0,1,2,3,4,5,6,7,8,9} var h={0,1,2,3,4,5,6,7,8,9} var i={2,4} var j={1,3,6} var k={0,1,2,4,5,6,7,8,9} 0,i,a,b,c,d,e,f,g,2 5,i,a,b,c,d,e,f,g,3 0,a,b,c,d,j,e,f,g,1 5,a,b,c,d,j,e,f,g,4 0,a,b,k,7,c,d,e,f,7 0,9,a,b,c,d,e,f,g,7 8,a,b,c,d,e,f,g,h,5 9,a,b,c,d,e,f,g,h,6 0,9,a,b,c,d,e,f,g,7 0,a,b,c,d,e,f,8,g,8 0,a,b,c,d,e,f,g,9,9 1,a,b,c,d,e,f,g,h,0 2,a,b,c,d,e,f,g,h,0 7,a,b,c,d,e,f,g,h,0 3,a,b,c,d,e,f,g,h,5 4,a,b,c,d,e,f,g,h,5 6,a,b,c,d,e,f,g,h,5 (Pix near end of http://gosper.org/g12a.pdf (100M!).) --rwg On 2016-09-27 12:41, Andy Latto wrote: > On Tue, Sep 27, 2016 at 11:51 AM, Henry Baker <hbaker1(a)pipeline.com> wrote: > >> So what will be the impact of this? > > I don't think it will have any practical or cryptographic effects, > though it may lead to other faster algorithms that do, or other > theoretically interesting algorithm improvements. >> >> Will we see cheaper, lower-power encryption devices? > > While many encryption algorithms start with "find a couple of large > primes", I don't think this is a significant part of the running time > of encryption algorithms. You can find candidates quickly by dividing > by a few small divisors, then checking that 2^(p-1) = 1 mod p, and > then only doing a full primality test for those that aren't ruled out > by these two fast tests, which will have you doing at most a couple of > full primality tests. Eratosthsenes' s sieve or improvements on it are > good for finding all the primes in a range fast, but even with the > improvements are slow compared to testing a single number for > primality. >> >> Or maybe quicker cracking times in brute force attacks? > > As far as I know, attacks care about fast factoring, not fast > primality testing or finding all of the primes in a range. > > Andy.latto(a)pobox.com

1 0

[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 27 Sep '16

27 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