Little math problem(s) November 2020

[pier4r]

Reading the library of babel (n1, n2) was a pleasure.
Thinking about it, I was interested to know what one could represent with all the possible permutations of a finite number of symbols in a finite amount of places.

I didn't investigate much on the part where one introduces a protocol external to the representation (that is, a protocol that is not represented within the permutations but it is used to give meaning to a combination of permutations); but without any of this one should not be able to represent infinite processes that are not periodical.

Now let's say we have a book containing 1 million characters (for simplicity, be it those visible on a standard PC US keyboard, not even ASCII). If we want to represent PI we should have at least one book explaining the procedure, then books having all the possible permutations of numbers up to 1 million slots, then indexes of indexes that tell us the order how to read those books one after another to construct PI.

Since PI is infinite and not periodical, if I am not mistaken we should run out of possible valid permutations that could help forming the indexes. In other words we run out of space to construct the tree or chain of indexes to construct PI. If we could have infinite indexes then we could construct PI even with finite permutations because it is how we are doing it currently. Indeed we use only 10 digits, only the order of those needs to have infinite space.

Aside from infinite processes, I thought that finite ones should be representable. But then thinking a bit more I am not sure.

Shrinking the example. Imagine we have 4 bytes, all the permutations of those 4 bytes. Thus we have 2^32 possibilities.
Now imagine we have a protocol (admittedly external to the representation) where we want to represent a large number (thus finite) combining the available permutations of the 4 bytes in a certain order.

