@MarzioDeBiasi You mentioned "2^m 3^x1 5^x2 z" what is that encoding?

Is it some sort of bijection?

I am interested in making a bijection from NxNxN to N. So I can run the x-th machine on input y for z steps

@PALEN it is the a quick example of bijection between NxNxNxN to N (m,x1,x2 are encoded using the powers of 2,3,5; z is encoded by the other factors). E.g. 2^1*3^2*5^1*7*11 encodes m=1,x1=2,x2=1,z=77

@Raphael I think it's fine as a reference question. One suggestion: I personally don't like the footnotes (such as "Induction anchor, also base case: you show for small cases¹ that the claim holds.")

It always makes me scroll down, and then I have to scroll back... and usually I lose the line where I was at

I bet it's even harder to read on a small device

so how about instead of using a footnote, simply write what would be in the footnote in parenthesis? I the meaning is basically the same as a footnote, that is, "this is not too important, but you can read it"

@MarzioDeBiasi That's not going to be a bijection. (cc @PALEN)

What you want it a generalised/nested version of Cantor's scheme.

@PALEN It's a conceptually simple encoding that relies on prime factorisations being unique. The resulting encoding is impractical but a readily available example in theory.

@Raphael: why it is not a bijection?

@MarzioDeBiasi The canonical way would be to use 2^{x_1} * 3^{x_2} * 5^{x_3} * 7^{x_7}, which clearly not bijective.

Having read your example, I no longer understand your mapping at all. How are tuples encoded whose fourt component has prime factors from {2,3,4}?

But I wrote 2^x * 3^y * 5^w * z (with z not divisible by 2,3,5)

Yea, that restriction on z was implicit, I guess. ;)

A simpler example is the enoiding of pairs: 2^x*(2y+1)

And the set of such z is not N.

I'd go with Cantor if you need bijection, but that's a matter of taste, I guess.

You're right I assumed that z should be calculated in a manner similar to the pairing function ...

(the pairing function 2^x (2y+1)

So in my example above (2^1*3^2*5^1*7*11), z is not 77

(you should "shift" the primes 7->2 11->3, so z = 6 ... )

in other words given the prime factorization of z replace p_i with p_{i-2}

... a little bit weird but in these days I'm busy with number theory stuff so I thought it was natural

:-D

2^1 3^2 5^1 (7^2 * 13) -> m=1, x1=2, x2=1, z=2^2*5=20 ...

Ah, I see now.

I concede: something like this can work. (I still don't like it ;))

@Raphael Did what I said about the footnote make sense?

It's "number theory style" ... :-D

@Juho Yes, I have that tab open.

I think I still favor the footnote since the remarks are well beyond the expected scope of the novice reader, but I get your point about the distance. (Website suck in this.)

I gotcha. In any case, it's not a big deal

@Raphael I searched for 'generalised/nested version of Cantor's scheme' but didn't find anything. However, by the name I may guess correct: is it a nested application of the NxN -> N bijection? Because I ended up using that....

@Raphael Also if you could point me to some reading will be very helpful

@MarzioDeBiasi It is not as natural for me :( Intuitively, it seems to me that combining the factors of prime numbers you could generate any number of N. Am I correct? No x that is in N would be repeated as the prime numbers don't have common factors... Also, if you could point me to some reading would be great!

@PALEN: for what regards Cantor's pairing function; it is the following:

J(x,y) = ((x+y)(x+y+1))/2 + 1

as suggested by Raphael you can "nest" it how many times as you want:

J(x,y,z)=J(x,J(y,z)), ...

@PALEN If f : N x N -> N is Cantors scheme, use g(a,b,c) = f(f(a,b),c)

And so on. Nesting bijections in that way yields bijections.

Or what Marzio just said which I did not read before typing. Whoops.

Exercise: design a bijection from N^+ to N.

N^+ is the union of all N^k for natural k >= 1

For what regards my encoding, it is based on the fundamental theorem of arithmetic en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic : every integer has an unique factorization. So you can use the exponents of the primes (in the factorization) to encode tuples. The easiest way to encode an n-tuple is to use only the exponents of the first n-primes (e.g. 2^x 3^y 5^z), but as noted by Raphael it is not a bijection; an alternate way is to "shift" the remaining primes as I wrote above.

IMO the representation is elegant (though Raphael and probably many others don't like it :-)))) but surely it cannot be used in practice because FACTORING is (seems) hard.

I used the nested Cantor's pairing function before asking :) ... Thank

@MarzioDeBiasi It seems elegant to me too!

@PALEN think "inner loops" where the inner loop increments to the outer loops.

its also called "listing in canonical order"

are you working on something theoretical or otherwise?