13
\$\begingroup\$

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.

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

Ulam spiral

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 , so the shortest answers in bytes wins
\$\endgroup\$

10 Answers 10

12
\$\begingroup\$

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
\$\endgroup\$
  • 2
    \$\begingroup\$ Very nice. And you surpassed the MATL answer! \$\endgroup\$ – agtoever Apr 20 at 21:35
  • 1
    \$\begingroup\$ Tied now... :-) \$\endgroup\$ – Luis Mendo Apr 21 at 2:46
  • \$\begingroup\$ @LuisMendo I just realised I can do something sneaky here and save one byte :) \$\endgroup\$ – Jonathan Allan Apr 21 at 3:19
  • 1
    \$\begingroup\$ @JonathanAllan Aww. That deserves one upvote :-) \$\endgroup\$ – Luis Mendo Apr 21 at 3:22
  • 1
    \$\begingroup\$ @Lynn I am actually just updating to a different 9 byter. Yours will prob make 8! \$\endgroup\$ – Jonathan Allan Apr 22 at 17:29
6
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 60 bytes

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

Try it online!

\$\endgroup\$
5
\$\begingroup\$

MATL, 12 11 bytes

Eq1YL!tPG=)

Try it online!

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

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ Save 39 avoiding the imports, removing some redundant parentheses, and using > in place of <= and x*x in place of x**2 ...like so: def f(n):x=((n-1)**.5+1)//2;return 8*x**2+(-2,6)[n>4*x*x+2*x]*x+2-n ...TIO \$\endgroup\$ – Jonathan Allan Apr 20 at 23:07
  • \$\begingroup\$ Awesome! I will incorporate the edits. Made some changes before I saw your comment and got it down to 74 bytes. Does it matter that yours returns floats? I assume not... \$\endgroup\$ – Kapocsi Apr 20 at 23:11
  • \$\begingroup\$ Float representations of integers should be fine. Save some more using Python 3.8 assignment ...EDIT: make it zero indexed \$\endgroup\$ – Jonathan Allan Apr 20 at 23:14
  • \$\begingroup\$ Very cool. Feel free to make any further edits directly! \$\endgroup\$ – Kapocsi Apr 20 at 23:27
3
\$\begingroup\$

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!

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

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I just told Jonathan that x+(1-x%2) is x|1 (saving a byte in Jelly), which this answer can also benefit from, I bet. \$\endgroup\$ – Lynn Apr 22 at 17:26
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Suggest sqrt(n-1)/2+.5 instead of (sqrt(n-1)+1)/2 \$\endgroup\$ – ceilingcat Apr 22 at 21:54

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.