# Find X,Y,Z coordinates from index

## Introduction

I began studying the Collatz Conjecture

And noticed these patterns;
0,1,2,2,3,3...A055086, and 0,1,2,0,3,1...A082375,
in the numbers that go to 1 in one odd step,
5,10,20,21,40,42...A062052
Related like so;
A062052()(n) = ( 16*2^A055086(n) - 2^A082375(n) ) /3

The formula for A055086 is $$\lfloor\sqrt{4n + 1}\rfloor - 1$$

and the formula for A082375 is $${\left\lfloor\sqrt{4\left\lfloor x\right\rfloor+1}\right\rfloor - 1 - \left\lfloor \frac12 \left(4\left\lfloor x\right\rfloor + 1 -\left\lfloor\sqrt{4\left\lfloor x\right\rfloor+1}\right\rfloor^2\right)\right\rfloor}$$

So the formula for A062052 most likely is

$$\frac{8\cdot2^{\left\lfloor\sqrt{4\left\lfloor x\right\rfloor+1}\right\rfloor} - 2^{\left\lfloor\sqrt{4\left\lfloor x\right\rfloor+1}\right\rfloor - 1 - \left\lfloor \frac12 \left(4\left\lfloor x\right\rfloor + 1 -\left\lfloor\sqrt{4\left\lfloor x\right\rfloor+1}\right\rfloor^2\right)\right\rfloor}}{3}$$

Then I looked at numbers going to 1 in two steps, like 3,6,12,13,24,26...
Where I found another pattern that I could not find a formula for on OEIS

long nth(int n){if(n>241)return -1;return (((1<<Y[n]+5)-(1<<1+Y[n]-((Z[n]&1)+Z[n]*3)))/3-(1<<Y[n]-2*X[n]-(2*(Z[n]&1)+Z[n]*3)))/3;}


With X[],Y[] and Z[] being these lookup-tables

 int[]X=new int[]{
0,
0,
0,  1,
0,  1,
0,  1,  2,
0,  1,  2,                              0,
0,  1,  2,  3,                          0,                          0,
0,  1,  2,  3,                          0,  1,                      0,
0,  1,  2,  3,  4,                      0,  1,                      0,  1,
0,  1,  2,  3,  4,                      0,  1,  2,                  0,  1,
0,  1,  2,  3,  4,  5,                  0,  1,  2,                  0,  1,  2,
0,  1,  2,  3,  4,  5,                  0,  1,  2,  3,              0,  1,  2,                  0,
0,  1,  2,  3,  4,  5,  6,              0,  1,  2,  3,              0,  1,  2,  3,              0,              0,
0,  1,  2,  3,  4,  5,  6,              0,  1,  2,  3,  4,          0,  1,  2,  3,              0,  1,          0,
0,  1,  2,  3,  4,  5,  6,  7,          0,  1,  2,  3,  4,          0,  1,  2,  3,  4,          0,  1,          0,  1,
0,  1,  2,  3,  4,  5,  6,  7,          0,  1,  2,  3,  4,  5,      0,  1,  2,  3,  4,          0,  1,  2,      0,  1,
0,  1,  2,  3,  4,  5,  6,  7,  8,      0,  1,  2,  3,  4,  5,      0,  1,  2,  3,  4,  5,      0,  1,  2,      0,  1,  2,
0,  1,  2,  3,  4,  5,  6,  7,  8,      0,  1,  2,  3,  4,  5,  6,  0,  1,  2,  3,  4,  5,      0,  1,  2,  3,  0,  1,  2,      0,
0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  0,  1,  2,  3,  4,  5,  6,  0,  1,  2,  3,  4,  5,  6,  0,  1,  2,  3,  0,  1,  2,  3,  1, 2
};
int[]Y=new int[]{
0,
1,
2,  2,
3,  3,
4,  4,  4,
5,  5,  5,                              5,
6,  6,  6,  6,                          6,                          6,
7,  7,  7,  7,                          7,  7,                      7,
8,  8,  8,  8,  8,                      8,  8,                      8,  8,
9,  9,  9,  9,  9,                      9,  9,  9,                  9,  9,
10, 10, 10, 10, 10, 10,                 10, 10, 10,                 10, 10, 10,
11, 11, 11, 11, 11, 11,                 11, 11, 11, 11,             11, 11, 11,                 11,
12, 12, 12, 12, 12, 12, 12,             12, 12, 12, 12,             12, 12, 12, 12,             12,             12,
13, 13, 13, 13, 13, 13, 13,             13, 13, 13, 13, 13,         13, 13, 13, 13,             13, 13,         13,
14, 14, 14, 14, 14, 14, 14, 14,         14, 14, 14, 14, 14,         14, 14, 14, 14, 14,         14, 14,         14, 14,
15, 15, 15, 15, 15, 15, 15, 15,         15, 15, 15, 15, 15, 15,     15, 15, 15, 15, 15,         15, 15, 15,     15, 15,
16, 16, 16, 16, 16, 16, 16, 16, 16,     16, 16, 16, 16, 16, 16,     16, 16, 16, 16, 16, 16,     16, 16, 16,     16, 16, 16,
17, 17, 17, 17, 17, 17, 17, 17, 17,     17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,     17, 17, 17, 17, 17, 17, 17,     17,
18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18
};
int[]Z=new int[]{
0,
0,
0,  0,
0,  0,
0,  0,  0,
0,  0,  0,                              1,
0,  0,  0,  0,                          1,                          2,
0,  0,  0,  0,                          1,  1,                      2,
0,  0,  0,  0,  0,                      1,  1,                      2,  2,
0,  0,  0,  0,  0,                      1,  1,  1,                  2,  2,
0,  0,  0,  0,  0,  0,                  1,  1,  1,                  2,  2,  2,
0,  0,  0,  0,  0,  0,                  1,  1,  1,  1,              2,  2,  2,                  3,
0,  0,  0,  0,  0,  0,  0,              1,  1,  1,  1,              2,  2,  2,  2,              3,              4,
0,  0,  0,  0,  0,  0,  0,              1,  1,  1,  1,  1,          2,  2,  2,  2,              3,  3,          4,
0,  0,  0,  0,  0,  0,  0,  0,          1,  1,  1,  1,  1,          2,  2,  2,  2,  2,          3,  3,          4,  4,
0,  0,  0,  0,  0,  0,  0,  0,          1,  1,  1,  1,  1,  1,      2,  2,  2,  2,  2,          3,  3,  3,      4,  4,
0,  0,  0,  0,  0,  0,  0,  0,  0,      1,  1,  1,  1,  1,  1,      2,  2,  2,  2,  2,  2,      3,  3,  3,      4,  4,  4,
0,  0,  0,  0,  0,  0,  0,  0,  0,      1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,      3,  3,  3,  3,  4,  4,  4,      5,
0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  1,  1,  1,  1,  1,  1,  1,  2,  2,  2,  2,  2,  2,  2,  3,  3,  3,  3,  4,  4,  4,  4,  5, 5
};


## Challenge

The challenge is to write a "reasonably fast" function or expression that replaces, and extends these lookup tables to index 719 or more.
Think of the lookup tables as a 3D structure of boxes. Pictured is the top 720 boxes of this structure.

## Input

An integer which is the index of a cube in the structure. You can assume the input will be in the range 0 to 719 inclusive.

## Output

The x,y,z coordinates for the given index. Assuming the input is between 0 and 719 the output ranges are x, 0 to 13 y, 0 to 27 z, 0 to 8

It's fine to accept and return larger indexes correctly just not required.

## Examples

    i  ->   x   y   z
0  ->   0,  0,  0
12  ->   0,  5,  1
30  ->   4,  8,  0
65  ->   2, 11,  1
100  ->   0, 13,  2
270  ->   1, 19,  3
321  ->   1, 20,  6
719  ->   1, 27,  8


If you collapse the z-coordinate, then the structure is indexed top-down left right like shown below; Examples are marked in square brackets []

