A291788 -id:A291788 - cp's OEIS frontend

A291784 a(n) = (psi(n) + phi(n))/2.

1, 2, 3, 4, 5, 7, 7, 8, 9, 11, 11, 14, 13, 15, 16, 16, 17, 21, 19, 22, 22, 23, 23, 28, 25, 27, 27, 30, 29, 40, 31, 32, 34, 35, 36, 42, 37, 39, 40, 44, 41, 54, 43, 46, 48, 47, 47, 56, 49, 55, 52, 54, 53, 63, 56, 60, 58

Offset: 1

N. J. A. Sloane, Sep 02 2017

This is (A001615 + A000010)/2. It is easy to see that this is always an integer.
If n is a power of a prime (including 1 and primes), then a(n) = n, and in any other case a(n) > n. - M. F. Hasler, Sep 09 2017
If n is in A006881, then a(n)=n+1. - Robert Israel, Feb 10 2019

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41 (page 96 of 2nd ed., pages 147ff of 3rd ed.).

Hugo Pfoertner, Table of n, a(n) for n = 1..10000
Marcin Mazur and Bogdan V. Petrenko, Generalizations of Arnold's version of Euler's theorem for matrices, Japanese Journal of Mathematics, 5:183-189, 2010.
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)

Cf. A000010, A001615, A006881, A291785, A291786, A291787, A291788.

f:= proc(n) local P, p;
  P:= numtheory:-factorset(n);
  n*(mul((p-1)/p, p=P) + mul((p+1)/p, p=P))/2
end proc:
map(f, [$1..100]); # Robert Israel, Feb 10 2019

psi[n_] := If[n == 1, 1, n*Times @@ (1 + 1/FactorInteger[n][[All, 1]])];
a[n_] := (psi[n] + EulerPhi[n])/2;
Array[a, 100] (* Jean-François Alcover, Feb 25 2019 *)

A291784(n)=(eulerphi(n)+n*sumdivmult(n,d,issquarefree(d)/d))\2 \\ M. F. Hasler, Sep 03 2017

Sum_{k=1..n} a(k) = c * n^2 + O(n*log(n)), where c = 21/(4*Pi^2) = 0.531936... . - Amiram Eldar, Dec 05 2023

A291787 Trajectory of 45 under repeated application of the map k -> A291784(k).

Original entry on oeis.org

45, 48, 56, 60, 80, 88, 92, 94, 95, 96, 112, 120, 160, 176, 184, 188, 190, 216, 252, 324, 378, 486, 567, 594, 738, 876, 1032, 1224, 1488, 1776, 2112, 2624, 2656, 2672, 2680, 2976, 3552, 4224, 5248, 5312, 5344, 5360, 5952, 7104, 8448, 10496, 10624

Offset: 0

N. J. A. Sloane, Sep 02 2017

nonn

It may be that every trajectory under iteration of the map k -> A291784(k) which increases indefinitely will eventually merge with this sequence. This is certainly true for the terms 45 through 152 of A291788. - N. J. A. Sloane, Sep 24 2017

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.

N. J. A. Sloane, Table of n, a(n) for n = 0..10000
N. J. A. Sloane, Three (No, 8) Lovely Problems from the OEIS, Experimental Mathematics Seminar, Rutgers University, Oct 05 2017, Part I, Part 2, Slides. (Mentions this sequence)
C. R. Wall, Unbounded sequences of Euler-Dedekind means, Amer. Math. Monthly, 92 (1985), 587.

Cf. A000010, A001615, A291784, A291785, A291786, A291788.

a(n) = 2*a(n-7) for n >= 35, which proves this is unbounded. [Guy, Wall]

More terms from Hugo Pfoertner, Sep 03 2017

A291785 Iterate the map A291784: k -> (psi(k)+phi(k))/2, starting with n, until a power of a prime (A000961) is reached, or -1 if that never happens.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 7, 8, 9, 11, 11, 16, 13, 16, 16, 16, 17, 23, 19, 23, 23, 23, 23, 47, 25, 27, 27, 47, 29, 47, 31, 32, 83, 83, 83, 83, 37, 47, 47, 47, 41, 83, 43, 47, -1, 47, 47, -1, 49, -1, 83, 83, 53, 83, -1, -1, 59, 59, 59, -1, 61, 83, 83, 64, 83, 83, 67, -1, -1, -1, 71, -1, 73

Offset: 1

N. J. A. Sloane, Sep 02 2017

sign

Primes and prime powers are fixed points under the map f(k) = (psi(k)+phi(k))/2. (If n = p^k, then psi(n) = p^k(1+1/p), phi(n) = p^k(1-1/p), and their average is p^k, so n is a fixed point under the map.)
Since f(n)>n if n is not a prime power, there can be no nontrivial cycles.
Wall (1985) observes that the trajectories of 45 and 50 are unbounded, so a(45) = a(50) = -1.
Also 48 and many more terms seem to have unbounded trajectories. - Hugo Pfoertner, Sep 03 2017.
Obviously any number in the trajectory of a number with unbounded trajectory (in particular that of 45, A291787) again has this property. A291788 is the union of all these. - M. F. Hasler, Sep 03 2017

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.

C. R. Wall, Unbounded sequences of Euler-Dedekind means, Amer. Math. Monthly, 92 (1985), 587.

Cf. A000010, A001615, A291784, A291786, A291787, A291788.

A291785(n,L=n)={for(i=0,L,isprimepower(n=A291784(n))&&return(n));(-1)^(n>1)} \\ The search limit L=n is only experimental but appears quite conservative w.r.t. known data, cf. A291786. The algorithm assumes that there are no cycles except for the powers of primes. - M. F. Hasler, Sep 03 2017

More terms from Hugo Pfoertner, Sep 03 2017

A291786 a(n) = number of iterations of k -> (psi(k)+phi(k))/2 (A291784) needed to reach a prime or a power of a prime or 1, or -1 if that doesn't happen.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 3, 0, 2, 1, 0, 0, 3, 0, 2, 2, 1, 0, 6, 0, 1, 0, 5, 0, 4, 0, 0, 9, 8, 7, 6, 0, 5, 4, 3, 0, 5, 0, 2, -1, 1, 0, -1, 0, -1, 6, 5, 0, 4, -1, -1, 2, 1, 0, -1, 0, 4, 3, 0, 3, 2, 0, -1, -1, -1, 0, -1, 0

Offset: 1

N. J. A. Sloane, Sep 02 2017

Primes and prime powers are fixed points under the map f(k) = (psi(k)+phi(k))/2, so in that case we take a(n)=0. (If n = p^k, then psi(n) = p^k(1+1/p), phi(n) = p^k(1-1/p), and their average is p^k, so n is a fixed point under the map.)
Since f(n)>n if n is not a prime power, there can be no nontrivial cycles.
Wall (1985) observes that the trajectories of 45 and 50 are unbounded, so a(45) = a(50) = -1. See A291787, A291788.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004. See Section B41, p. 147.

C. R. Wall, Unbounded sequences of Euler-Dedekind means, Amer. Math. Monthly, 92 (1985), 587.

Cf. A000010, A001615, A291784, A291785, A291787, A291788.

A291786(n,L=n)=n>1&&for(i=0,L,isprimepower(n)&&return(i);n=A291784(n));-(n>1) \\ The suggested search limit L=n is only empirical and might require revision. The code also currently assumes that the prime powers are the only cycles. - M. F. Hasler, Sep 03 2017

a(n) = 0 iff n is in A000961. - M. F. Hasler, Sep 03 2017

Initial terms corrected and more terms from M. F. Hasler, Sep 03 2017

cp's OEIS Frontend

A291784 a(n) = (psi(n) + phi(n))/2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A291787 Trajectory of 45 under repeated application of the map k -> A291784(k).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A291785 Iterate the map A291784: k -> (psi(k)+phi(k))/2, starting with n, until a power of a prime (A000961) is reached, or -1 if that never happens.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

A291786 a(n) = number of iterations of k -> (psi(k)+phi(k))/2 (A291784) needed to reach a prime or a power of a prime or 1, or -1 if that doesn't happen.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions