A182321 Number of iterations of A025581(n) required to reach 0.

0, 1, 2, 1, 3, 2, 1, 2, 3, 2, 1, 4, 2, 3, 2, 1, 3, 4, 2, 3, 2, 1, 2, 3, 4, 2, 3, 2, 1, 3, 2, 3, 4, 2, 3, 2, 1, 4, 3, 2, 3, 4, 2, 3, 2, 1, 3, 4, 3, 2, 3, 4, 2, 3, 2, 1, 2, 3, 4, 3, 2, 3, 4, 2, 3, 2, 1

Offset: 0

Author

Patrick Devlin, Apr 24 2012

Keywords

• nonn

Comments

Following the notation in the link, for n >= 0, let n = (0 + 1 + 2 + ... + f(n)) - g(n) be the representation of n with f(n) and g(n) minimal such that 0 <= g(n) <= f(n). Then f(n) = A002024(n) = round(sqrt(2n)), and g(n) = A025581(n) = f(n)*(f(n)+1)/2 - n.

With this notation, a(n) is the number of iterations of g(n) needed to reach 0.

The sequence a(n) is essentially the function phi(n) of the link.

The sequence a(n) has a high degree of fractal-like symmetry. Consider, for instance, the sequence in the triangular array (read left to right then top to bottom, with the term for a(0) on top):

0

1

2 1

3 2 1

2 3 2 1

Then the rows of this triangle (read from right to left) are simply 1+a(n).

a(n) is related to the recurrence between A186053 and A182298.

For n >= 1, a(n) is the number of terms in the minimal alternating triangular-number representation of n+1, defined at A255974. - Clark Kimberling, Apr 10 2015

Examples

			g(8) = 2, g(2) = 1, g(1) = 0.  Therefore a(8) = 3.
		

Links

• Clark Kimberling, Table of n, a(n) for n = 0..1000
• Patrick Devlin, Integer Subsets with High Volume and Low Perimeter, arXiv:1202.1331v1 [math.CO]

Crossrefs

Cf. A025581, A002024, A255974.

Programs

Maple

# With this code, the n-th term of the sequence is given by a call to a(n)
f:=n->round(sqrt(2*n)): g:=n->f(n)*(f(n)+1)/2-n:
a:=proc(n) option remember:
  if n < 1 then return 0: fi: return 1 + a(g(n)):
end proc:

Mathematica

(* This program computes the sequence as the number of terms in the minimal alternative triangular-number representation of n+1. *)
b[n_] := n (n + 1)/2; bb = Table[b[n], {n, 0, 1000}];
s[n_] := Table[b[n], {k, 1, n}];
h[1] = {1}; h[n_] := Join[h[n - 1], s[n]]; g = h[100]; r[0] = {0};
r[n_] := If[MemberQ[bb, n], {n}, Join[{g[[n]]}, -r[g[[n]] - n]]];
Join[{0}, Rest[Table[Length[r[n]], {n, 0, 100}]]] (* A182321 for n >= 1 *)
(* Clark Kimberling, Apr 10 2015 *)

Formula

The Devlin link shows a(n) < log_2(log_2(n/2)) + 2.