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