July 2014 - mathfun@mailman.xmission.com

[math-fun] The lissajoke rolling on Bob Hearn's floor
by Thane Plambeck 15 Jul '14

15 Jul '14

I took a video of a metal version of Bill Gosper's lissajoke rolling on the floor at Bob Hearn's house ( http://gosper.org/lissajoke.gif ). Completely coincidentally, Bob Hearn is narrating its ambiguous rolling behavior as I'm pushing it around on the floor. Anyway, here is the video https://www.youtube.com/watch?v=7YpYCgRt9Qc&list=UUbBGpH5hVMFF23WjuaFzjcw The ambiguous rolling effect is quite noticeable when I push it farther away. -- Thane Plambeck tplambeck(a)gmail.com http://counterwave.com/

1 0

Re: [math-fun] Mildly surprising: The 2-sphere of radius 2
by Bill Gosper 15 Jul '14

15 Jul '14

On 2014-07-15 05:55, Henry Baker wrote: > Possibly relevant: > > arxiv.org/pdf/math/0101066 > > Beyond the Descartes Circle Theorem > Jeffrey C. Lagarias > Colin L. Mallows > Allan R. Wilks > AT&T Labs, Florham Park, NJ 07932-0971 > (January 8, 2001) > ABSTRACT > > The Descartes circle theorem states that if four circles are mutually > tangent in the plane, with > disjoint interiors, then their curvatures (or “bends”) b i = 1 r i > satisfy the relation (b 1 + b 2 + b 3 + b 4 ) 2 = 2(b 21 + b 2 2 + b 2 > 3 + b 2 4 ). "Four circles to the kissing come, ..." http://www.pballew.net/soddy.html Also http://www.tweedledum.com/rwg/Sodddy.htm If only we still had Thurston. --rwg > We show that similar relations hold involving the centers of > the four circles in such a configuration, coordinatized as complex > numbers, yielding a complex > Descartes Theorem. These relations have elegant matrix generalizations > to the n-dimensional > case, in each of Euclidean, spherical, and hyperbolic geometries. > These include analogues of > the Descartes circle theorem for spherical and hyperbolic space. > AMS Subject Classification (2000): 52C26 (Primary) 11H55, 51M10, 53A35 > (Secondary) > Keywords: Apollonian packing, circle packings, inversive geometry, > hyperbolic geometry, > spherical geometry > > Also > > R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, > Apollonian Packings: > Geometry and Group Theory I. The Apollonian Group, eprint: arXiv math.MG/0010298 > R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, > Apollonian Packings: > Geometry and Group Theory II. Super- Apollonian Group and Integral > Packings, eprint: arXiv math.MG/0010302 > R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, > Apollonian Packings: > Geometry and Group Theory III. Higher Dimensions, eprint: arXiv math.MG/0010324 > R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, > Apollonian Circle > Packings: Number Theory, eprint: arXiv math.NT/0009113 > > At 10:59 AM 7/14/2014, Bill Gosper wrote: >>(at the origin) bisects the unit 2-sphere at (1,1,1): >>Graphics3D[{Sphere[{0, 0, 0}, 2], Sphere[{1, 1, 1}]}, PlotRange -> {{0, 2}, >>{0, 2}, {0, 2}}] >>gosper.org/2spheres.png >>--rwg >

1 0

Re: [math-fun] digital money
by Dave Dyer 15 Jul '14

15 Jul '14

At 12:21 PM 7/14/2014, Eugene Salamin via math-fun wrote: >Why is Bitcoin trustworthy? Money is based on the theory that the value you assign to something today will be similar to the value someone else assigns to it in the future, so it's safe to trade something you value (your time, your house) for money, instead of a direct barter for something else you value (ie; "will work for food") Producing gold requires a lot of work, and the gold itself is durable and portable; which is why gold is traditionally a trustworthy measure of stored value. Similarly creating a bitcoin requires a lot of work. The cleverness in the bitcoin system is that the "work" is intimately linked to the process of recording and verifying transactions in bitcoin.

2 1

Re: [math-fun] Mildly surprising: The 2-sphere of radius 2
by Henry Baker 15 Jul '14

15 Jul '14

Possibly relevant: arxiv.org/pdf/math/0101066 Beyond the Descartes Circle Theorem Jeffrey C. Lagarias Colin L. Mallows Allan R. Wilks AT&T Labs, Florham Park, NJ 07932-0971 (January 8, 2001) ABSTRACT The Descartes circle theorem states that if four circles are mutually tangent in the plane, with disjoint interiors, then their curvatures (or bends) b i = 1 r i satisfy the relation (b 1 + b 2 + b 3 + b 4 ) 2 = 2(b 21 + b 2 2 + b 2 3 + b 2 4 ). We show that similar relations hold involving the centers of the four circles in such a configuration, coordinatized as complex numbers, yielding a complex Descartes Theorem. These relations have elegant matrix generalizations to the n-dimensional case, in each of Euclidean, spherical, and hyperbolic geometries. These include analogues of the Descartes circle theorem for spherical and hyperbolic space. AMS Subject Classification (2000): 52C26 (Primary) 11H55, 51M10, 53A35 (Secondary) Keywords: Apollonian packing, circle packings, inversive geometry, hyperbolic geometry, spherical geometry Also R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, Apollonian Packings: Geometry and Group Theory I. The Apollonian Group, eprint: arXiv math.MG/0010298 R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, Apollonian Packings: Geometry and Group Theory II. Super- Apollonian Group and Integral Packings, eprint: arXiv math.MG/0010302 R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, Apollonian Packings: Geometry and Group Theory III. Higher Dimensions, eprint: arXiv math.MG/0010324 R. L. Graham, J. C. Lagarias, C. L. Mallows, A. Wilks and C. Yan, Apollonian Circle Packings: Number Theory, eprint: arXiv math.NT/0009113 At 10:59 AM 7/14/2014, Bill Gosper wrote: >(at the origin) bisects the unit 2-sphere at (1,1,1): >Graphics3D[{Sphere[{0, 0, 0}, 2], Sphere[{1, 1, 1}]}, PlotRange -> {{0, 2}, >{0, 2}, {0, 2}}] >gosper.org/2spheres.png >--rwg

1 0

Re: [math-fun] digital money
by Keith F. Lynch 14 Jul '14

14 Jul '14

Would the people posting about Bitcoins please learn something about them first? For instance the computation necessary to produce one scales with how much computer power is being used to produce them, so they can't be inflated away by any increase in computing power. The simplistic labor theory of value is part of Marxism. Nobody but Communists has taken it seriously in more than a century. Plenty of things other than labor are of great value, and plenty of labor is of no value or even of negative value. And please learn how to quote correctly. Much of the time I can't figure out who is saying what. Today, someone quoted an *entire digest* at the *bottom* of his post, and them someone else replied to him, quoting his entire message, including his quoting of that entire digest *again*. The purpose of quoting is to establish context, so that you don't have to paraphrase. A good rule of thumb is to never quote more than you'd be willing to type if automatic quoting wasn't available. And always quote it *above* your reply to that paragraph, since English is read top to bottom, not bottom to top. Use angle brackets to indicate quoted text. And read your whole post before sending it, to make sure you're not doing something you don't intend to. Thanks.

1 0

[math-fun] digital money
by Warren D Smith 14 Jul '14

14 Jul '14

> Warren Smith wrote: > Chaum (subject to reasonable conjectures) had that property. Bitcoin, > on the contrary, has the property that I can steal your money by > simply outcomputing you, and with no need > for me to exponentially outcompute you. APG: No, you can only steal my money if you can outcompute the sum of the rest of the world's computing power. And if you can do that, then you may as well just mine bitcoins instead, as your profit will be substantially greater. --oh. I had not realized that. But let's assume that is true; this is (a) still far weaker assurance than exponential time (b) still requires computing forever to protect money even if you never use a cent (c) supposedly there will be at most 21 million bitcoins, and if we believe the NSA owns 21 million computers, then, uh... doesn't that mean the NSA can totally dominate everything bitcoin? And let's say the NSA is not interested in making "substantially greater profit"; instead they are interested in power. (d) bitcoins can be stolen, but I thought Chaum's money was unstealable. Question: is the entire record of who-paid-who-when publicly accessible with bitcoins? If so, this is in some ways good, but in other ways a privacy disaster, e.g. "big brother." >Why is Bitcoin trustworthy? Dave Dyer: Money is based on the theory that the value you assign to something today will be similar to the value someone else assigns to it in the future, so it's safe to trade something you value (your time, your house) for money, instead of a direct barter for something else you value (ie; "will work for food") Producing gold requires a lot of work, and the gold itself is durable and portable; which is why gold is traditionally a trustworthy measure of stored value. Similarly creating a bitcoin requires a lot of work. The cleverness in the bitcoin system is that the "work" is intimately linked to the process of recording and verifying transactions in bitcoin. --WDS: well, first of all, the cost of computing has changed by, like, a factor of 10^6 over my life. That means gold is way more stable in terms of inherent value in terms of labor, no? Second, it is just a fact that the value of bitcoins has changed tremendously over time, far more so than gold, right? So it has already failed hugely by those desiderata? But there is an analogy -- nobody can trivially create more gold, unlike paper money. Ditto bitcoins. Both have that advantage over paper money. But it has been far easier to obtain gold some places and times than others, another reason it did not work too well. But: with gold, that meant lots of human labor was wasted mining gold for no reason. Pollution, energy consumption. It was a stupid waste. Ditto for "mining" bitcoins. And bitcoins are worse because everybody can be a bitcoin miner but only a few could be gold miners, which means there will be more waste; and also gold mining creates more gold, but bitcoin mining will be required even in a planned era of no further bitcoin creation. There is a simpler solution (which I proposed many years ago, not that anybody listened; and this may have been proposed by others too): tie money directly to the ultimate measure of "value": human labor. Specifically, make a law saying there is a minimum wage of $1 per hour, and a maximum wage of $10000/hour (say), and these two numbers are fixed. Now actually, a hard maximum is not needed, just a progressive income tax that goes to 100% asymptotically on a fixed curve. Anyhow, if we really had those laws and they really were unchangeable (and money could not be counterfeited), then it seems to me money would be inflation-proof. A big "if", but that would be all that would be needed. Right now there is no relation between the value of money and the value of human labor aside from habit/tradition. If tomorrow it were declared that all wages and all prices were to double, we'd go on just as before, just moving money at twice the flow-rate. That proves nothing sets the scale and that the total quantity of money is irrelevant. I think lots of the stuff many economists say about the value of money (and other things) is hogwash. APG: There's no central authority. WDS: What is so horrible about needing a "trusted central bank"? For many purposes that might well be a good, not a bad, thing.

1 0

[math-fun] digital money
by Warren D Smith 14 Jul '14

14 Jul '14

God almighty, APG says bitcoin currently uses half the world's computing cycles??? And it isn't even very popular at present??!!?! What a nightmare. What an utterly colossal epic fail for humanity. That's worse than the "gold standard" was. See papers underlying "digicash" digital money by David Chaum et al for something actually comparatively sensible, though his company digicash ended up failed. [I do not think you can replace the PKC inside with some lattice based "post quantum" PKC, it is not that simple, sorry.] If you can figure out how to produce quantum-immune digital money with properties like Chaum had, that I think would be an excellent accomplishment. I used to think quantum computers would never happen, but they are worrying... On 7/14/14, math-fun-request(a)mailman.xmission.com <math-fun-request(a)mailman.xmission.com> wrote: > Send math-fun mailing list submissions to > math-fun(a)mailman.xmission.com > > To subscribe or unsubscribe via the World Wide Web, visit > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > or, via email, send a message with subject or body 'help' to > math-fun-request(a)mailman.xmission.com > > You can reach the person managing the list at > math-fun-owner(a)mailman.xmission.com > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of math-fun digest..." > > > Today's Topics: > > 1. Re: "period" 6 (Dan Asimov) > 2. Post-quantum proof-of-work system? (Warren D Smith) > 3. Shanks' 707 digits (James Propp) > 4. Re: Shanks' 707 digits (Hans Havermann) > 5. Warren Smith versus Bitcoin (was Re: Post-quantum > proof-of-work system?) (Adam P. Goucher) > 6. Mildly surprising: The 2-sphere of radius 2 (Bill Gosper) > 7. Re: Mildly surprising: The 2-sphere of radius 2 (Tom Rokicki) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Sun, 13 Jul 2014 22:46:27 -0700 > From: Dan Asimov <dasimov(a)earthlink.net> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] "period" 6 > Message-ID: <8536A091-E207-47F1-8975-ACEC97915CAE(a)earthlink.net> > Content-Type: text/plain; charset=utf-8 > > This has to be due to the Pisotudinousness of GoldenRatio, > and the +-1 slope of Sin at multiples of Pi. > > --Dan > > > On Jul 13, 2014, at 10:33 PM, Bill Gosper <billgosper(a)gmail.com> wrote: > >> On Sun, Jul 13, 2014 at 8:57 PM, Bill Gosper <billgosper(a)gmail.com> >> wrote: >> >>> In[360]:= >>> Table[GoldenRatio^n*Sin[?*GoldenRatio^n] // N[N[#, 99]] &, {n, 69, 105}] >>> >>> Out[360]= {3.14159, 3.14159, >>> -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, >>> -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, >>> -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, >>> -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, >>> -3.14159, -3.14159, -3.14159, 3.14159, 3.14159, 3.14159, >>> -3.14159, -3.14159, -3.14159, 3.14159, 3.14159} >>> --rwg >>> >> >> Whereas >> In[362]:=Table[ >> (Sqrt[2] + Sqrt[3])^n*Sin[?*(Sqrt[2] + Sqrt[3])^n]/? // N[N[#, 99]] &, >> {n, 69, 105}] >> >> Out[362]= {6.81476*10^33, >> -1., 6.77788*10^34, -1., -4.89061*10^35, -1., -2.09519*10^36, >> -1., -4.56286*10^37, -1., -4.59961*10^38, -1., -3.15805*10^39, >> -1., 5.68896*10^40, -1., 2.91069*10^41, -1., -2.724*10^42, >> -1., -4.32617*10^43, -1., -4.06476*10^44, -1., 4.21738*10^44, >> -1., 6.08704*10^46, -1., 5.32596*10^47, -1., 1.94754*10^48, >> -1., 5.52776*10^49, -1., -5.72711*10^50, -1., -5.86847*10^51} >> --rwg >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > > ------------------------------ > > Message: 2 > Date: Mon, 14 Jul 2014 09:53:21 -0400 > From: Warren D Smith <warren.wds(a)gmail.com> > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] Post-quantum proof-of-work system? > Message-ID: > <CAAJP7Y04wnTcOFiTQyo61wxZC=caXWLJjprunkW4-t_JtQn3sw(a)mail.gmail.com> > Content-Type: text/plain; charset=ISO-8859-1 > > If you were not worried about having exponentially large memory for a > classical computer I suppose to be fair we should allow this for a > quantum computer too. > > In that case, you could have the quantum computer seek 2^(n*C) > words, at least two of which agree about the first n bits of their hash. > This has probability of occurrence that is of order 2^(-max(1-2*C, 0)*n) > if random words are tried. > > Now there are versions of Grover search algorithm, which run in expected > #steps proportional to about squareroot(1/p) where p=probability of > occurrence. > If time for a step is here 2^(n*C), then > total time is of order > 2^( (C + max(1-2*C,0)) * n ) > which is optimized by choosing C=1/3, > which causes the quantum runtime to be of order > 2^( n*2/3 ). > > So... no. The quantum computer here is faster than the classical > algorithm, > so Adam Goucher's proposal only partially worked. > > While I'm at it, I think bitcoin is incredibly stupid and cannot believe > anybody > wants to use it. It is an embarrassment to humankind. > Far far better proposals for digital money based on > public key cryptography have been made, and made well before the > idiots who came up > with bitcoin too, and they do NOT require any > idiots to keep on grinding for ages and to prove they did (which, if > bitcoin really > caught on, would be a huge consumer of power forever). Instead, when > using money > you just do one polynomial time computation then stop, confident you > will never be breakable unless PKC is broken. > > These still will be busted by quantum computers though (which bust the > PKC schemes that were used). > > > > ------------------------------ > > Message: 3 > Date: Mon, 14 Jul 2014 10:27:46 -0400 > From: James Propp <jamespropp(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: [math-fun] Shanks' 707 digits > Message-ID: > <CA+G9J-ea4sNTtaE42OS9Y6qOjMUawx9GOQt8BvV-OrYt-CuKuQ(a)mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > Does anyone know what precise error (or errors) William Shanks made? > > (see http://en.m.wikipedia.org/wiki/William_Shanks) > > E.g., if you take the difference between Shanks' 707-digit approximation to > pi and the 707-digit truncation of pi, do you get the initial digits of > some rational number? > > Jim Propp > > > ------------------------------ > > Message: 4 > Date: Mon, 14 Jul 2014 11:39:11 -0400 > From: Hans Havermann <gladhobo(a)teksavvy.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Shanks' 707 digits > Message-ID: <DEB3E289-2825-4101-9EDC-783C887976FC(a)teksavvy.com> > Content-Type: text/plain; charset=us-ascii > > http://www.engert.us/erwin/miscellaneous/William%20Shanks%20707%20digits.pdf > > I believe the "707 digits" refers to decimal places. The first 527 > (excluding typos) were correct. I think your difference is > 696972233400402414486921529175050301808106570457226115312565026347185368614269829439388229424273703513612402766518096376765306056957758635728165741884423700490282252529162636899/10^706. > > > On Jul 14, 2014, at 10:27 AM, James Propp <jamespropp(a)gmail.com> wrote: > >> Does anyone know what precise error (or errors) William Shanks made? > >> E.g., if you take the difference between Shanks' 707-digit approximation >> to >> pi and the 707-digit truncation of pi, do you get the initial digits of >> some rational number? > > > > ------------------------------ > > Message: 5 > Date: Mon, 14 Jul 2014 19:22:35 +0200 > From: "Adam P. Goucher" <apgoucher(a)gmx.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: [math-fun] Warren Smith versus Bitcoin (was Re: Post-quantum > proof-of-work system?) > Message-ID: > <trinity-8cfeb0c9-5cca-47a7-b056-2322f5ef4d06-1405358555663@3capp-mailcom-bs05> > > Content-Type: text/plain; charset=UTF-8 > >> Warren Smith wrote: >> >> While I'm at it, I think bitcoin is incredibly stupid and cannot believe >> anybody wants to use it. It is an embarrassment to humankind. > > ?! > > Have you read the original paper? It's quite a beautiful system. > > >> Far far better proposals for digital money based on >> public key cryptography have been made, and made well before the >> idiots who came up >> with bitcoin too, and they do NOT require any >> idiots to keep on grinding for ages and to prove they did (which, if >> bitcoin really >> caught on, would be a huge consumer of power forever). > > It already uses about half of the world's computing power, apparently. > Of course, one can replace the proof-of-work system with something > different (and useful), such as how PrimeCoin resulted in vast quantities > of Cunningham chains being discovered. > > Basically, the proof-of-work can be anything that's in NP but not in P. > And ideally we don't want quantum computers to be vastly better than > classical computers, although it doesn't matter too much when quantum > computers go mainstream (since then the `honest nodes' will again have > more processing power than `attacker nodes'). > > >> Instead, when using money you just do one polynomial time computation >> then stop, confident you will never be breakable unless PKC is broken. > > How do you prevent double-spending without either a proof-of-work-driven > blockchain (a la Bitcoin) or a centralised server (in which case the > owners can cheat)? > > >> These still will be busted by quantum computers though (which bust the >> PKC schemes that were used). > > It's fairly easy to replace every instance of `elliptic curve DSA' with > `lattice-based cryptography' to make a public-key cryptosystem resistant > to quantum computers. > > >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > > > > ------------------------------ > > Message: 6 > Date: Mon, 14 Jul 2014 10:59:11 -0700 > From: Bill Gosper <billgosper(a)gmail.com> > To: math-fun(a)mailman.xmission.com > Subject: [math-fun] Mildly surprising: The 2-sphere of radius 2 > Message-ID: > <CAA-4O0FJ=2ud3APigxd-y+zO-KYNMzP9aUNZS=KLTwKWrv3BCA(a)mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > (at the origin) bisects the unit 2-sphere at (1,1,1): > Graphics3D[{Sphere[{0, 0, 0}, 2], Sphere[{1, 1, 1}]}, PlotRange -> {{0, 2}, > {0, 2}, {0, 2}}] > gosper.org/2spheres.png > --rwg > > > ------------------------------ > > Message: 7 > Date: Mon, 14 Jul 2014 11:06:23 -0700 > From: Tom Rokicki <rokicki(a)gmail.com> > To: math-fun <math-fun(a)mailman.xmission.com> > Subject: Re: [math-fun] Mildly surprising: The 2-sphere of radius 2 > Message-ID: > <CAGia-=UJ2DgmaUk3vn26Y__3ae5G764Qh+YNNRMEiBbGBApnmg(a)mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > Nice! > > On Mon, Jul 14, 2014 at 10:59 AM, Bill Gosper <billgosper(a)gmail.com> wrote: >> (at the origin) bisects the unit 2-sphere at (1,1,1): >> Graphics3D[{Sphere[{0, 0, 0}, 2], Sphere[{1, 1, 1}]}, PlotRange -> {{0, >> 2}, >> {0, 2}, {0, 2}}] >> gosper.org/2spheres.png >> --rwg >> _______________________________________________ >> math-fun mailing list >> math-fun(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > > -- > -- http://cube20.org/ -- http://golly.sf.net/ -- > > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > > > ------------------------------ > > End of math-fun Digest, Vol 137, Issue 20 > ***************************************** > -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

4 6

[math-fun] Mildly surprising: The 2-sphere of radius 2
by Bill Gosper 14 Jul '14

14 Jul '14

(at the origin) bisects the unit 2-sphere at (1,1,1): Graphics3D[{Sphere[{0, 0, 0}, 2], Sphere[{1, 1, 1}]}, PlotRange -> {{0, 2}, {0, 2}, {0, 2}}] gosper.org/2spheres.png --rwg

3 2

[math-fun] Post-quantum proof-of-work system?
by Warren D Smith 14 Jul '14

14 Jul '14

If you were not worried about having exponentially large memory for a classical computer I suppose to be fair we should allow this for a quantum computer too. In that case, you could have the quantum computer seek 2^(n*C) words, at least two of which agree about the first n bits of their hash. This has probability of occurrence that is of order 2^(-max(1-2*C, 0)*n) if random words are tried. Now there are versions of Grover search algorithm, which run in expected #steps proportional to about squareroot(1/p) where p=probability of occurrence. If time for a step is here 2^(n*C), then total time is of order 2^( (C + max(1-2*C,0)) * n ) which is optimized by choosing C=1/3, which causes the quantum runtime to be of order 2^( n*2/3 ). So... no. The quantum computer here is faster than the classical algorithm, so Adam Goucher's proposal only partially worked. While I'm at it, I think bitcoin is incredibly stupid and cannot believe anybody wants to use it. It is an embarrassment to humankind. Far far better proposals for digital money based on public key cryptography have been made, and made well before the idiots who came up with bitcoin too, and they do NOT require any idiots to keep on grinding for ages and to prove they did (which, if bitcoin really caught on, would be a huge consumer of power forever). Instead, when using money you just do one polynomial time computation then stop, confident you will never be breakable unless PKC is broken. These still will be busted by quantum computers though (which bust the PKC schemes that were used).

2 1

[math-fun] Shanks' 707 digits
by James Propp 14 Jul '14

14 Jul '14

Does anyone know what precise error (or errors) William Shanks made? (see http://en.m.wikipedia.org/wiki/William_Shanks) E.g., if you take the difference between Shanks' 707-digit approximation to pi and the 707-digit truncation of pi, do you get the initial digits of some rational number? Jim Propp

2 1