New Order #6: Easter Egg

Question

Introduction (may be ignored)

Putting all positive integers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive integers. This is the sixth challenge in this series (links to the first, second, third, fourth and fifth challenge).

This challenge has a mild Easter theme (because it's Easter). I took my inspiration from this highly decorated (and in my personal opinion rather ugly) goose egg.

It reminded me of the Ulam spiral, where all positive integers are placed in a counter-clockwise spiral. This spiral has some interesting features related to prime numbers, but that's not relevant for this challenge.

We get to this challenge's permutation of positive integers if we take the numbers in the Ulam spiral and trace all integers in a clockwise turning spiral, starting at 1. This way, we get:

1, 6, 5, 4, 3, 2, 9, 8, 7, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, etc.

If you would draw both of the spirals, you'd get some sort of an infinite mesh of (egg shell) spirals (note the New Order reference there).

This sequence is present in the OEIS under number A090861. Since this is a "pure sequence" challenge, the task is to output \$a(n)\$ for a given \$n\$ as input, where \$a(n)\$ is A090861.

Task

Given an integer input \$n\$, output \$a(n)\$ in integer format, where \$a(n)\$ is A090861.

Note: 1-based indexing is assumed here; you may use 0-based indexing, so \$a(0) = 1; a(1) = 6\$, etc. Please mention this in your answer if you choose to use this.

Test cases

Input | Output
---------------
1     |  1
5     |  3
20    |  10
50    |  72
78    |  76
123   |  155
1234  |  1324
3000  |  2996
9999  |  9903
29890 |  29796

Rules

• Input and output are integers.
• Your program should at least support input in the range of 1 up to 32767).
• Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
• Default I/O rules apply.
• Default loopholes are forbidden.
• This is code-golf, so the shortest answers in bytes wins

Answer 1

Jelly,  16 14 11 10 9  8 bytes

-1 thanks to Lynn (mod-2; logical NOT; add to self: Ḃ¬+ -> bitwise OR with 1:|1)

|1×r)ẎQi

A monadic Link accepting an integer, n, which yields an integer, a(n).

Try it online! (very inefficient since it goes out to layer \$\lceil\frac n2\rceil\$)

An 11-byte version, ½‘|1×rƲ€ẎQi, completes all but the largest test case in under 30s - Try it at TIO - this limits the layers used to \$\lceil\frac{\lfloor\sqrt n\rfloor+1}2\rceil\$.

How?

The permutation is to take the natural numbers in reversed slices of lengths [1,5,3,11,5,17,7,23,9,29,11,35,13,...] - the odd positive integers interspersed with the positive integers congruent to five modulo six, i.e [1, 2*3-1, 3, 4*3-1, 5, 6*3-1, 7, 8*3-1, 9, ...].

This is the same as concatenating and then deduplicating reversed ranges [1..x] of where x is the cumulative sums of these slice lengths (i.e. the maximum of each slice) - [1,6,9,20,25,42,49,72,81,110,121,156,169,...], which is the odd integers squared interspersed with even numbers multiplied by themselves incremented, i.e. [1*1, 2*3, 3*3, 4*5, 5*5, 6*7, 7*7,...].

Since the differences are all greater than 1 we can save a byte (the reversal) by building ranges [x..k] directly, where k is the 1-indexed index of the slice.

Due to this structure the permutation is a self-conjugate permutation, i.e. we know that \$P(n) = v \iff P(v) = n\$, so rather than finding the value at (1-indexed) index n (|1×r)ẎQị@) we can actually get the (1-indexed) index of the first occurrence of n (|1×r)ẎQi).

