cp's OEIS Frontend

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.

%I A305615 #44 Feb 16 2025 08:33:54
%S A305615 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,
%T A305615 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,
%U A305615 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
%N 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.
%C A305615 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).
%C A305615 A269501 is an essentially identical sequence: a(n) = A269501(n)-1. - _N. J. A. Sloane_, Jul 03 2018
%C A305615 For n > 3 indices for values = 1 are A008865(m), m > 2. - _Bill McEachen_, Oct 26 2023
%H A305615 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PairingFunction.html">Pairing function</a>
%F A305615 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.
%e A305615 a(0): no already-used value exists, so one has to take the least nonnegative integer, so a(0) = 0;
%e A305615 a(1): reusing 0 is legal, so a(1) = 0. Repeating (0, 0) now becomes illegal;
%e A305615 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;
%e A305615 a(3): reusing 1 is legal. a(3) = 1. Repeating (1, 1) becomes illegal;
%e A305615 a(4): reusing 1 is illegal (would repeat (1, 1)) but reusing 0 is legal. a(4) = 0. Repeating (1, 0) becomes illegal;
%e A305615 and so on.
%e A305615 a(n) is also the x-coordinate of the cell that contains n in the following 2D infinite array:
%e A305615   y
%e A305615   ^
%e A305615   |
%e A305615   4 |... ... ... ... ...
%e A305615     +---------------+
%e A305615   3 | 9  14  12  10 |...
%e A305615     +-----------+   |
%e A305615   2 | 4   7   5 |11 |...
%e A305615     +-------+   |   |
%e A305615   1 | 1   2 | 6 |13 |...
%e A305615     +---+   |   |   |
%e A305615   0 | 0 | 3 | 8 |15 |...
%e A305615     +---+---+---+---+---
%e A305615       0   1   2   3   4 --->x
%t A305615 A[n_] := Module[{k, t}, k = Floor[Sqrt[n]]; t = n - k^2;
%t A305615   Boole[t != 0]*k - Boole[OddQ[t]]*(t - 1)/2]; Table[A[n], {n, 0, 100}]
%o A305615 (Prolog)
%o A305615 main :- a(100, A, _, _), reverse(A, R), writeln(R).
%o A305615 a(0, [0], [0], []) :- !.
%o A305615 a(N, A, V, P) :-
%o A305615   M is N - 1, a(M, AA, VV, PP), AA = [AM | _],
%o A305615   findall(L, (member(L, VV), not(member([AM, L], PP))), Ls),
%o A305615   (Ls = [L | _] -> V = VV ; (length(VV, L), V = [L | VV])),
%o A305615   A = [L | AA], P = [[AM, L] | PP].
%o A305615 (PARI)
%o A305615 a(n)=k=floor(sqrt(n));t=n-k^2;(t!=0)*k-(t%2)*(t-1)/2
%o A305615 for(n=0,100,print1(a(n),", "))
%Y A305615 Cf. A000196, A053186, A269501, A008865.
%Y A305615 For the 2D array shown in the EXAMPLE section, see A316323 and A269780. - _N. J. A. Sloane_, Jul 03 2018
%K A305615 nonn,nice
%O A305615 0,6
%A A305615 _Luc Rousseau_, Jun 06 2018