Convert infinite 2D plane integer coords to 1D number
Say I have an infinte 2D grid (ex. a procedurally generated world) and I want to get a unique number for each integer coordinate pair. How would I accomplish this?
My idea is to use a square spiral, but I cant find a way to make a formula for the unique number other than an algorythm that just goes in a square spiral and stops at the wanted coords.
The application for this converstion could be for example a way to save an n dimensional shape to a file where each line represents a chunk of the shape (by using $u(x, y, z) = u(u(x, y), u(y, z))$ ), or have a very unique random seed for each integer point (ex. a way to hash an integer vector to a data point in an n dimensional array)
algebraic-geometry
add a comment |
Say I have an infinte 2D grid (ex. a procedurally generated world) and I want to get a unique number for each integer coordinate pair. How would I accomplish this?
My idea is to use a square spiral, but I cant find a way to make a formula for the unique number other than an algorythm that just goes in a square spiral and stops at the wanted coords.
The application for this converstion could be for example a way to save an n dimensional shape to a file where each line represents a chunk of the shape (by using $u(x, y, z) = u(u(x, y), u(y, z))$ ), or have a very unique random seed for each integer point (ex. a way to hash an integer vector to a data point in an n dimensional array)
algebraic-geometry
More generally than Ross's answer there are a range of pairing functions, some of which are defined precisely as spirals as you describe. It is a theorem that Ross's answer is the unique quadratic pairing function, modulo exchanging x and y.
– user334732
Nov 19 '18 at 4:21
add a comment |
Say I have an infinte 2D grid (ex. a procedurally generated world) and I want to get a unique number for each integer coordinate pair. How would I accomplish this?
My idea is to use a square spiral, but I cant find a way to make a formula for the unique number other than an algorythm that just goes in a square spiral and stops at the wanted coords.
The application for this converstion could be for example a way to save an n dimensional shape to a file where each line represents a chunk of the shape (by using $u(x, y, z) = u(u(x, y), u(y, z))$ ), or have a very unique random seed for each integer point (ex. a way to hash an integer vector to a data point in an n dimensional array)
algebraic-geometry
Say I have an infinte 2D grid (ex. a procedurally generated world) and I want to get a unique number for each integer coordinate pair. How would I accomplish this?
My idea is to use a square spiral, but I cant find a way to make a formula for the unique number other than an algorythm that just goes in a square spiral and stops at the wanted coords.
The application for this converstion could be for example a way to save an n dimensional shape to a file where each line represents a chunk of the shape (by using $u(x, y, z) = u(u(x, y), u(y, z))$ ), or have a very unique random seed for each integer point (ex. a way to hash an integer vector to a data point in an n dimensional array)
algebraic-geometry
algebraic-geometry
asked Nov 18 '18 at 15:25
Flutterish
837
837
More generally than Ross's answer there are a range of pairing functions, some of which are defined precisely as spirals as you describe. It is a theorem that Ross's answer is the unique quadratic pairing function, modulo exchanging x and y.
– user334732
Nov 19 '18 at 4:21
add a comment |
More generally than Ross's answer there are a range of pairing functions, some of which are defined precisely as spirals as you describe. It is a theorem that Ross's answer is the unique quadratic pairing function, modulo exchanging x and y.
– user334732
Nov 19 '18 at 4:21
More generally than Ross's answer there are a range of pairing functions, some of which are defined precisely as spirals as you describe. It is a theorem that Ross's answer is the unique quadratic pairing function, modulo exchanging x and y.
– user334732
Nov 19 '18 at 4:21
More generally than Ross's answer there are a range of pairing functions, some of which are defined precisely as spirals as you describe. It is a theorem that Ross's answer is the unique quadratic pairing function, modulo exchanging x and y.
– user334732
Nov 19 '18 at 4:21
add a comment |
4 Answers
4
active
oldest
votes
You need the Cantor pairing function, tuned up to accept integers instead of naturals. The basic function takes a pair of naturals (including zero) $x,y$ and returns a natural $pi(x,y)=frac 12(x+y)(x+y+1)+y$. It is invertible, so given $pi(x,y)$ you can recover $x$ and $y$. Now just take your integers to naturals by $$f(z)=begin {cases} 2z&zge 0\-2z-1& z lt 0end {cases}$$ pair them and you have your result.
add a comment |
Other answers state how to convert integers to naturals, I won't repeat this step. Let's suppose you have two naturals, e.g.:
$$ 123 $$
$$ 98765 $$
Add leading zeros to obtain equal number of digits:
$$ 00123 $$
$$ 98765 $$
And "interleave":
$$ 0908172635 $$
Reverting is trivial: you pick digits from either odd or even positions.
Notes:
- the representation depends on the base of the numeral system you use;
- you can expand the method to non-negative reals in a quite obvious way;
- similarly you can create a method that takes any fixed number of numbers and yields one number.
This is a valid answer, but I cant see this as an effieicient solution, especially in the 1st example use where one would save the data in the file line with index of the unique number. Also as far as I'm concerned numbers dont begin with 0's, so if this would to be stored in a variable, it would have to be a string which is 256 bits per numerical digit where a numerical variable takes ~3.32 bits per numerical digit. I know this is a math forum, but I'm talking about this because my proposed applications are IT ones!
– Flutterish
Nov 18 '18 at 19:28
3
@Flutterish You need numbers as strings only during conversion. At any other moment you can store numbers as numbers.
– Kamil Maciorowski
Nov 18 '18 at 19:30
2
0908172635, the example you've given is leaded by a zero, which cant be saved as a number. I know I could just cut it off, but then... No, actually yes, you are right, there is no way I will ever end up with 2 leading zeros (except $(0,0)$, but thats not a problem), therefore I will always be able to store it as a number.
– Flutterish
Nov 18 '18 at 19:39
add a comment |
There are also tools from number theory. We can first map all integers to non-negative ones, which is easy, just take $$f(n)=left{begin{align}&2n&nge0\&-2n-1&n<0end{align}right.$$ as Ross pointed out. Now us take the pair $(m,n)$ to be $2^{f(m)}3^{f(n)}$. Since we can uniquely decompose positive integers into prime factors, this function is invertible, and you have your result.
Unlike Ross's answer, this answer doesn't biject so some wastage occurs insofar as it will only use two thirds of the integers.
– user334732
Nov 19 '18 at 4:15
3
@RobertFrost: In fact, this mapping will skip almost all integers; specifically, its image only includes the powers of 2 and 3 and their products (including 1, as a trivial case), whose asymptomatic density among all integers is zero. For example, the only numbers below 100 this function can return are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81 and 96; they start out pretty dense below 10, but get sparser and sparser quickly.
– Ilmari Karonen
Nov 19 '18 at 7:29
@IlmariKaronen the 3 smooth numbers no less, excluding every number having a 5 rough number other than 1 as a factor.
– user334732
Nov 19 '18 at 7:54
add a comment |
This is an interesting question. I will provide a method to simplify your algorithm, but not necessarily a formula just yet (I'm sure that what I'm about to show you will lead to a formula...probably).
Let's begin with a point in the center. That is, we are not starting at the top corner of a semi-infinite plane, we are instead assuming the plane is infinite. The point in the center is assigned the number 1, and we call it the $i = 1$ point. We surround this square with a border of squares. This border has 8 such squares. We repeat the process and get 16 squares. In general, each "border" has $2(2i-1) + 2(2i-3) = 8i - 8 = 8(i-1)$ squares.
We now want to form a sum of the first $N$ such squares:
$$S_N = bigg(sum_{i=2}^{N}8(i-1)bigg) + 1$$
Now, you want to simplify your life, so let's simplify that sum. We would end up with:
$$S_N = 8bigg(sum_{i=2}^{N}(i-1)bigg) + 1$$
$$S_N = 8frac{N(N+1)}{2}-1 - (8N - 8) + 1$$ (I'll leave you to simplify) and check my algebra. I'm 99% sure it's accurate.
Now you want to unpack this. This involves several steps. Say you have the number $M$. You need to find the largest $N$ such that $S_N le M lt S_{N+1}$. Other than a strict search, I'm afraid I don't know how to do that, sorry.
Once you know the $N$, then you need to compute the quantity $M - S_N$. This quantity tells you how many squares to "walk" from some starting square on border $N+1$ to where you want to be. Since you know where the border squares start, and you know how far you've walked, you know where on the border you are and therefore what the coordinates are.
The method needs some cleanup, but should do it. Good luck doing that in N-D.
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003672%2fconvert-infinite-2d-plane-integer-coords-to-1d-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
You need the Cantor pairing function, tuned up to accept integers instead of naturals. The basic function takes a pair of naturals (including zero) $x,y$ and returns a natural $pi(x,y)=frac 12(x+y)(x+y+1)+y$. It is invertible, so given $pi(x,y)$ you can recover $x$ and $y$. Now just take your integers to naturals by $$f(z)=begin {cases} 2z&zge 0\-2z-1& z lt 0end {cases}$$ pair them and you have your result.
add a comment |
You need the Cantor pairing function, tuned up to accept integers instead of naturals. The basic function takes a pair of naturals (including zero) $x,y$ and returns a natural $pi(x,y)=frac 12(x+y)(x+y+1)+y$. It is invertible, so given $pi(x,y)$ you can recover $x$ and $y$. Now just take your integers to naturals by $$f(z)=begin {cases} 2z&zge 0\-2z-1& z lt 0end {cases}$$ pair them and you have your result.
add a comment |
You need the Cantor pairing function, tuned up to accept integers instead of naturals. The basic function takes a pair of naturals (including zero) $x,y$ and returns a natural $pi(x,y)=frac 12(x+y)(x+y+1)+y$. It is invertible, so given $pi(x,y)$ you can recover $x$ and $y$. Now just take your integers to naturals by $$f(z)=begin {cases} 2z&zge 0\-2z-1& z lt 0end {cases}$$ pair them and you have your result.
You need the Cantor pairing function, tuned up to accept integers instead of naturals. The basic function takes a pair of naturals (including zero) $x,y$ and returns a natural $pi(x,y)=frac 12(x+y)(x+y+1)+y$. It is invertible, so given $pi(x,y)$ you can recover $x$ and $y$. Now just take your integers to naturals by $$f(z)=begin {cases} 2z&zge 0\-2z-1& z lt 0end {cases}$$ pair them and you have your result.
answered Nov 18 '18 at 16:43
Ross Millikan
291k23196371
291k23196371
add a comment |
add a comment |
Other answers state how to convert integers to naturals, I won't repeat this step. Let's suppose you have two naturals, e.g.:
$$ 123 $$
$$ 98765 $$
Add leading zeros to obtain equal number of digits:
$$ 00123 $$
$$ 98765 $$
And "interleave":
$$ 0908172635 $$
Reverting is trivial: you pick digits from either odd or even positions.
Notes:
- the representation depends on the base of the numeral system you use;
- you can expand the method to non-negative reals in a quite obvious way;
- similarly you can create a method that takes any fixed number of numbers and yields one number.
This is a valid answer, but I cant see this as an effieicient solution, especially in the 1st example use where one would save the data in the file line with index of the unique number. Also as far as I'm concerned numbers dont begin with 0's, so if this would to be stored in a variable, it would have to be a string which is 256 bits per numerical digit where a numerical variable takes ~3.32 bits per numerical digit. I know this is a math forum, but I'm talking about this because my proposed applications are IT ones!
– Flutterish
Nov 18 '18 at 19:28
3
@Flutterish You need numbers as strings only during conversion. At any other moment you can store numbers as numbers.
– Kamil Maciorowski
Nov 18 '18 at 19:30
2
0908172635, the example you've given is leaded by a zero, which cant be saved as a number. I know I could just cut it off, but then... No, actually yes, you are right, there is no way I will ever end up with 2 leading zeros (except $(0,0)$, but thats not a problem), therefore I will always be able to store it as a number.
– Flutterish
Nov 18 '18 at 19:39
add a comment |
Other answers state how to convert integers to naturals, I won't repeat this step. Let's suppose you have two naturals, e.g.:
$$ 123 $$
$$ 98765 $$
Add leading zeros to obtain equal number of digits:
$$ 00123 $$
$$ 98765 $$
And "interleave":
$$ 0908172635 $$
Reverting is trivial: you pick digits from either odd or even positions.
Notes:
- the representation depends on the base of the numeral system you use;
- you can expand the method to non-negative reals in a quite obvious way;
- similarly you can create a method that takes any fixed number of numbers and yields one number.
This is a valid answer, but I cant see this as an effieicient solution, especially in the 1st example use where one would save the data in the file line with index of the unique number. Also as far as I'm concerned numbers dont begin with 0's, so if this would to be stored in a variable, it would have to be a string which is 256 bits per numerical digit where a numerical variable takes ~3.32 bits per numerical digit. I know this is a math forum, but I'm talking about this because my proposed applications are IT ones!
– Flutterish
Nov 18 '18 at 19:28
3
@Flutterish You need numbers as strings only during conversion. At any other moment you can store numbers as numbers.
– Kamil Maciorowski
Nov 18 '18 at 19:30
2
0908172635, the example you've given is leaded by a zero, which cant be saved as a number. I know I could just cut it off, but then... No, actually yes, you are right, there is no way I will ever end up with 2 leading zeros (except $(0,0)$, but thats not a problem), therefore I will always be able to store it as a number.
– Flutterish
Nov 18 '18 at 19:39
add a comment |
Other answers state how to convert integers to naturals, I won't repeat this step. Let's suppose you have two naturals, e.g.:
$$ 123 $$
$$ 98765 $$
Add leading zeros to obtain equal number of digits:
$$ 00123 $$
$$ 98765 $$
And "interleave":
$$ 0908172635 $$
Reverting is trivial: you pick digits from either odd or even positions.
Notes:
- the representation depends on the base of the numeral system you use;
- you can expand the method to non-negative reals in a quite obvious way;
- similarly you can create a method that takes any fixed number of numbers and yields one number.
Other answers state how to convert integers to naturals, I won't repeat this step. Let's suppose you have two naturals, e.g.:
$$ 123 $$
$$ 98765 $$
Add leading zeros to obtain equal number of digits:
$$ 00123 $$
$$ 98765 $$
And "interleave":
$$ 0908172635 $$
Reverting is trivial: you pick digits from either odd or even positions.
Notes:
- the representation depends on the base of the numeral system you use;
- you can expand the method to non-negative reals in a quite obvious way;
- similarly you can create a method that takes any fixed number of numbers and yields one number.
edited Nov 18 '18 at 20:51
answered Nov 18 '18 at 19:02
Kamil Maciorowski
2,4991920
2,4991920
This is a valid answer, but I cant see this as an effieicient solution, especially in the 1st example use where one would save the data in the file line with index of the unique number. Also as far as I'm concerned numbers dont begin with 0's, so if this would to be stored in a variable, it would have to be a string which is 256 bits per numerical digit where a numerical variable takes ~3.32 bits per numerical digit. I know this is a math forum, but I'm talking about this because my proposed applications are IT ones!
– Flutterish
Nov 18 '18 at 19:28
3
@Flutterish You need numbers as strings only during conversion. At any other moment you can store numbers as numbers.
– Kamil Maciorowski
Nov 18 '18 at 19:30
2
0908172635, the example you've given is leaded by a zero, which cant be saved as a number. I know I could just cut it off, but then... No, actually yes, you are right, there is no way I will ever end up with 2 leading zeros (except $(0,0)$, but thats not a problem), therefore I will always be able to store it as a number.
– Flutterish
Nov 18 '18 at 19:39
add a comment |
This is a valid answer, but I cant see this as an effieicient solution, especially in the 1st example use where one would save the data in the file line with index of the unique number. Also as far as I'm concerned numbers dont begin with 0's, so if this would to be stored in a variable, it would have to be a string which is 256 bits per numerical digit where a numerical variable takes ~3.32 bits per numerical digit. I know this is a math forum, but I'm talking about this because my proposed applications are IT ones!
– Flutterish
Nov 18 '18 at 19:28
3
@Flutterish You need numbers as strings only during conversion. At any other moment you can store numbers as numbers.
– Kamil Maciorowski
Nov 18 '18 at 19:30
2
0908172635, the example you've given is leaded by a zero, which cant be saved as a number. I know I could just cut it off, but then... No, actually yes, you are right, there is no way I will ever end up with 2 leading zeros (except $(0,0)$, but thats not a problem), therefore I will always be able to store it as a number.
– Flutterish
Nov 18 '18 at 19:39
This is a valid answer, but I cant see this as an effieicient solution, especially in the 1st example use where one would save the data in the file line with index of the unique number. Also as far as I'm concerned numbers dont begin with 0's, so if this would to be stored in a variable, it would have to be a string which is 256 bits per numerical digit where a numerical variable takes ~3.32 bits per numerical digit. I know this is a math forum, but I'm talking about this because my proposed applications are IT ones!
– Flutterish
Nov 18 '18 at 19:28
This is a valid answer, but I cant see this as an effieicient solution, especially in the 1st example use where one would save the data in the file line with index of the unique number. Also as far as I'm concerned numbers dont begin with 0's, so if this would to be stored in a variable, it would have to be a string which is 256 bits per numerical digit where a numerical variable takes ~3.32 bits per numerical digit. I know this is a math forum, but I'm talking about this because my proposed applications are IT ones!
– Flutterish
Nov 18 '18 at 19:28
3
3
@Flutterish You need numbers as strings only during conversion. At any other moment you can store numbers as numbers.
– Kamil Maciorowski
Nov 18 '18 at 19:30
@Flutterish You need numbers as strings only during conversion. At any other moment you can store numbers as numbers.
– Kamil Maciorowski
Nov 18 '18 at 19:30
2
2
0908172635, the example you've given is leaded by a zero, which cant be saved as a number. I know I could just cut it off, but then... No, actually yes, you are right, there is no way I will ever end up with 2 leading zeros (except $(0,0)$, but thats not a problem), therefore I will always be able to store it as a number.
– Flutterish
Nov 18 '18 at 19:39
0908172635, the example you've given is leaded by a zero, which cant be saved as a number. I know I could just cut it off, but then... No, actually yes, you are right, there is no way I will ever end up with 2 leading zeros (except $(0,0)$, but thats not a problem), therefore I will always be able to store it as a number.
– Flutterish
Nov 18 '18 at 19:39
add a comment |
There are also tools from number theory. We can first map all integers to non-negative ones, which is easy, just take $$f(n)=left{begin{align}&2n&nge0\&-2n-1&n<0end{align}right.$$ as Ross pointed out. Now us take the pair $(m,n)$ to be $2^{f(m)}3^{f(n)}$. Since we can uniquely decompose positive integers into prime factors, this function is invertible, and you have your result.
Unlike Ross's answer, this answer doesn't biject so some wastage occurs insofar as it will only use two thirds of the integers.
– user334732
Nov 19 '18 at 4:15
3
@RobertFrost: In fact, this mapping will skip almost all integers; specifically, its image only includes the powers of 2 and 3 and their products (including 1, as a trivial case), whose asymptomatic density among all integers is zero. For example, the only numbers below 100 this function can return are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81 and 96; they start out pretty dense below 10, but get sparser and sparser quickly.
– Ilmari Karonen
Nov 19 '18 at 7:29
@IlmariKaronen the 3 smooth numbers no less, excluding every number having a 5 rough number other than 1 as a factor.
– user334732
Nov 19 '18 at 7:54
add a comment |
There are also tools from number theory. We can first map all integers to non-negative ones, which is easy, just take $$f(n)=left{begin{align}&2n&nge0\&-2n-1&n<0end{align}right.$$ as Ross pointed out. Now us take the pair $(m,n)$ to be $2^{f(m)}3^{f(n)}$. Since we can uniquely decompose positive integers into prime factors, this function is invertible, and you have your result.
Unlike Ross's answer, this answer doesn't biject so some wastage occurs insofar as it will only use two thirds of the integers.
– user334732
Nov 19 '18 at 4:15
3
@RobertFrost: In fact, this mapping will skip almost all integers; specifically, its image only includes the powers of 2 and 3 and their products (including 1, as a trivial case), whose asymptomatic density among all integers is zero. For example, the only numbers below 100 this function can return are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81 and 96; they start out pretty dense below 10, but get sparser and sparser quickly.
– Ilmari Karonen
Nov 19 '18 at 7:29
@IlmariKaronen the 3 smooth numbers no less, excluding every number having a 5 rough number other than 1 as a factor.
– user334732
Nov 19 '18 at 7:54
add a comment |
There are also tools from number theory. We can first map all integers to non-negative ones, which is easy, just take $$f(n)=left{begin{align}&2n&nge0\&-2n-1&n<0end{align}right.$$ as Ross pointed out. Now us take the pair $(m,n)$ to be $2^{f(m)}3^{f(n)}$. Since we can uniquely decompose positive integers into prime factors, this function is invertible, and you have your result.
There are also tools from number theory. We can first map all integers to non-negative ones, which is easy, just take $$f(n)=left{begin{align}&2n&nge0\&-2n-1&n<0end{align}right.$$ as Ross pointed out. Now us take the pair $(m,n)$ to be $2^{f(m)}3^{f(n)}$. Since we can uniquely decompose positive integers into prime factors, this function is invertible, and you have your result.
answered Nov 18 '18 at 16:50
Trebor
58112
58112
Unlike Ross's answer, this answer doesn't biject so some wastage occurs insofar as it will only use two thirds of the integers.
– user334732
Nov 19 '18 at 4:15
3
@RobertFrost: In fact, this mapping will skip almost all integers; specifically, its image only includes the powers of 2 and 3 and their products (including 1, as a trivial case), whose asymptomatic density among all integers is zero. For example, the only numbers below 100 this function can return are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81 and 96; they start out pretty dense below 10, but get sparser and sparser quickly.
– Ilmari Karonen
Nov 19 '18 at 7:29
@IlmariKaronen the 3 smooth numbers no less, excluding every number having a 5 rough number other than 1 as a factor.
– user334732
Nov 19 '18 at 7:54
add a comment |
Unlike Ross's answer, this answer doesn't biject so some wastage occurs insofar as it will only use two thirds of the integers.
– user334732
Nov 19 '18 at 4:15
3
@RobertFrost: In fact, this mapping will skip almost all integers; specifically, its image only includes the powers of 2 and 3 and their products (including 1, as a trivial case), whose asymptomatic density among all integers is zero. For example, the only numbers below 100 this function can return are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81 and 96; they start out pretty dense below 10, but get sparser and sparser quickly.
– Ilmari Karonen
Nov 19 '18 at 7:29
@IlmariKaronen the 3 smooth numbers no less, excluding every number having a 5 rough number other than 1 as a factor.
– user334732
Nov 19 '18 at 7:54
Unlike Ross's answer, this answer doesn't biject so some wastage occurs insofar as it will only use two thirds of the integers.
– user334732
Nov 19 '18 at 4:15
Unlike Ross's answer, this answer doesn't biject so some wastage occurs insofar as it will only use two thirds of the integers.
– user334732
Nov 19 '18 at 4:15
3
3
@RobertFrost: In fact, this mapping will skip almost all integers; specifically, its image only includes the powers of 2 and 3 and their products (including 1, as a trivial case), whose asymptomatic density among all integers is zero. For example, the only numbers below 100 this function can return are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81 and 96; they start out pretty dense below 10, but get sparser and sparser quickly.
– Ilmari Karonen
Nov 19 '18 at 7:29
@RobertFrost: In fact, this mapping will skip almost all integers; specifically, its image only includes the powers of 2 and 3 and their products (including 1, as a trivial case), whose asymptomatic density among all integers is zero. For example, the only numbers below 100 this function can return are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81 and 96; they start out pretty dense below 10, but get sparser and sparser quickly.
– Ilmari Karonen
Nov 19 '18 at 7:29
@IlmariKaronen the 3 smooth numbers no less, excluding every number having a 5 rough number other than 1 as a factor.
– user334732
Nov 19 '18 at 7:54
@IlmariKaronen the 3 smooth numbers no less, excluding every number having a 5 rough number other than 1 as a factor.
– user334732
Nov 19 '18 at 7:54
add a comment |
This is an interesting question. I will provide a method to simplify your algorithm, but not necessarily a formula just yet (I'm sure that what I'm about to show you will lead to a formula...probably).
Let's begin with a point in the center. That is, we are not starting at the top corner of a semi-infinite plane, we are instead assuming the plane is infinite. The point in the center is assigned the number 1, and we call it the $i = 1$ point. We surround this square with a border of squares. This border has 8 such squares. We repeat the process and get 16 squares. In general, each "border" has $2(2i-1) + 2(2i-3) = 8i - 8 = 8(i-1)$ squares.
We now want to form a sum of the first $N$ such squares:
$$S_N = bigg(sum_{i=2}^{N}8(i-1)bigg) + 1$$
Now, you want to simplify your life, so let's simplify that sum. We would end up with:
$$S_N = 8bigg(sum_{i=2}^{N}(i-1)bigg) + 1$$
$$S_N = 8frac{N(N+1)}{2}-1 - (8N - 8) + 1$$ (I'll leave you to simplify) and check my algebra. I'm 99% sure it's accurate.
Now you want to unpack this. This involves several steps. Say you have the number $M$. You need to find the largest $N$ such that $S_N le M lt S_{N+1}$. Other than a strict search, I'm afraid I don't know how to do that, sorry.
Once you know the $N$, then you need to compute the quantity $M - S_N$. This quantity tells you how many squares to "walk" from some starting square on border $N+1$ to where you want to be. Since you know where the border squares start, and you know how far you've walked, you know where on the border you are and therefore what the coordinates are.
The method needs some cleanup, but should do it. Good luck doing that in N-D.
add a comment |
This is an interesting question. I will provide a method to simplify your algorithm, but not necessarily a formula just yet (I'm sure that what I'm about to show you will lead to a formula...probably).
Let's begin with a point in the center. That is, we are not starting at the top corner of a semi-infinite plane, we are instead assuming the plane is infinite. The point in the center is assigned the number 1, and we call it the $i = 1$ point. We surround this square with a border of squares. This border has 8 such squares. We repeat the process and get 16 squares. In general, each "border" has $2(2i-1) + 2(2i-3) = 8i - 8 = 8(i-1)$ squares.
We now want to form a sum of the first $N$ such squares:
$$S_N = bigg(sum_{i=2}^{N}8(i-1)bigg) + 1$$
Now, you want to simplify your life, so let's simplify that sum. We would end up with:
$$S_N = 8bigg(sum_{i=2}^{N}(i-1)bigg) + 1$$
$$S_N = 8frac{N(N+1)}{2}-1 - (8N - 8) + 1$$ (I'll leave you to simplify) and check my algebra. I'm 99% sure it's accurate.
Now you want to unpack this. This involves several steps. Say you have the number $M$. You need to find the largest $N$ such that $S_N le M lt S_{N+1}$. Other than a strict search, I'm afraid I don't know how to do that, sorry.
Once you know the $N$, then you need to compute the quantity $M - S_N$. This quantity tells you how many squares to "walk" from some starting square on border $N+1$ to where you want to be. Since you know where the border squares start, and you know how far you've walked, you know where on the border you are and therefore what the coordinates are.
The method needs some cleanup, but should do it. Good luck doing that in N-D.
add a comment |
This is an interesting question. I will provide a method to simplify your algorithm, but not necessarily a formula just yet (I'm sure that what I'm about to show you will lead to a formula...probably).
Let's begin with a point in the center. That is, we are not starting at the top corner of a semi-infinite plane, we are instead assuming the plane is infinite. The point in the center is assigned the number 1, and we call it the $i = 1$ point. We surround this square with a border of squares. This border has 8 such squares. We repeat the process and get 16 squares. In general, each "border" has $2(2i-1) + 2(2i-3) = 8i - 8 = 8(i-1)$ squares.
We now want to form a sum of the first $N$ such squares:
$$S_N = bigg(sum_{i=2}^{N}8(i-1)bigg) + 1$$
Now, you want to simplify your life, so let's simplify that sum. We would end up with:
$$S_N = 8bigg(sum_{i=2}^{N}(i-1)bigg) + 1$$
$$S_N = 8frac{N(N+1)}{2}-1 - (8N - 8) + 1$$ (I'll leave you to simplify) and check my algebra. I'm 99% sure it's accurate.
Now you want to unpack this. This involves several steps. Say you have the number $M$. You need to find the largest $N$ such that $S_N le M lt S_{N+1}$. Other than a strict search, I'm afraid I don't know how to do that, sorry.
Once you know the $N$, then you need to compute the quantity $M - S_N$. This quantity tells you how many squares to "walk" from some starting square on border $N+1$ to where you want to be. Since you know where the border squares start, and you know how far you've walked, you know where on the border you are and therefore what the coordinates are.
The method needs some cleanup, but should do it. Good luck doing that in N-D.
This is an interesting question. I will provide a method to simplify your algorithm, but not necessarily a formula just yet (I'm sure that what I'm about to show you will lead to a formula...probably).
Let's begin with a point in the center. That is, we are not starting at the top corner of a semi-infinite plane, we are instead assuming the plane is infinite. The point in the center is assigned the number 1, and we call it the $i = 1$ point. We surround this square with a border of squares. This border has 8 such squares. We repeat the process and get 16 squares. In general, each "border" has $2(2i-1) + 2(2i-3) = 8i - 8 = 8(i-1)$ squares.
We now want to form a sum of the first $N$ such squares:
$$S_N = bigg(sum_{i=2}^{N}8(i-1)bigg) + 1$$
Now, you want to simplify your life, so let's simplify that sum. We would end up with:
$$S_N = 8bigg(sum_{i=2}^{N}(i-1)bigg) + 1$$
$$S_N = 8frac{N(N+1)}{2}-1 - (8N - 8) + 1$$ (I'll leave you to simplify) and check my algebra. I'm 99% sure it's accurate.
Now you want to unpack this. This involves several steps. Say you have the number $M$. You need to find the largest $N$ such that $S_N le M lt S_{N+1}$. Other than a strict search, I'm afraid I don't know how to do that, sorry.
Once you know the $N$, then you need to compute the quantity $M - S_N$. This quantity tells you how many squares to "walk" from some starting square on border $N+1$ to where you want to be. Since you know where the border squares start, and you know how far you've walked, you know where on the border you are and therefore what the coordinates are.
The method needs some cleanup, but should do it. Good luck doing that in N-D.
edited Nov 18 '18 at 16:28
answered Nov 18 '18 at 16:00
Michael Stachowsky
1,260417
1,260417
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3003672%2fconvert-infinite-2d-plane-integer-coords-to-1d-number%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
More generally than Ross's answer there are a range of pairing functions, some of which are defined precisely as spirals as you describe. It is a theorem that Ross's answer is the unique quadratic pairing function, modulo exchanging x and y.
– user334732
Nov 19 '18 at 4:21