|1×r)ẎQi - Link: integer, n       e.g. 10
    )    - for each k in [1..n]:  vs = [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
|1       -   bitwise-OR (k) with 1     [ 1, 3, 3, 5, 5, 7, 7, 9, 9,11]
  ×      -   multiply (by k)           [ 1, 6, 9,20,25,42,49,72,81,110]
   r     -   inclusive range (to k)    [[1],[6..2],[9..3],[20..4],...,[110..10]]
     Ẏ   - tighten                     [1,6,5,4,3,2,9,8,7,6,5,4,3,20,...,4,......,110,...,10]
      Q  - de-duplicate                [1,6,5,4,3,2,9,8,7,20,...,10,......,110,...82]
       i - first index with value (n)  20

Answer 2

JavaScript (ES7),  46 45  41 bytes

0-indexed.

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Try it online!

How?

This is based on the 1-indexed formula used in the example programs of A090861.

\$x_n\$ is the layer index of the spiral, starting with \$0\$ for the center square:

$$x_n=\left\lfloor\frac{\sqrt{n-1}+1}{2}\right\rfloor$$

Try it online!

\$k_n\$ is set to \$6\$ for the bottom part of each layer (including the center square), and to \$-2\$ everywhere else:

$$k_n=\begin{cases} -2&\text{if }n\le 4{x_n}^2+2x_n\\ 6&\text{otherwise} \end{cases}$$

Try it online!

Then \$a_n\$ is given by:

$$a_n=8{x_n}^2+k_nx_n+2-n$$

Try it online!

Which can be translated into:

n=>8*(x=(n-1)**.5+1>>1)*x+(n<=4*x*x+2*x?-2:6)*x+2-n

Making it 0-indexed saves 5 bytes right away:

n=>8*(x=n**.5+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n

The formula can be further simplified by using:

$${x'}_n=2\times\left\lfloor\frac{\sqrt{n}+1}{2}\right\rfloor$$

which can be expressed as:

x=n**.5+1&~1

leading to:

n=>2*(x=n**.5+1&~1)*x+(n<x*x+x?-1:3)*x+1-n

and finally:

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Answer 3

Wolfram Language (Mathematica), 60 bytes

8(s=⌊(⌊Sqrt[#-1]⌋+1)/2⌋)^2-#+2+If[#<=4s^2+2s,-2,6]s&

Try it online!

Answer 4

MATL, 12 11 bytes

Eq1YL!tPG=)

Try it online!

Very memory-inefficient. Prepending X^k makes it more efficient.

Answer 5

C# (Visual C# Interactive Compiler), 67 bytes

n=>8*(x=(int)Math.Sqrt(--n)+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n;int x;

Try it online!

Answer 6

Python 3.8, 104 74 65 60 57 bytes

lambda n:(-2,6)[n>4*(x:=(n**.5+1)//2)*x+2*x]*x+2+~n+8*x*x

Edit: Thanks to Johnathan Allan for getting it from 74 to 57 bytes!

This solution uses 0-based indexing.

Answer 7

Python 3.8 (pre-release), 53 bytes

A direct port of Arnauld's JavaScript answer, go upvote that, and/or J42161217's Mathematica answer, and/or Kapocsi's Python answer :)

lambda n:((x:=int(n**.5+1)&-2)*2-(n<x*x+x)*4+3)*x+1-n

0-indexed.

Try it online!

Answer 8

Befunge, 67 57 bytes

This solution assumes 0-based indexing for the input values.

p&v-*8p00:+1g00:<
0:<@.-\+1*g00+*<|`
0g6*\`!8*2+00g4^>$:0

Try it online!

Explanation

We start by calculating the "radius" at which the input n is found with a loop:

radius = 0
while n > 0
  radius += 1
  n -= radius*8

At the end of the loop, the previous value of n is the offset into the spiral at that radius:

offset = n + radius*8

We can then determine if we're on the top or bottom section of the spiral as follows:

bottom = offset >= radius*6

And once we have all these details, the spiral value is calculated with:

value = ((bottom?10:2) + 4*radius)*radius + 1 - offset

The radius is the only value that we need to store as a "variable", limiting it to a maximum value of 127 in Befunge-93, so this algorithm can handle inputs up to 65024.

Answer 9

Japt, 15 bytes

Port of Jonathan's Jelly solution. 1-indexed.

gUòȲ+X*v)õÃcÔâ

Try it

gUòȲ+X*v)õÃcÔâ     :Implicit input of integer U
g                   :Index into
 Uò                 :  Range [0,U]
   È                :  Map each X
    ²               :    Square X
     +X*            :    Add X multiplied by
        v           :    1 if X is divisible by 2, 0 otherwise
         )          :    Group result
          õ         :    Range [1,result]
           Ã        :  End map
            c       :  Flatten
             Ô      :    After reversing each
              â     :  Deduplicate

Answer 10

Husk, 11 bytes

!uṁS`…S*v1N

Try it online!

Instead of creating a range, an infinite list is created and nubbed. Hence, will be be very very slow for larger \$n\$

Answer 11

C++ (gcc), 88 bytes

#import<cmath>
int a(int n){int x=(sqrt(n-1)+1)/2;return x*(8*(x+(n>4*x*x+2*x))-2)+2-n;}

1-indexed; uses the formula on the OEIS page, but manipulated to save a few bytes.

Try it online!

Answer 12

Vyxal, 13 bytes

ƛ1⋎*›rṘ;fU?‹i

Try it Online!

Messy port