Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Is there a way that makes finding inverses a bit easier?
I defined a really nice pairing function based on a space filling curve which acts on natural numbers,
⟨x,y⟩={(x≥y)∧(x≡0mod2)x2+x−y(x≥y)∧(x≡1mod2)x2+y(y>x)∧(y≡0mod2)y2+y+x+1(y>x)∧(y≡1mod2)(y+1)2−y+x,
and would like to find it’s projections. Is such a thing possible?
This seems to work, i.e., gives a bijection ⟨−,−⟩:ℕ×ℕ→ℕ, although it’s a tad unusual. (I wouldn’t call it a “space-filling curve” though; in usual parlance, a space-filling curve is a continuous surjection with domain the unit interval I, e.g., I↠I2.) Also, it’s much more common to use a simpler-looking one-line formula such as
(x,y)↦(x+y+12)+yBut anyway, if n=⟨x,y⟩ labels the grid point (x,y), and if Fl denotes the floor function, then putting f=Fl(√n) we have
(x,y)=(f,n−f2)iff2≤n≤f2+fandfisodd(x,y)=(f,f2+f−n)iff2≤n≤f2+fandfiseven(x,y)=(n−f2−f−1,f)iff2+f+1≤n≤f2+2fassuming my calculations are correct (which I won’t swear to).
Oh, by the way, notice that y2+y+x+1=(y+1)2−y+x, so your third and fourth lines could have been combined into a single line.
Thank you, Todd.
Actually, here’s an even better function I figured out that’s based on the curve I wanted that I was trying to define last night:
⟨x,y⟩={(x≡0mod2)∧(x⩾y)x2+y(y≡0mod2)∧(y>x)(y+1)2−(x+1)(x≡1mod2)∧(x>y)(x+1)2−(y+1)(y≡1mod2)∧(y⩾x)y2+xI could see it being a mechanical way to iterate an infinite matrix, so having the projections has an actual real world use.
Edit: I made it from chopping in half, then flipping the pairing function:
{(x⩾y)x2+y(y>x)(y+1)2−(x+1)Again, it should not be called a “space-filling curve”.
I’m mildly curious why this choice of bijection in 3., with the bifurcation into odd and even cases. A cousin to the bijection of 1. is the two-line expression
⟨x,y⟩=x2+yifx≥y⟨x,y⟩=y2+y+x+1ifx<ywhich to me looks simpler, and is closely connected with a standard well-ordering on ℕ×ℕ where (x,y)<(x′,y′) if either max{x,y}<max{x′,y′} or max{x,y}=max{x′,y′}∧y<y′ or max{x,y}=max{x′,y′}∧y=y′∧x<x′. (A similar type of well-ordering arises in one of the standard proofs that κ2=κ for infinite cardinals κ, assuming the axiom of choice.)
That I can answer quite easily, The reason for splitting the terms into odd and even case can be seen from the tables:
Compare the image of,
{(x⩾y)x2+y(y>x)(y+1)2−(x+1)Image: http://imgur.com/KsskDoQ
with that of,
⟨x,y⟩={(x≡0mod2)∧(x⩾y)x2+y(y≡0mod2)∧(y>x)(y+1)2−(x+1)(x≡1mod2)∧(x>y)(x+1)2−(y+1)(y≡1mod2)∧(y⩾x)y2+xImage: http://imgur.com/NIok3JM
Also, from Cantor’s pairng function,
(x+y)(x+y+1)2+yImage: http://imgur.com/Nh25uoj
I found the derivation,
{(x+y)≡0mod2(x+y)(x+y+1)2+y(x+y)≡1mod2(x+y)(x+y+1)2+xImage: http://imgur.com/CXmfFAE
Splitting up the functions this way allows for “ox-plowing” variants.
I was motivated by the page http://mathworld.wolfram.com/PairingFunction.html, which pointed out that the two ox-plowing functions given by Stein in his book had no explicit formula. Well, now they do.
As a bonus, here’s the pairing function I first defined,
{(x≥y)∧(x≡0mod2)x2+x−y(x≥y)∧(x≡1mod2)x2+y(y>x)(y+1)2−y+xImage: http://imgur.com/as34fVe
While this is nice to think about, is there are reason why the question was asked here rather than, for example, math.stackexchange?
1 to 6 of 6