

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 halfinteger 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 kth 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:


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



KEYWORD



AUTHOR



STATUS

approved