Y,Z 0,
0   | [0]
1   |  1
2   |  2   3
3   |  4   5
4   |  6   7   8                                1,
5   |  9  10  11                                 |[12]                           2,
6   | 13  14  15  16                             | 17                             | 18
7   | 19  20  21  22                             | 23  24                         | 25
8   | 26  27  28  29 [30]                        | 31  32                         | 33  34
9   | 35  36  37  38  39                         | 40  41  42                     | 43  44
10   | 45  46  47  48  49  50                     | 51  52  53                     | 54  55  56                    3,
11   | 57  58  59  60  61  62                     | 63  64 [65] 66                 | 67  68  69                     | 70                4,
12   | 71  72  73  74  75  76  77                 | 78  79  80  81                 | 82  83  84  85                 | 86                 | 87
13   | 88  89  90  91  92  93  94                 | 95  96  97  98  99             [100] 101 102 103                |104 105             |106
14   |107 108 109 110 111 112 113 114             |115 116 117 118 119             |120 121 122 123 124             |125 126             |127 128
15   |129 130 131 132 133 134 135 136             |137 138 139 140 141 142         |143 144 145 146 147             |148 149 150         |151 152
16   |153 154 155 156 157 158 159 160 161         |162 163 164 165 166 167         |168 169 170 171 172 173         |174 175 176         |177 178 179        5,
17   |180 181 182 183 184 185 186 187 188         |189 190 191 192 193 194 195     |196 197 198 199 200 201         |202 203 204 205     |206 207 208         |209    6,
18   |210 211 212 213 214 215 216 217 218 219     |220 221 222 223 224 225 226     |227 228 229 230 231 232 233     |234 235 236 237     |238 239 240 241     |242     |243
19   |244 245 246 247 248 249 250 251 252 253     |254 255 256 257 258 259 260 261 |262 263 264 265 266 267 268     |269[270]271 272 273 |274 275 276 277     |278 279 |280
20   |281 282 283 284 285 286 287 288 289 290 291 |292 293 294 295 296 297 298 299 |300 301 302 303 304 305 306 307 |308 309 310 311 312 |313 314 315 316 317 |318 319 |320[321]
X->|  0   1   2   3   4   5   6   7   8   9  10 |  0   1   2   3   4   5   6   7 |  0   1   2   3   4   5   6   7 |  0   1   2   3   4 |  0   1   2   3   4 |  0   1 |  0   1


Note that at even y-coordinates the structure expands in the x-direction, and at 0 and 5 mod 6 in the z-direction.

# Rules

This is code-golf, the shortest code in bytes wins.

Reasonably fast As an additional requirement although not a competition of fastest code,
the code must still be shown to compute coordinates in a reasonable amount of time.
$$\\ O(n)\$$ or less time-complexity with regards to index is valid by default

Alternatively may for example use try it online or similar website and run a loop through all coordinates under 720 without exceeding the time limit of a minute, printing is optional.
Any time-complexity is valid as long as actual time is reasonably low.

Lookup tables are allowed but included in byte-count so aim to make them sparse if you choose to use them.

# Example code

EDIT: Look at Nick Kennedy's solution

Original example;

coord coords(int index){
int a=0,b=0,c=0;
int x=0,y=0,z=0;
long n,k,one;
n = k = 3;
int t=0;
while(t<index){
int s=0;k++;n=k;
while(n>1 && s<4){ n/=n&-n;n=n*3+1; n/=n&-n;s++;}
if(s==2)t++;
}
n=k;
one=n&-n;k = one;while(k>1){k>>=1;c++;} n=3*n+one;
one=n&-n;k = one;while(k>1){k>>=1;b++;} n=3*n+one;
one=n&-n;k = one;while(k>1){k>>=1;a++;}
coord r;
r.x = (b-c-1)>>1;
r.y = a-5;
r.z = (a-b-2)/6 +(a-b-4)/6;
return r;
}


Try it online! Note it's too slow!

• "storing information as you go" is forbidden. For example executing f(100) should not depend on having computed f(99) previously. I don't understand why you add this requirement on top of code-golf and restricted-time. It's also an unobservable requirement which is something that should be avoided in challenge writing. (Otherwise it's a good challenge I think) Jul 11, 2019 at 20:34
• To @JonathanAllan's point, if I'm reading that restriction correctly, you're essentially banning recursive functions, are you not? Jul 11, 2019 at 20:59
• @ Jonathan Allan and @Shaggy , what I had in mind was something like this , but I'm open to dropping the rule if it's a problem Jul 11, 2019 at 21:08
• Are you sure you want this to be a shortest code in bytes challenge? This feels more like an efficiency challenge. Maybe a version of both? In my typical language of choice, this is going to take up some bytes.... But I think I could whip something together moderately efficient in C++. Jul 12, 2019 at 7:42
• didn't understand the link with A055086, but found : A062052, A062053 ... A062060 Jul 12, 2019 at 8:36

# Python 3, 150 140 bytes

def f(n):
a=b=x=y=z=0
for i in range(n):
a=x-~x<y--~z//2*6+z%2
b=z<y//6+-~y//6
x=-~x*a
y+=not(a|b)
z+=b>a
z*=a|b
return x,y,z


Try it online!

Has $$\O(n)\$$ complexity. TIO footer prints first 720 values in about 0.5 seconds.

Thanks to @ElPedro and @PrincePolka for each saving 5 bytes!

• I'm not familiar with Python; what is the else:z,y=0,y+1 line doing? Jul 12, 2019 at 11:43
• @Shaggy if the condition from the previous line is not met, then z is set to zero and y is incremented by 1. Python allows tuple unpacking during assignment statements. Jul 12, 2019 at 12:06
• Since you apparently understand what the question is asking for, could you edit it to make it more intelligible for everyone else? Jul 12, 2019 at 12:09
• else:z=0;y+=1 does the same and is actually 1 byte shorter :) Jul 12, 2019 at 12:16
• And you can movex+=1 to the same line as if x<... to save another 4 bytes. Jul 12, 2019 at 12:20

