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.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
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
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
Sequence in context: A102347 A230846 A204908 * A339696 A263027 A069974
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.

License Agreements, Terms of Use, Privacy Policy. .

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