18
\$\begingroup\$

We can arrange the positive integers like this:

1_| 2 | 5 | 10
4___3_| 6 | 11
9___8___7_| 12
16  15  14  13

That is, in L-shaped brackets expanding down and right infinitely.

Then, we can read it off with the antidiagonals:

1 2 5  10
 / /  /
4 3  6  11
 /  /  /
9  8  7  12
  /  /  /
16 15 14  13

For the above, we read 1, then 2, 4, then 5, 3, 9, then 10, 6, 8, 16, and so on.

Your challenge is to output this sequence. Standard rules apply. This is A060736.

This is , shortest wins!

Improve this question
\$\endgroup\$

13 Answers 13

Reset to default
10
\$\begingroup\$

x86-64 machine code, 25 23 bytes

31 C0 48 01 C1 7F FB 29 C8 29 C1 7F 03 01 C8 48 01 C1 F7 E8 01 C8 C3

Try it online!

Following the fastcall calling convention, this takes a number n in ECX and returns the 1-indexed nth entry in EAX.

This works by first determining x and y coordinates in the grid. Then, letting m = min(x,y), the result is m2+m+1+y-x.

 │ 0 1 2 
─┼─┴─┴─┴x
0┤ 1 2 5
1┤ 4 3 6
2┤ 9 8 7
 y

In assembly:

f:  xor eax, eax    # Set EAX to 0.
r:  dec eax         # Subtract 1 from EAX.
                    # This will be the negative length of the current diagonal.
    add ecx, eax    # Add EAX to ECX.
    jg r            # Jump back if the result is positive --
                    #   if the index given has not been reached.
                    # When the loop ends, ECX will hold the negative 0-indexed reverse
                    #   position of the given index within its diagonal, equal to -x.
                    # EAX will hold the negative length of the diagonal, -x-y-1.
    sub eax, ecx    # Subtract ECX from EAX; EAX now holds -y-1.
    sub ecx, eax    # Subtract EAX from ECX, making ECX y-x+1.
    jg s            # Jump if that's positive.
    add eax, ecx    # (Otherwise: y<x) Add ECX to EAX, making EAX -x.
    dec eax         # Subtract 1 from EAX, making -x-1.
                    # Either way, EAX ends up as -m-1.
s:  add ecx, eax    # Add EAX to ECX, making ECX y-x-m.
    imul eax        # Multiply EAX by itself, making (-m-1)² = m²+2m+1.
    add eax, ecx    # Add ECX to EAX, making m²+m+1+y-x.
    ret             # Return.
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

JavaScript (ES7), 49 bytes

Returns the \$n\$-th term, 1-indexed.

n=>(t=(2*n)**.5+.5|0,t-=n-=t*~-t/2)<n?n*n-t:t*t+n

Try it online!

How?

This is a revamped version of the 2nd formula given on OEIS.

We define the 1-based index \$t\$ of the diagonal to which the \$n\$-th entry belongs (this is A002024):

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

We define the 1-based index \$N\$ representing the position of the entry in the diagonal (from top-right to bottom-left):

$$N=n-\frac{t(t-1)}{2}$$

We turn it into an index \$T\$ going from \$t-1\$ to \$0\$:

$$T=t-N$$

The figures below represent \$n\$, \$t\$, \$N\$ and \$T\$ respectively:

$$\begin{bmatrix} \color{red}1&2&\color{red}4&7\\ 3&\color{red}5&8\\ \color{red}6&9\\ 10 \end{bmatrix} \begin{bmatrix} \color{red}1&2&\color{red}3&4\\ 2&\color{red}3&4\\ \color{red}3&4\\ 4 \end{bmatrix} \begin{bmatrix} \color{red}1&1&\color{red}1&1\\ 2&\color{red}2&2\\ \color{red}3&3\\ 4 \end{bmatrix} \begin{bmatrix} \color{red}0&1&\color{red}2&3\\ 0&\color{red}1&2\\ \color{red}0&1\\ 0 \end{bmatrix}$$

The final result is given by:

$$\cases{N^2-T,&\text{if $T<N$}\\T^2+N,&\text{if $T\ge N$}}$$

Leading to:

$$\begin{bmatrix} \color{red}1&2&\color{red}5&10\\ 4&\color{red}3&6\\ \color{red}9&8\\ 16 \end{bmatrix}$$

Improve this answer
\$\endgroup\$
0
6
\$\begingroup\$

Haskell, 40 bytes

[k^2+k-n*min(2*k-n)1|n<-[1..],k<-[1..n]]

Attempt This Online!

-2 bytes thanks to @ovs.

Based on the Mathematica code on OEIS.