# Jelly, 31 bytes

5,1ṁ9ĖŒṙṚḊḊḊ$Ƭz0ZUṬ€€ỊŒṪ’ṙÞ1ị@‘  A monadic link accepting an integer in $$\[0,719]\$$ which yields a list of three integers $$\[X, Y, Z]\$$. Try it online! Or see the test-suite (which completes in around 12-20s on TIO) ### How? Builds a lookup table and indexes into it: 5,1ṁ9ĖŒṙṚḊḊḊ$Ƭz0ZUṬ€€ỊŒṪ’ṙÞ1ị@‘ - Link: integer, n
5,1                             - pair literal = [5,1]
ṁ9                           - mould like 9 = [5,1,5,1,5,1,5,1,5]
Ė                          - enumerate = [[1,5],[2,1],[3,5],[4,1],[5,5],[6,1],[7,5],[8,1],[9,5]]
Œṙ                        - run-length-decode = [1,1,1,1,1,2,3,...,7,7,7,7,7,8,9,9,9,9,9]
Ṛ                       - reverse = [9,9,9,9,9,8,7,7,7,7,7,...,3,2,1,1,1,1,1]
Ḋ                      - dequeue = [9,9,9,9,8,7,7,7,7,7,...,3,2,1,1,1,1,1]
Ƭ                  - collect until a fixed-point:
$- last two links as a monad: Ḋ - dequeue Ḋ - dequeue - } = [[9,9,9,9,8,7,7,7,7,7,...,3,2,1,1,1,1,1],[9,9,8,7,...],[8,7,...],...,[1,1],[]] z0 - transpose with filler zero Z - transpose U - reverse each list Ṭ€€ - un-truth each int (e.g. 5 -> [0,0,0,0,1]) Ị - insignificant? (abs(x)<=1) (e.g. [0,0,0,0,1]->[1,1,1,1,1]) ŒṪ - truthy multi-dimensional 1-indexed indices ’ - decrement (i.e. all the [X,Y,Z] values) Þ - sort by: ṙ 1 - the list value rotated left by one (i.e. by [Y,Z,X]) ‘ - increment (n) (since Jelly is 1-indexed) @ - with swapped arguments: ị - index into  • @PrincePolka Note that it's quite common for askers on this stack to wait a good amount of time (a week or two) before accepting an answer. Jul 12, 2019 at 13:07 • Nice. If you don’t mind me asking, how did you end up with this approach? Jul 12, 2019 at 14:21 • @NickKennedy I saw the nice images of the 3d box structure and it just felt like it would probably be a good approach to "build that". I initially was trying to mould a range of the input numbers into the correct shape in order to find the first equal multidimensional index, but moved to building just the blocks. I do feel like there may be a way to build in a different orientation and avoid the sort and/or some of the z0ZU... Jul 12, 2019 at 15:53 # JavaScript, 93 85 bytes A port of Nick's Python solution. n=>(g=x=>n--?g(x<y+~z/2n*6n+z%2n>>1n?++x:z<y/6n-~y/6n?++z-z:z=++y-y):[x,y,z])(y=z=0n)  Try It Online! Saved 8 bytes thank to Arnauld's suggestion of using BigInts, plus a couple of other tweaks. # Jelly, 54 41 bytes HĊ×6_Ḃ{ạHḞ;;‘$:6SƊ}
<Ḋç/$T;3ḢṬ 0x3Ç+×¥$⁸¡


Try it online!

Loosely a Jelly translation of my Python 3 answer but much slower. Still $$\O(n)\$$ though. Outputs [x, z, y].