A097026 Function f(x) = phi(x) + floor(x/2) is iterated, starting at x=n; a(n) is the length of terminal cycle (or 0 if no finite cycle exists).

1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 4, 1, 1, 1, 2, 1, 4, 4, 2, 1, 4, 4, 2, 4, 2, 2, 6, 4, 2, 4, 6, 4, 2, 2, 6, 4, 6, 2, 1, 2, 6, 2, 6, 2, 1, 1, 6, 2, 6, 6, 6, 1, 2, 6, 6, 6, 6, 6, 6, 2, 6, 6, 6, 6, 6, 6, 6, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 2, 6, 6, 6, 6, 6, 6, 6, 6, 6

Offset: 1

Author

Labos Elemer, Aug 27 2004

Keywords

• nonn

Comments

While iteration of phi(x) always leads to a fixed point, f(x) = phi(x) + incr(x) may result in cycles or be divergent. What is the magnitude of the added incrementing function?

Some initial values are hard to analyze. The first is n=163, so perhaps a(163)=0 by definition.

Observation regarding the above comment: most n <= 1000 have 1 <= a(n) <= 12; the following have unresolved cycles at 10^3 iterations of f(x): {163, 182, 196, 243, 283, 331, 423, 487, 495, 503, 511, 523, 533, 551, 559, 571, 583, 591, 593, ...}. - Michael De Vlieger, May 16 2017

Examples

			n=70: iteration list = {70, 59, 87, 99, 109, 162, 135, 139, 207, 235, 301, 402, 333, 382, 381, 442, [413, 554, 553, 744, 612, 498], 413}, a(70)=6;
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..162
• Michael De Vlieger, Table of n, a(n) for n = 1..1000 with 0 representing terms that have unresolved cycles at 10^3 iterations of f(x).

Crossrefs

Cf. A000010, A097027, A097028, A097029.

Programs

Mathematica

With[{nn = 10^3}, Table[Count[Values@ PositionIndex@ NestList[EulerPhi@ # + Floor[#/2] &, n, nn], s_ /; Length@ s > 1], {n, 105}]] (* Michael De Vlieger, May 16 2017 *)

PARI

findpos(newn, v) = {forstep(k=#v, 1, -1, if (v[k] == newn, return(k)););}
a(n) = {ok = 0; v = [n]; while(!ok, newn = eulerphi(n) + n\2; ipos = findpos(newn, v); if (ipos, ok = 1; break); v = concat(v, newn); n = newn;); #v - ipos + 1;} \\ Michel Marcus, Jan 03 2017

Formula

For n=2^j: a(2^j)=1, powers of 2 are fixed points.