A097027 Function f(x) = phi(x) + floor(x/2) is iterated; a(n) is the length of transient if the iteration was initiated at n.

0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 3, 0, 0, 4, 1, 3, 2, 0, 0, 0, 3, 1, 2, 2, 3, 2, 0, 1, 0, 0, 1, 3, 0, 2, 3, 17, 1, 2, 1, 16, 2, 0, 0, 18, 2, 19, 1, 2, 2, 17, 1, 15, 3, 1, 2, 15, 1, 19, 20, 15, 0, 4, 18, 14, 19, 17, 16, 21, 2, 20, 21, 30, 22, 29, 16, 27, 3, 24, 25, 14, 19, 22, 23, 14, 20, 23

Offset: 1

Author

Labos Elemer, Aug 27 2004

Keywords

• nonn

Comments

Infinite iterations cannot be excluded, when a(n) is infinite. First at n=163?

For 1 <= n <= 1000, potentially infinite iterations at {163, 182, 196, 243, 283, 331, 423, 487, 495, 503, 511, 523, 533, 551, 559, 571, 583, 591, 593, 606, 611, 623, 642, 646, 651, 679, 685, 687, 725, 726, 729, 731, 732, 745, 746, 753, 755, 757, 758, 767, 779, 781, 783, 791, 799, 809, 811, 814, 839, 850, 855, 857, 859, 867, 869, 871, 875, 876, 885, 886, 888, 891, 895, 906, 908, 911, 913, 914, 915, 916, 921, 922, 923, 931, 937, 942, 959, 962, 964, 970, 971, 977, 985, 991} (tested to 1000 iterations). The maximum number of finite iterations in this range appears to be 96. - Michael De Vlieger, Mar 26 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], so a(70)=16.
n=2^j: a(2^j)=0, powers of 2 are fixed points of f, free of transients.
		

Crossrefs

Cf. A000010, A097026, A097028, A097029.

Programs

Maple

a:= proc(n) local i, m, p;
      p:= proc() -1 end; forget(p);
      p(n):= 0; m:= n;
      for i do m:= numtheory[phi](m)+iquo(m, 2);
               if p(m)>-1 then return p(m) fi;
               p(m):= i
      od
    end:
seq(a(n), n=1..162);  # Alois P. Heinz, Nov 13 2015

Mathematica

Table[Count[Values@ PositionIndex@ NestList[EulerPhi@ # + Floor[#/2] &, n, 10^3], k_ /; Length@ k == 1], {n, 89}] (* Michael De Vlieger, Mar 26 2017, Version 10 *)