A061070 - OEIS

%I #13 Sep 10 2023 00:42:39

%S 1,1,2,2,3,3,4,4,4,4,5,5,6,6,7,7,8,8,9,9,9,9,10,10,11,11,11,11,12,12,

%T 13,13,13,13,14,14,15,15,15,15,16,16,17,17,17,17,18,18,18,18,19,19,20,

%U 20,20,20,20,20,21,21,22,22,22,22,23,23,24,24,25,25,26,26,27,27,27,27

%N Number of distinct values in the list of values of the Euler totient function {phi(j) : j=1..n}.

%H T. D. Noe, <a href="/A061070/b061070.txt">Table of n, a(n) for n=1..1000</a>

%H Terence Tao, <a href="https://arxiv.org/abs/2309.02325">Monotone non-decreasing sequences of the Euler totient function</a>, arXiv:2309.02325 [math.NT], 2023.

%F a(n) = | {phi(j) : j=1..n} |.

%e From _Michael De Vlieger_, Sep 09 2023: (Start)

%e a(1) = 1 since phi(1) = 1 is distinct from phi(k), k < 1.

%e a(2) = 1 since phi(2) = phi(1).

%e a(3) = 2 since phi(3) = 2, distinct from phi(1) = phi(2) = 1.

%e a(4) = 2 since phi(4) = phi(3) = 2.

%e a(5) = 3 since phi(5) = 4, distinct from phi(k), k < 5, etc. (End)

%t nn = 120; c[_] := False; k = 0; Reap[Do[If[! c[#], k++; c[#] = True] &[EulerPhi[i]]; Sow[k], {i, nn}]][[-1, 1]] (* _Michael De Vlieger_, Sep 09 2023 *)

%o (Python)

%o from sympy import totient

%o def A061070(n): return len({totient(i) for i in range(1,n+1)}) # _Chai Wah Wu_, Sep 08 2023

%Y Cf. A000010.

%K nonn

%O 1,3

%A _Labos Elemer_, May 28 2001