A305615 Next term is the largest earlier term that would not create a repetition of an earlier subsequence of length 2, if such a number exists; otherwise it is the smallest nonnegative number not yet in the sequence.

0, 0, 1, 1, 0, 2, 2, 1, 2, 0, 3, 3, 2, 3, 1, 3, 0, 4, 4, 3, 4, 2, 4, 1, 4, 0, 5, 5, 4, 5, 3, 5, 2, 5, 1, 5, 0, 6, 6, 5, 6, 4, 6, 3, 6, 2, 6, 1, 6, 0, 7, 7, 6, 7, 5, 7, 4, 7, 3, 7, 2, 7, 1, 7, 0, 8, 8, 7, 8, 6, 8, 5, 8, 4, 8, 3, 8, 2, 8, 1, 8, 0, 9, 9, 8, 9, 7, 9, 6, 9, 5, 9, 4, 9, 3, 9, 2, 9, 1, 9, 0

Offset: 0

Author

Luc Rousseau, Jun 06 2018

Keywords

• nonn
• nice

Comments

The map n |-> (a(n), a(n+1)) is a bijection between N and N X N: when drawn in a 2D array, this map makes progress by finishing the filling of a square gnomon before starting to fill the next one. This and the predictable zigzag way each gnomon is filled make it possible to deduce a closed formula for a(n).

A269501 is an essentially identical sequence: a(n) = A269501(n)-1. - N. J. A. Sloane, Jul 03 2018

For n > 3 indices for values = 1 are A008865(m), m > 2. - Bill McEachen, Oct 26 2023

Examples

			a(0): no already-used value exists, so one has to take the least nonnegative integer, so a(0) = 0;
a(1): reusing 0 is legal, so a(1) = 0. Repeating (0, 0) now becomes illegal;
a(2): reusing 0 is illegal since (a(1), a(2)) would repeat (0, 0). The smallest unused value is 1, so a(2) = 1. Repeating (0, 1) becomes illegal;
a(3): reusing 1 is legal. a(3) = 1. Repeating (1, 1) becomes illegal;
a(4): reusing 1 is illegal (would repeat (1, 1)) but reusing 0 is legal. a(4) = 0. Repeating (1, 0) becomes illegal;
and so on.
a(n) is also the x-coordinate of the cell that contains n in the following 2D infinite array:
  y
  ^
  |
  4 |... ... ... ... ...
    +---------------+
  3 | 9  14  12  10 |...
    +-----------+   |
  2 | 4   7   5 |11 |...
    +-------+   |   |
  1 | 1   2 | 6 |13 |...
    +---+   |   |   |
  0 | 0 | 3 | 8 |15 |...
    +---+---+---+---+---
      0   1   2   3   4 --->x
		

Links

• Eric Weisstein's World of Mathematics, Pairing function

Crossrefs

Cf. A000196, A053186, A269501, A008865.

For the 2D array shown in the EXAMPLE section, see A316323 and A269780. - N. J. A. Sloane, Jul 03 2018

Programs

Mathematica

A[n_] := Module[{k, t}, k = Floor[Sqrt[n]]; t = n - k^2;
  Boole[t != 0]*k - Boole[OddQ[t]]*(t - 1)/2]; Table[A[n], {n, 0, 100}]

PARI

a(n)=k=floor(sqrt(n));t=n-k^2;(t!=0)*k-(t%2)*(t-1)/2
for(n=0,100,print1(a(n),", "))

Prolog

main :- a(100, A, , ), reverse(A, R), writeln(R).
a(0, [0], [0], []) :- !.
a(N, A, V, P) :-
  M is N - 1, a(M, AA, VV, PP), AA = [AM | _],
  findall(L, (member(L, VV), not(member([AM, L], PP))), Ls),
  (Ls = [L | _] -> V = VV ; (length(VV, L), V = [L | VV])),
  A = [L | AA], P = [[AM, L] | PP].

Formula

a(n) = [t!=0]*k-[t is odd]*(t-1)/2, where k = floor(sqrt(n)), t = n-k^2 and [] stands for the Iverson bracket.