A097027 -id:A097027 - cp's OEIS frontend

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

Labos Elemer, Aug 27 2004

nonn

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

			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;

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).

Cf. A000010, A097027, A097028, A097029.

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 *)

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

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

A097028 Function f(x) = EulerPhi(x) + floor(x/2) is iterated; a(n) is the length of transient part and terminal cycle if the iteration was initiated at n. So a(n) is the number of distinct terms arising during iteration.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 3, 1, 2, 2, 2, 3, 3, 4, 1, 1, 5, 2, 5, 3, 2, 2, 4, 4, 2, 3, 4, 4, 6, 4, 3, 1, 4, 5, 5, 4, 4, 5, 23, 5, 4, 5, 22, 6, 2, 2, 24, 6, 25, 3, 3, 4, 23, 3, 21, 5, 2, 3, 21, 3, 25, 26, 21, 1, 6, 24, 20, 25, 23, 22, 27, 4, 26, 27, 36, 28, 35, 22, 33, 5, 30, 31, 20, 25, 28, 29, 20, 26, 29

Offset: 1

Labos Elemer, Aug 27 2004

nonn

Observation (see also Labos Elemer's comment at A097026): most n < 1000 have 1 <= a(n) <= 108; the following have a(n) > 1000 if finite: {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}. - Michael De Vlieger, Feb 27 2017

			For 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) = 22.
n=2^j: a(2^j)=1, powers of 2 are fixed points, free of transients, so t + c = 0 + 1 = 1.

Cf. A000010, A097026, A097028, A097029.

Table[Length@ Union@ NestList[EulerPhi@ # + Floor[#/2] &, n, 10^3], {n, 10^3}] (* Michael De Vlieger, Feb 27 2017 *)

a(n) = A097026(n) + A097027(n) = c(n) + t(n).

A097029 Fixed points when the function f(x) = phi(x) + floor(x/2) is iterated, i.e., solutions to f(x) = x.

Original entry on oeis.org

1, 2, 3, 4, 8, 15, 16, 32, 64, 128, 255, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65535, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 83623935, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967295

Offset: 1

Labos Elemer, Aug 27 2004

nonn

Trivial fixed points are the powers of 2. How many nontrivial cases exist like 3, 15, 255, 65535: the first 5 terms of A051179. More?

83623935 is the next such term (see also A050474 and A203966). - Michel Marcus, Nov 13 2015

			For fixed points the cycle lengths are A097026(n=fix)=1, but the reverse is not true because long transients may also lead to 1-cycles.
So, e.g., 1910 is not here because its terminal 1-cycle is prefixed by a long transient: {1910, 1715, 2033, 2924, 2806, 2723, 3689, 4724, 4722, 3933, 4342, 4163, 6041, 8192, 8192}.

Max Alekseyev, Table of n, a(n) for n = 1..91

Union of A000079 and A050474.

Cf. A000010, A051179, A097026, A097027, A097028.

isok(n) = eulerphi(n) + n\2 == n; \\ Michel Marcus, Nov 13 2015

a(30)-a(35) from Michel Marcus, Nov 13 2015

a(36)-a(38) from Jinyuan Wang, Jul 22 2021

A280577 a(n) = eulerphi(n) + floor(n/2).

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 9, 8, 10, 9, 15, 10, 18, 13, 15, 16, 24, 15, 27, 18, 22, 21, 33, 20, 32, 25, 31, 26, 42, 23, 45, 32, 36, 33, 41, 30, 54, 37, 43, 36, 60, 33, 63, 42, 46, 45, 69, 40, 66, 45, 57, 50, 78, 45, 67, 52, 64, 57, 87, 46, 90, 61, 67, 64, 80, 53, 99, 66, 78

Offset: 1

Michel Marcus, Jan 05 2017

Cf. A000010, A004526.

Cf. A097026, A097027, A097028, A097029.

with(numtheory): A280577:=n->phi(n)+floor(n/2): seq(A280577(n), n=1..100); # Wesley Ivan Hurt, Jan 05 2017

Table[EulerPhi[n] + Floor[n/2], {n, 100}] (* Wesley Ivan Hurt, Jan 05 2017 *)

PARI
```
a(n) = eulerphi(n) + floor(n/2);
```

a(n) = A000010(n) + A004526(n).

G.f.: x^2/((1 + x)*(1 - x)^2) + Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Jan 05 2017

A280578 Integers that are fixed points of some iteration of f(x) = phi(x) + floor(x/2), see A280577.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 9, 10, 15, 16, 21, 22, 23, 30, 32, 33, 36, 45, 46, 64, 128, 255, 256, 413, 498, 512, 513, 514, 553, 554, 580, 612, 744, 765, 766, 1024, 1073, 1125, 1162, 1250, 1540, 1544, 2048, 2241, 2413, 2457, 2458, 2522, 2524, 2596, 2754, 2889, 3348, 3352, 3474, 4096

Offset: 1

Michel Marcus, Jan 05 2017

nonn

A097029 is the subsequence of integers that are fixed points of one iteration.

Up to 10^9, one can find cycles of length: 1, 2, 3, 4, 5, 6, 8, 10, 12, 20.

Michel Marcus, Table of n, a(n) for n = 1..178
Michel Marcus, Cycles up to 10^7

Cf. A000010, A004526.
Cf. A097026, A097027, A097028, A097029.
Cf. A280577.

iscycle(v, nextn) = for (i=1, #v, if (v[i] == nextn, return (1); ); ); return (0);
fcycle(n, known) = {v = vector(1); v[1] = n; first = n; while ((nextn = eulerphi(n) + n\2) <= first, if (vecsearch(known, nextn), return([])); if (iscycle(v, nextn), return (v)); v = concat(v, nextn); n = nextn; ); return ([]);}
lista(nn) = {known = []; for (n = 1, nn, v = fcycle(n, known); if (#v, known = vecsort(concat(known, v)));); print(known);} \\ corrected by Michel Marcus, Mar 15 2022

cp's OEIS Frontend

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).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A097028 Function f(x) = EulerPhi(x) + floor(x/2) is iterated; a(n) is the length of transient part and terminal cycle if the iteration was initiated at n. So a(n) is the number of distinct terms arising during iteration.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A097029 Fixed points when the function f(x) = phi(x) + floor(x/2) is iterated, i.e., solutions to f(x) = x.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Extensions

A280577 a(n) = eulerphi(n) + floor(n/2).

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A280578 Integers that are fixed points of some iteration of f(x) = phi(x) + floor(x/2), see A280577.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI