The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A340265 a(n) = n + 1 - a(phi(n)). 1
 1, 2, 2, 3, 3, 5, 3, 6, 5, 8, 4, 10, 4, 10, 10, 11, 7, 14, 6, 15, 12, 15, 9, 19, 11, 17, 14, 19, 11, 25, 7, 22, 19, 24, 17, 27, 11, 25, 21, 30, 12, 33, 11, 30, 27, 32, 16, 38, 17, 36, 30, 34, 20, 41, 26, 38, 31, 40, 20, 50, 12, 38, 37, 43, 28, 52, 16, 47, 40, 52, 20, 54, 20, 48 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,2 COMMENTS Since phi(n) < n, a(n) only depends on earlier values a(k), k < n. This makes the sequences computable using dynamic programming. The motivation for the "+ 1" is that without it the sequence becomes half-integer as a(1) would equal 1/2. 1 <= a(n) <= n. Proof: Suppose 1 <= a(k) <= k for all k < n. Then a(k + 1) = k + 1 + 1 - a(phi(k + 1)). As 1 <= a(phi(k)) <= k we have 2 <= k + 1 + 1 - k <= k + 1 + 1 - a(phi(k + 1)) = a(k + 1) <= k + 1. LINKS Robert Israel, Table of n, a(n) for n = 1..10000 FORMULA a(n) = n + Sum_{k=1..floor(log_2(n))} (-1)^k*(phi^k(n) - 1), where phi^k(n) is the k-th iterate of phi(n). - Ridouane Oudra, Oct 10 2023 MAPLE f:= proc(n) option remember; n+ 1 - procname(numtheory:-phi(n)); end proc: f(1):= 1: map(f, [\$1..100]); # Robert Israel, Jan 06 2021 MATHEMATICA Function[, If[#1 == 1, 1, # + 1 - #0[EulerPhi@#]], Listable]@Range[70] PROG (Python) from sympy import totient as phi N = 100 # a(n) = n + 1 - a(phi(n)), n > 0, a(0) = 0 a = [ 0 ] * N # a(1) = 1 + 1 - a(phi(1)) = 2 - a(1) => 2 a(1) = 2 => a(1) = 1 # a(n), n > 1 computed using dynamic programming a[1] = 1 for n in range(2, N): a[n] = n + 1 - a[phi(n)] print(a[1:]) (Python) from sympy import totient as phi def a(n): return 1 if n==1 else n + 1 - a(phi(n)) print([a(n) for n in range(1, 100)]) # Michael S. Branicky, Jan 03 2021 (PARI) first(n) = {my(res = vector(n)); res[1] = 1; for(i = 2, n, res[i] = i + 1 - res[eulerphi(i)]); res} \\ David A. Corneth, Jan 03 2021 CROSSREFS Cf. A000010, A053478. Sequence in context: A102347 A230846 A204908 * A339696 A263027 A069974 Adjacent sequences: A340262 A340263 A340264 * A340266 A340267 A340268 KEYWORD nonn,look AUTHOR Emanuel Landeholm, Jan 03 2021 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 19 13:04 EDT 2024. Contains 372692 sequences. (Running on oeis4.)