Find X,Y,Z coordinates from index

5

2

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 ⌊√4n+1⌋−1

and the formula for A082375 is ⌊√4⌊x⌋+1⌋−1−⌊12(4⌊x⌋+1−⌊√4⌊x⌋+1⌋2)⌋

So the formula for A062052 most likely is

8⋅2⌊√4⌊x⌋+1⌋−2⌊√4⌊x⌋+1⌋−1−⌊12(4⌊x⌋+1−⌊√4⌊x⌋+1⌋2)⌋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.

challenge

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!

PrincePolka

Posted 6 years ago

Reputation: 653

8"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) – Jonathan Allan – 6 years ago

1To @JonathanAllan's point, if I'm reading that restriction correctly, you're essentially banning recursive functions, are you not? – Shaggy – 6 years ago

@ 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

– PrincePolka – 6 years ago

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++. – ouflak – 6 years ago

didn't understand the link with A055086, but found : A062052, A062053 ... A062060 – Nahuel Fouilleul – 6 years ago

@NahuelFouilleul You can use the A022332 and A055086 sequences to get the A062052 sequence like so ... (16*2^2^A022332(n) - 2^A055086(n) )/3 = A062052(n) , Similarly you can get the A062053 sequence from the X,Y,Z sequences in this challenge.

– PrincePolka – 6 years ago

@ouflak Bytes is a simpler measure than efficiency. Also it naturally deters lookup-table based solutions. – PrincePolka – 6 years ago

@NahuelFouilleul might have messed that up but here is an example

– PrincePolka – 6 years ago

I've tidied up the MathJax expressions by applying simple transformation rules, but I haven't a clue what the second one is supposed to show (what's x? In what way does this "plot these numbers in their natural order"?), and I can't make any sense out of the rest of the question. – Peter Taylor – 6 years ago

@PrincePolka, thank you for the explanations, wouldn't be easier to generate first sequence from (m>=1,n>=0) (2^(2*m)-1)/3*2^n, and the second sequence from the first (2^(2*m)*S-1)/3*2^n where S is an element of first sequence (or element2) so that `(2^(2m)*S-1)` is a multiple of 3 – Nahuel Fouilleul – 6 years ago

@ Peter Taylor thanks for the help, by natural I mean t ascending. x is n just i used desmos to plot it and it doesn't accept n, also thats the reason behind floor() , @NahuelFouilleul thanks for the idea, I'll look into it – PrincePolka – 6 years ago

@NahuelFouilleul I got A198584 which doesn't include the evens figured out. Maybe with some modification this can generate A062053?https://pastebin.com/RqjDqk6k

– PrincePolka – 6 years ago

Answers

4

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

Jonathan Allan

Posted 6 years ago

Reputation: 67 804

1@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. – Jonathan Allan – 6 years ago

Nice. If you don’t mind me asking, how did you end up with this approach? – Nick Kennedy – 6 years ago

@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... – Jonathan Allan – 6 years ago

5

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!

Nick Kennedy

Posted 6 years ago

Reputation: 11 829

I'm not familiar with Python; what is the else:z,y=0,y+1 line doing? – Shaggy – 6 years ago

1@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. – Nick Kennedy – 6 years ago

Since you apparently understand what the question is asking for, could you edit it to make it more intelligible for everyone else? – Peter Taylor – 6 years ago

else:z=0;y+=1 does the same and is actually 1 byte shorter :) – ElPedro – 6 years ago

And you can movex+=1 to the same line as if x<... to save another 4 bytes. – ElPedro – 6 years ago

Ah, I see now; it was the equivalent of [z,y]=[0,y+1] in JS. – Shaggy – 6 years ago

140 bytes – PrincePolka – 6 years ago

3

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.

Shaggy

Posted 6 years ago

Reputation: 24 623

2

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].

Nick Kennedy

Posted 6 years ago

Reputation: 11 829

Asked: 6 years ago

Viewed: 443 times

Active: 6 years ago