5
\$\begingroup\$

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.

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!

\$\endgroup\$
  • 8
    \$\begingroup\$ "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) \$\endgroup\$ – Jonathan Allan Jul 11 at 20:34
  • 1
    \$\begingroup\$ To @JonathanAllan's point, if I'm reading that restriction correctly, you're essentially banning recursive functions, are you not? \$\endgroup\$ – Shaggy Jul 11 at 20:59
  • \$\begingroup\$ @ 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 \$\endgroup\$ – PrincePolka Jul 11 at 21:08
  • \$\begingroup\$ 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++. \$\endgroup\$ – ouflak Jul 12 at 7:42
  • \$\begingroup\$ didn't understand the link with A055086, but found : A062052, A062053 ... A062060 \$\endgroup\$ – Nahuel Fouilleul Jul 12 at 8:36
4
\$\begingroup\$

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
\$\endgroup\$
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Jonathan Allan Jul 12 at 13:07
  • \$\begingroup\$ Nice. If you don’t mind me asking, how did you end up with this approach? \$\endgroup\$ – Nick Kennedy Jul 12 at 14:21
  • \$\begingroup\$ @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... \$\endgroup\$ – Jonathan Allan Jul 12 at 15:53
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ I'm not familiar with Python; what is the else:z,y=0,y+1 line doing? \$\endgroup\$ – Shaggy Jul 12 at 11:43
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – Nick Kennedy Jul 12 at 12:06
  • \$\begingroup\$ Since you apparently understand what the question is asking for, could you edit it to make it more intelligible for everyone else? \$\endgroup\$ – Peter Taylor Jul 12 at 12:09
  • \$\begingroup\$ else:z=0;y+=1 does the same and is actually 1 byte shorter :) \$\endgroup\$ – ElPedro Jul 12 at 12:16
  • \$\begingroup\$ And you can movex+=1 to the same line as if x<... to save another 4 bytes. \$\endgroup\$ – ElPedro Jul 12 at 12:20
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.