A097026 -id:A097026 - cp's OEIS frontend

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.

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

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.

Original entry on oeis.org

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

Labos Elemer, Aug 27 2004

nonn

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

			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.

Cf. A000010, A097026, A097028, A097029.

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

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

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

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

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

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