|
%I #13 May 12 2017 18:22:16
%S 1,1,2,2,3,2,4,3,4,3,5,3,6,4,7,7,8,4,9,7,6,5,10,7,11,6,9,6,12,7,13,8,
%T 11,8,14,6,15,9,14,8,16,6,17,11,14,10,18,8,17,11,19,14,20,9,16,14,15,
%U 12,21,8,22,13,15,19,23,11,24,19,25,14,26,14,27,15,16,15,22,14,28,19,29,16,30,14,31,17,32,16,33,14,27,25,22,18,27,19,34,17,22
%N Restricted growth sequence computed for Euler totient function phi, A000010.
%H Antti Karttunen, <a href="/A286610/b286610.txt">Table of n, a(n) for n = 1..10000</a>
%e Construction: we start with a(1)=1 for phi(1)=1 (where phi = A000010), and then after, for all n > 1, whenever the value of phi(n) has not been encountered before, we set a(n) to the least natural number k not already in sequence among a(1) .. a(n-1), otherwise [whenever phi(n) = phi(m), for some m < n], we set a(n) = a(m), i.e., to the same value that was assigned to a(m).
%e For n=2, phi(2) = 1, which value was already encountered as phi(1), thus we set also a(2) = 1.
%e For n=3, phi(3) = 2, which has not been encountered before, thus we allot for a(3) the least so far unused number, which is 2, thus a(3) = 2.
%e For n=4, phi(4) = 2, which was already encountered as at n=3 for the first time, thus we set a(4) = a(3) = 2.
%e For n=5, phi(5) = 4, which has not been encountered before, thus we allot for a(5) the least so far unused number, which is now 3, thus a(5) = 3.
%t With[{nn = 99}, Function[s, Table[Position[Keys@ s, k_ /; MemberQ[k, n]][[1, 1]], {n, nn}]]@ Map[#1 -> #2 & @@ # &, Transpose@ {Values@ #, Keys@ #}] &@ PositionIndex@ Array[EulerPhi, nn]] (* _Michael De Vlieger_, May 12 2017, Version 10 *)
%o (PARI)
%o rgs_transform(invec) = { my(occurrences = Map(), outvec = vector(length(invec)), u=1); for(i=1, length(invec), if(mapisdefined(occurrences,invec[i]), my(pp = mapget(occurrences, invec[i])); outvec[i] = outvec[pp] , mapput(occurrences,invec[i],i); outvec[i] = u; u++ )); outvec; };
%o write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
%o A000010(n) = eulerphi(n);
%o write_to_bfile(1,rgs_transform(vector(10000,n,A000010(n))),"b286610.txt");
%Y Cf. A000010, A210719 (positions of records, and also the first occurrence of each n).
%Y Cf. also A101296, A286603, A286605, A286619, A286621, A286622, A286626, A286378 for similarly constructed sequences.
%K nonn
%O 1,3
%A _Antti Karttunen_, May 11 2017
|
