|
| |
|
|
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.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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).
|
|
|
LINKS
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
