A340265 a(n) = n + 1 - a(phi(n)).

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

Offset: 1

Author

Emanuel Landeholm, Jan 03 2021

Keywords

• nonn
• look

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

Crossrefs

Cf. A000010, A053478.

Programs

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]

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

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

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