cp's OEIS Frontend

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

%I A340265 #68 Oct 29 2023 21:48:40
%S A340265 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,
%T A340265 11,25,7,22,19,24,17,27,11,25,21,30,12,33,11,30,27,32,16,38,17,36,30,
%U A340265 34,20,41,26,38,31,40,20,50,12,38,37,43,28,52,16,47,40,52,20,54,20,48
%N A340265 a(n) = n + 1 - a(phi(n)).
%C A340265 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.
%C A340265 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.
%H A340265 Robert Israel, <a href="/A340265/b340265.txt">Table of n, a(n) for n = 1..10000</a>
%F A340265 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
%p A340265 f:= proc(n) option remember; n+ 1 - procname(numtheory:-phi(n)); end proc:
%p A340265 f(1):= 1:
%p A340265 map(f, [$1..100]); # _Robert Israel_, Jan 06 2021
%t A340265 Function[, If[#1 == 1, 1, # + 1 - #0[EulerPhi@#]], Listable]@Range[70]
%o A340265 (Python)
%o A340265 from sympy import totient as phi
%o A340265 N = 100
%o A340265 # a(n) = n + 1 - a(phi(n)), n > 0, a(0) = 0
%o A340265 a = [ 0 ] * N
%o A340265 # a(1) = 1 + 1 - a(phi(1)) = 2 - a(1) => 2 a(1) = 2 => a(1) = 1
%o A340265 # a(n), n > 1 computed using dynamic programming
%o A340265 a[1] = 1
%o A340265 for n in range(2, N):
%o A340265   a[n] = n + 1 - a[phi(n)]
%o A340265 print(a[1:])
%o A340265 (Python)
%o A340265 from sympy import totient as phi
%o A340265 def a(n): return 1 if n==1 else n + 1 - a(phi(n))
%o A340265 print([a(n) for n in range(1, 100)]) # _Michael S. Branicky_, Jan 03 2021
%o A340265 (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
%Y A340265 Cf. A000010, A053478.
%K A340265 nonn,look
%O A340265 1,2
%A A340265 _Emanuel Landeholm_, Jan 03 2021