Improve this answer
\$\endgroup\$
0
5
\$\begingroup\$

J, 44 39 bytes

{.&;[:</.@(*+/\"1@,._1+<:/*2*]"0/)~1+i.

Try it online!

The formula might have been shorter, but I wanted to construct the matrix and use J's /. adverb to get the diagonals, because when you have a primitive to get diagonals you cannot not use it.

To construct the matrix, note that the successive deltas have an easy to describe pattern that looks like this:

 1  3  5  7  9 11 13
_1  3  5  7  9 11 13
_1 _1  5  7  9 11 13
_1 _1 _1  7  9 11 13
_1 _1 _1 _1  9 11 13
_1 _1 _1 _1 _1 11 13
_1 _1 _1 _1 _1 _1 13

and that the first column are the squares. So we just zip them together:

 1  1  3  5  7  9 11 13
 4 _1  3  5  7  9 11 13
 9 _1 _1  5  7  9 11 13
16 _1 _1 _1  7  9 11 13
25 _1 _1 _1 _1  9 11 13
36 _1 _1 _1 _1 _1 11 13
49 _1 _1 _1 _1 _1 _1 13

and then scan sum each row to reproduce the matrix:

 1  2  5 10 17 26 37 50
 4  3  6 11 18 27 38 51
 9  8  7 12 19 28 39 52
16 15 14 13 20 29 40 53
25 24 23 22 21 30 41 54
36 35 34 33 32 31 42 55
49 48 47 46 45 44 43 56
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Python, 67 bytes

n=0
while n:=n+1:[print(k*k+k-n*min(2*k-n,1))for k in range(1,n+1)]

Attempt This Online!

Port of Haskell. Outputs infinitely.

Old answer:

Python, 77 bytes

n=0
while n:=n+1:[print(n<2*k-1and-~k*k-n or(n-k)**2+k)for k in range(1,n+1)]

Attempt This Online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

C (gcc), 86 \$\cdots\$ 60 55 bytes

t;f(n){t=sqrt(2*n)+.5;n=(t-=n-=t*~-t/2)<n?n*n-t:t*t+n;}

Try it online!

Saved a whopping 13 bytes thanks to ceilingcat!!!
Saved yet another a whopping 13 18 bytes thanks to the man himself Arnauld!!!

Returns the \$n^\text{th}\$ term.
Uses the formula from A060736.

Improve this answer
\$\endgroup\$
0
3
\$\begingroup\$

Factor, 86 83 bytes

0 [ 1 + 3 dupn [1,b] [ 3 dupn sq + -rot 2 * over - 1 min * - . ] with each t ] loop

Attempt This Online!

Outputs the sequence indefinitely. Loosely based on alephalpha's Haskell answer.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Retina, 83 bytes

.+
*
(^_|\1_)*(_+)
$.2*$2$2,$.1*$($1___)__-$.2*2*$($1_);$1_
,|(_+)-\1_*

(_+);\1

_

Try it online! Link includes test cases. Outputs the nth term. Explanation: Loosely based on @alephalpha's formula.

.+
*

Convert n to unary.

(^_|\1_)*(_+)

Decompose n into a triangular number t-1 and a residue k in the range 1..t.

$.2*$2$2,$.1*$($1___)__-$.2*2*$($1_);$1_

Calculate k*k+k, t*t+t, 2*k*t and t.

,|(_+)-\1_*

Subtract 2*k*t from t*t+t, clamping the result at 0, and add on k*k+k.

(_+);\1

Subtract t from the previous result.

_

Convert to decimal.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

05AB1E, 19 bytes

[¼¾ENnN+¾N·¾-1‚ß*-,

Port of @alephalpha's Haskell answer.

Outputs indefinitely.

Try it online.

Explanation:

[                   # Loop indefinitely:
 ¼                  #  Increase variable `c` by 1 (0 by default)
  ¾E                #  Inner loop `N` in the range [1,`c`]:
                  , #   Pop and output:
    NnN+¾N·¾-1‚ß*-  #    N²+N-c*min(2N-c,1)
    Nn              #    N²
      N+            #      +N
                 -  #        -
        ¾       *   #         c*
             1‚ß    #           min(    ,1)
         N·         #               2N
           ¾-       #                 -c
Improve this answer
\$\endgroup\$
3
+100
\$\begingroup\$

Vyxal, 28 27 bytes

⇧Þ□λ÷N^›WDṘ²+^∑1<i;ÞZÞḋIRfi

Try it Online!

Based on @Arnauld's Javascript answer.

–1 per @emanresu A.

How?

λ÷N^›WDṘ²+^∑1<i; # find the (i, j)th entry of the matrix
λ              ; # lambda           STACK (top ->)
 ÷               # unwrap           i j
  N              # negate           i -j
   ^             # reverse stack    -j i
    ›            # increment        -j i+1
     W           # wrap             [i+1,-j]
                 #                = [N,-T] (using Arnaud's notation)
      D          # triplicate       [N,-T] [N,-T] [N,-T]
       Ṙ         # reverse          [N,-T] [N,-T] [-T,N]
        ²        # square           [N,-T] [N,-T] [T^2,N^2]
         +       # sum              [N,-T] [T^2+N,N^2-T]
          ^      # reverse stack    [T^2+N,N^2-T] [N,-T]
           ∑     # sum              [T^2+N,N^2-T] N-T
            1<   # is < 1?          [T^2+N,N^2-T] (1 if N-T<1 else 0)
                 #                = [T^2+N,N^2-T] (1 if T>=N else 0)
              i  # index            N^2-T if T>=N else T^2+N

⇧Þ□λ÷N^›WDṘ²+^∑1<i;ÞZ # make the matrix
⇧                     # double increment, pushing N+2
 Þ□                   # (Nx2)x(Nx2) identity matrix
   λ÷N^›WDṘ²+^∑1<i;   # (above function)
                   ÞZ # fill by coordinates, i.e. replace each entry
                      # of the matrix with the result of calling the
                      # function on the entry's list of coordinates

ÞḋIRfi # output              example (3x3 matrix)
Þḋ     # antidiagonals       [[5,3,9],[2,4],[1],[7],[6,8]]
  I    # into two pieces     [ [[5,3,9],[2,4],[1]] , [[7],[6,8]] ]
   R   # vectorized reverse  [ [[1],[2,4],[5,3,9]] , [[6,8],[7]] ]
    f  # flatten             [1,2,4,5,3,9,6,8,7]
     i # index by input
Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ Nice answer! i also works with (num, list) so you can shave off the ⁰ at the end. If you need any help with Vyxal, the Vyxal chat exists, and there's also a deadlineless bounty for Vyxal answers. \$\endgroup\$
    – emanresu A
    Commented Jun 12, 2022 at 8:57
  • 1
    \$\begingroup\$ By the way, in Vyxal, # is the line comment character (i.e. the interpreter ignores it and chars after it), so we typically use that for explanation comments \$\endgroup\$
    – Seggan
    Commented Jun 12, 2022 at 12:46
2
\$\begingroup\$

Python 3.8, 72 bytes

-18 bytes thanks to the formula of Arnauld and -10 bytes thanks to Kevin Cruijssen.

lambda n:(t:=int((2*n)**.5+.5),(n:=n-t*~-t/2)*n-(t:=t-n),t*t+n)[2-(t<n)]

Attempt this online

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ You need to use Python 3.8 for the walrus operator to work. TIO is out of date so you need to separately choose "Python 3.8 (pre-release)". Also, I believe int(...) is unnecessary, because usually, a trailing .0 does not matter. \$\endgroup\$
    – naffetS
    Commented May 26, 2022 at 12:56
  • 1
    \$\begingroup\$ You can save 2 bytes by changing replacing the t:=(...)//1 with t:=int(...) and (t-1) with ~-t. \$\endgroup\$
    – Kevin Cruijssen
    Commented May 27, 2022 at 8:01
  • 1
    \$\begingroup\$ 72 bytes: lambda n:(t:=int((2*n)**.5+.5),(n:=n-t*~-t/2)*n-(t:=t-n),t*t+n)[2-(t<n)] \$\endgroup\$
    – Kevin Cruijssen
    Commented May 27, 2022 at 8:24
2
\$\begingroup\$

APL+WIN, 22 bytes

Prompts for input matrix. Index origin = 0

(,m)[⍋+⌿(⍴m)⊤(⍳⍴,m←⎕)]

Try it online! Thanks to Dyalog Classic

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 32 bytes

ＮθＦθＦ⊕ι⊞υ⁻×⊕κ⁺²κ×⊕ι⊕⌊⟦⁰⁻⊗κι⟧Ｉ…υθ

Try it online! Link is to verbose version of code. Outputs the first n terms. Explanation: Based on @alephalpha's Haskell answer.

Ｎθ

Input n.

Ｆθ

Generate n antidiagonals, to avoid having to do square roots to find out how many antidiagonals are actually needed.

Ｆ⊕ι⊞υ⁻×⊕κ⁺²κ×⊕ι⊕⌊⟦⁰⁻⊗κι⟧

Compute the values on each antidiagonal.

Ｉ…υθ

Output the first n terms.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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