To do this we add an external source of data (that we shouldn't add). A collection of 1000 (or 10k or 100k or an arbitrary large finite collection) addresses (could be hex form, decimal, binary or whatever other format) that tell us which of those 2^32 combinations to pick to construct the number, in order. Left to right.

The point being, with 1000 (or any other finite number N) addresses one could map binary numbers up to 2^32000 (accordingly, 2^(32*N) ) but not all of them.

Thus, if I am not mistaken, even with the limits of the library of babel. Having all the permutations of 1 million characters (or more), one can catch a lot of content (indeed even this very comment), but not necessarily all that is possible. Though it is really interesting to see that a vast quantity of things that can be discovered (or "invented" ) is already there. Only it costs less to rediscover them from scracth rather than going through the library itself.

Am I missing something? What is your take on it?

n1: https://www.hpmuseum.org/forum/thread-15921.html
n2: https://en.wikipedia.org/wiki/The_Library_of_Babel
n3: Almost this very comment https://libraryofbabel.info/browse.cgi book -> Volume 2 , page 67 , on Shelf 4 of Wall 2 of Hexagon:

Code:


1vc1kaviswpm2xjiltx3m06uzj6wsekm53ebui6kq16gjyguprvhe41rmcepp7n527m1juqmxsbzfu2o​zq4fh1qz9i7qkc59ly4x8evknwiqjumzmyevzqodhcril65fb8231ywf0alrtjdsi0b0x7beti3asiw5​nuxf4t0aknprmzo6ofdvaeq39rvfftlrzw0chnsp6ge7hnxywrgwf31ur2wuiz2wfvl4buc4hg18abd8​xezntolzlw41z6wn1wcyj9bh4ed4ppvirqo4rge49r4pktogser0rnbiegwcxl47tgusspu2ehoszas0​h16cqafg5emhmvhdmo4uvs2do3llw4p1e0k1ztn4lmlj6g69g67ufdyzoy5e8kfrl7allixcar6w6w5b​9fu5sn6xjvegcaevxnvnhsyxsvu4so4assv5u9n1jr3ygdu35yxnc5k0nemhe0yz2w4kk34br3rqw7b4​4p5frggx7v07eiwoxvepd4objjc7sjh2br1togamk780ineu8q8jogqsnaukgppe41zzsafowgsfl3zw​26p6g8e1tqw7d2tpb409xxasrbewrdnld0sxewegamkqh2nutt3uqo4hes2n6vgkijsy0vxotuqsr5i4​8b5tcxtpip6ei2qw1f1o25k3fncd9q0b4xohhutg35gzdwzx6rdk7o84w109i7xnvq4ywmc19zb2qkje​rmxpb2dts7q7tks6sbypzx7y8ls7o3yeshyimoxn1mzxnh39wd8vbaeleqjsxox1pvlp5fv991nd4tro​lud62ptpuziwvwho7epieo0m2i9cv2ruz40jsfi9zc5wsybzquk203vzxl4t00abnzkz9r2okus77x23​6z3n75nxzywjgj6wagrje5rmvcughwzomjqupjjhdb3ja4sruwhiao8jewkvfwax7zl72g5q35arp288​a82w3q1ok9dg0g6qujya9hf4lmx7pdymui1wq814w3wwacdtqbxq1z4pz0uzx4jvhbqgrors7dev63qo​ayqcbkwpalwuf9mqwqw53n3mcx0pymlz0j9xuwb3ke69xn75lq9dm8lt7okt4mk4xhnjk8adkhe4o5fp​hxg3hjhqzj6ewlysiujmb3m333q7vg5kxbgfewimm1uslsg2v1swuldkifwn5yfka6tgy1j2mwfw76ll​1mzz3f0eyqs24jqdl8bf1lllk3irgrj6tfw9f7g55yu4ssec5poetopz978kpecof1kx90f10gulwa8y​hpyo4uebz9kfwocieocap0i6sl0e7eri1974zwzp5h72n101c9op5x052az0a8dw7huk5x7qc9ulsy27​2qg2jjgmiro9ig40f561rzsuzlpnn16mn3pef7eqjucv3kedqlmoex0h60zcyl5wl37rz8nrv8exsx1r​ojd0ej5fy8qinxq2d7ryb47mwc2van704xno0o97evysuxhvzez4epj4c013rro5ntmiavbkntc7l4ng​t4d7f9t7n1kb9brrgkqj2ynrr6l5984frod7lcdoqlocu3rzqwe1rvvruykvb2cluz7hdi19evmp9gw9​mx9pn3sauen3dv0f2m9bfwcqz6rbxkazufkhsbzep4ojflj08cx5jkdbj8soyzjzcgzd8e7brobvpd5q​cz4xl8kdue6o3ep7gdb1ivv98relcc5ubdpbzl3a4dmlrl46av3wyq4g9ooxhq7k8fn05y3bed6k2ovi​3g3d4z6vn7lsnmvpajlqcq1uil2s1e40wvtuv76wyf41i1riyh1jb623ks4flif38w5ok0ieiwko5qp8​jz3dssdff0pq93pe387a5h9xhivrbnr6kjsgzqquq9vwdsbq26mkukp4oo5plr6wbpfpq98hz6jvygxn​xxi3iu0q04zajrd2x5n4zy7ko1wvawb2gbhoqx0bsi9pg7mini5u6x4spq89b4849ihi4zjxisqvb41b​qmtcc0qsp7f0fxgglkwvbkjrmy07ax0fp8w0w76da1nsfm79pedo0st1o5m2itykkpswwmfgj34mlkhw​5523ah7c9s49p2tot18jv395fu9kpbhropml5ti8nco060lajmwcxp3idvfzp74l9bj8y7fdr45yf8hn​4e9s8awe326gu3qa1xdglektpuxitp4jgplc1gj5qj1fo98th0kdkzpyt5xludcbmkckss34l1nqvet3​nxbek2enrkaw8avsolyrn07zje052bj1fskkvabdg0tvtlzexo19sjhfhanoqkgryt75mud6i7giatgv​vjlxov6i9w4kzjjbjfedua1t1ehm4dnaixiwwm3g1kdv8q51ezmn2vsma261re23qs3r5ydf1k13tui6​qpq81wwa64r9sp5uawl7vw9yxopq8al2ikq9k16hitle6t074ql72strkf2c61tsovhns5njarsgxudm​ad52ol2j00213hjn10ffz21rb0h9dhblq1j01t2za4na8l0uwvp21l11sv7n2jjkexz5xrjalxqys8je​3n9v3hjf3ds8ovkbqya8ofxq8h3zcmrvy2bsvkqlmurf3v2u1iphqwubsd3dl90eifr9psbpat6ypudw​45kaxxq3cym81oj9ybx39jxjr2ova4pjnqaj3k1lbj2qcfllyz0n9trl8bkwrpsft29mq01blq79aofx​dxrvruzk7s8ls1sj1q9f4st2r2og7qrc5p470mrhrihniubundru2pwtvcprx3bgkgscll7f4dsujqcj​qfgs3h7gdfe8w0n9g2s15fzhwo022zp8vx3nlthswehipthnl8ok6qwmpqpxteyulkv9qc9o0ynn3zid​rvm65ifxt31knb14vujxmz58ee24gylp8ft8ihb8z7xre9swyhehopap81h3cef60t8gdq3khghk0au7​dmoeywa96s6r9uet808bysidbuv4auc7x56ba7eof58l8nq7n3gcphkpadqpzvwuzki2y4cszz5o64mo​5b9dchhoieuskxtqxbnszwuw6ycelqacieywgresdvf4nxegj2yborzinmyco960ukxolwxxynt3ck96​8se1u7dvirw1wq26vwof0yyfgt5m0hw16i4a08saj72i53kjhztr104w7cn4ti0esvspvpnw1goidmzs​imxbtq3mtm2h4u8rj0v47mjzs7mfve712j34cfvym4xgrl5swdgnac

# I know that this is generated on the fly. But had the library been there, like in a platonic world, it had contained that information ab aeterno

[ttw]

You are correct. One quickly runs out of room to store lists like permutations. It's possible to store (for example) 2^32 different symbols in 32 bits. However, there are (2 ^32)! permutations.

[EdS2]

It's a pity really, if the best work of fiction ever happens to require 1000001 characters. (1001 Nights springs to mind, and it might well be longer than that...)

[Paul Dale]

I'm sure that this isn't optimal and it certainly doesn't fit into 4 bytes:

\(\pi=\sqrt{6\zeta(2)}\)


It's still a pretty neat formula.


Pauli

[grsbanks]

(11-21-2020 10:10 AM)Paul Dale Wrote:  \(\pi=\sqrt{6\zeta(2)}\)

I used that here

http://techy.horwits.com/2020/09/using-r...ue-of.html

[pier4r]

(11-21-2020 09:59 AM)EdS2 Wrote:  It's a pity really, if the best work of fiction ever happens to require 1000001 characters. (1001 Nights springs to mind, and it might well be longer than that...)

Tha wouldn't be a problem as one could use a book as a catalog, and two books for the content.

My point was that even with finite content, one runs out of space to compile the entire catalog even with a very large space.

[BillBee]

Ironically, I saw "The Name of the Rose" last night. That was one crazy library.

-B

[Albert Chan]

(11-21-2020 10:45 AM)grsbanks Wrote:  

(11-21-2020 10:10 AM)Paul Dale Wrote:  \(\pi=\sqrt{6\zeta(2)}\)

I used that here

http://techy.horwits.com/2020/09/using-r...ue-of.html

Instead of random number simulation, we can also do brute force.
Probability of a,b co-prime to each other (1 ≤ a,b ≤ n) = (number of co-primes pairs) / n^2

Number of co-prime pairs = sum(sum(gcd(x,y)==1, y=1 .. n), x=1 .. n)

We can simplify with symmetry: gcd(x,y) = gcd(y,x), gcd(x,x) = x:

XCAS> sum(sum(gcd(x,y)==1, y=1 .. x-1), x=1 .. n) * 2 + 1             (*)

+1 is due to under-counted gcd(1,1) = 1 (1 is co-prime to all integers)
We could also include the diagonal, and remove the over-counted gcd(1,1).

XCAS> sum(sum(gcd(x,y)==1, y=1 .. x), x=1 .. n) * 2 - 1

Inside sum is Euler totient function. (ref: "C++ for Mathematicians", page 67)

XCAS> P(n) := (sum(Phi(x), x=1 .. n) * 2. - 1) / n^2
XCAS> estimated_Pi(n) := sqrt(6./P(n))

XCAS> estimated_Pi(200)      → 3.13220921695, error = 0.2987%
XCAS> estimated_Pi(1e3)      → 3.14041534038, error = 0.0375%       (**)
XCAS> estimated_Pi(1e4)      → 3.14153423902, error = 0.0019%
XCAS> estimated_Pi(1e5)      → 3.14158477584, error = 0.0003%       // on my laptop, this take 2 seconds

(*) XCas sum(f(x), x=a .. b) had weird meaning if a > b+1
If a = b+1, result is 0
If a > b+1, result is -sum(f(x), x=b+1 .. a-1)       // see XCas sum limit confusion

(**) the blog wrongly stated for n=1000, error = 0.06%