OFFSET
0,6
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).
For n > 3 indices for values = 1 are A008865(m), m > 2. - Bill McEachen, Oct 26 2023
LINKS
Eric Weisstein's World of Mathematics, Pairing function
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.
EXAMPLE
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
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}]
PROG
(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].
(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), ", "))
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Luc Rousseau, Jun 06 2018
STATUS
approved