Subject: [math-fun] A simple naive question From: Éric Angelini <bk263401@skynet.be> Date: 3/10/20, 1:30 PM To: math-fun <math-fun@mailman.xmission.com>
Hello Math-Fun, I would like to transmit two _composite_ numbers A and B in the form of single number C. How can I do that?
For instance, if Alice concatenates A et B, Bob will have a problem in reconstructing those numbers out of C: A = 865445 B = 12377007 C = 86544512377007
Is there a clever, economic way to say where C must be split? Or do you know another technique (dealing perhaps with prime numbers)? This has nothing to do with cryptography (I guess) -- just a (silly) question. Best, É. Hi Éric--
Here's a technique that is economical (but only in the number of bits) and (as it happens) does have to do with prime factoring. This is just the intro, table of contents, and the basic definition. I hope the latex-flavored markdownisn't too hard on the eyes, I will work on putting a PDFsomewhere tomorrow. Charles R Greathouse IV and (indirectly) Richard Sladkey are referred to later in the body. I like Cantor's pairing because it's "mathy." But with Cantor and with the interleaving-digits way, the size of the final thing is twice the size of the *max* of the two inputs. Someone mentioned 2^x 3^y. Very compact (to describe). I have always admired Goedel's tuple-encoding function: 2^a 3^b 5^c 7^d 11^e... What's the word for that? Profligate? Hubristic? I like the BCD digits punctuated by a hex 'A' because it's roughly the size of the concatenation. But... what'sthe *best* way!? In particular, if (as it seems) I want theencoded number to be around the combined size of theinputs, what's the theoretical least overhead? Plus I wanted it to be mathy. Just a silly answer, --Steve ## Hyperbolic pairing function A pairing function is an $f(x, y)$ that takes two numbers (in our case any two positive integers) and somehow encodes them uniquely into a number $c$. Then an inverse function $f^{-1}(c)$ gives back the pair $(x, y)$. The granddad of pairing functions, Georg Cantor's, indexes pairs by scanning diagonals in an x, y grid. Here we define a pairing that scans hyperbolas that pass through integer points,for which the sequence $a(n)$ in https://oeis.org/A006218 is helpful. This definition (one of several there)... $$ a(n) = \sum_{k=1..n} d(k), \\ \text{where }d(k) = \text{number of divisors of k,}\\ $$ means that the half-open interval $[a(n - 1), a(n))$ has just enough room for those pairs whose product is $n$. If we but assign the pairs locations within the interval, a pairing function is defined. #### Contents Encoding $f(x, y)$ <br> Decoding <br> Cost in bits<br> Calculating $c = a(n)$ <br> - Exactly - Approximately - Bounds on $c$ Calculating the inverse $n = a^{-1}(c)$ - This means search - Approximating the inverse - Bounds on $n$ Digression about harmonic numbers ### Encoding $f(x, y)$ To encode a pair $(x, y)$, first let $$ n = xy. $$ Arrange the prime-power factors of $n$ in the usual way $$ n = \prod_j \large{p_j^{t_j}} \\ \text{where } p_k < p_j \text{ whenever } k < j.\\ $$ $x$ and $y$ are products of different powers of the same $p_j$'s: $$ x = \prod_j \large{p_j^{r_j}}\\ y = \prod_j \large{p_j^{s_j}}\\ $$ Encode $x$'s "$r$ digits in base $(t+1)$," *viz*, and bada-boom, $$c = f(x,y) = a(n-1) + \sum_j r_j \prod_{k \lt j} (t_k+1).$$ (I believe this is easier than, e.g., enumerating all the possible $x$'s and sorting them by $x$. And n.b., that would give a different ordering.) (end of extract) --Steve