A210719 -id:A210719 - cp's OEIS frontend

A081373 Number of values of k, 1 <= k <= n, with phi(k) = phi(n), where phi is Euler totient function, A000010.

1, 2, 1, 2, 1, 3, 1, 2, 2, 3, 1, 4, 1, 3, 1, 2, 1, 4, 1, 3, 2, 2, 1, 4, 1, 3, 2, 4, 1, 5, 1, 2, 2, 3, 1, 5, 1, 3, 2, 4, 1, 6, 1, 3, 3, 2, 1, 5, 2, 4, 1, 4, 1, 4, 2, 5, 2, 2, 1, 6, 1, 2, 3, 2, 1, 5, 1, 3, 1, 6, 1, 7, 1, 4, 3, 5, 2, 8, 1, 4, 1, 4, 1, 9, 1, 3, 1, 5, 1, 10, 2, 2, 3, 2, 3, 5, 1, 4, 4, 6

Offset: 1

Labos Elemer, Mar 24 2003

nonn

Ordinal transform of Euler totient function phi, A000010. - Antti Karttunen, Aug 26 2024

			For n = 16: phi(k) = {1,1,2,2,4,2,6,4,6,4,10,4,12,6,8,8} for k = 1,...,n; 2 numbers exist with phi(k) = phi(n) = 8: {15,16}, so a(16) = 2.
If n = p is an odd prime number, then a(p) = 1 with phi(k) = p-1.

Paul Tek, Table of n, a(n) for n = 1..100000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A081375 (positions of records), A210719 (of 1's).

Cf. also A067004, A303756, A303757, A303777 (ordinal transform of this sequence).

f[x_] := Count[Table[EulerPhi[j]-EulerPhi[x], {j, 1, x}], 0] Table[f[w], {w, 1, 100}]

a(n)=my(t=eulerphi(n), s); sum(k=1, n, eulerphi(k)==t) \\ Charles R Greathouse IV, Feb 21 2013, corrected by Antti Karttunen, Aug 26 2024

a(n) = #select(x -> x <= n, invphi(eulerphi(n))); \\ Amiram Eldar, Nov 08 2024, using Max Alekseyev's invphi.gp

A286610 Restricted growth sequence computed for Euler totient function phi, A000010.

Original entry on oeis.org

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, 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, 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

Offset: 1

Antti Karttunen, May 11 2017

nonn

			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).
For n=2, phi(2) = 1, which value was already encountered as phi(1), thus we set also a(2) = 1.
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.
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.
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.

Antti Karttunen, Table of n, a(n) for n = 1..10000

Cf. A000010, A210719 (positions of records, and also the first occurrence of each n).

Cf. also A101296, A286603, A286605, A286619, A286621, A286622, A286626, A286378 for similarly constructed sequences.

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

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; };
write_to_bfile(start_offset,vec,bfilename) = { for(n=1, length(vec), write(bfilename, (n+start_offset)-1, " ", vec[n])); }
A000010(n) = eulerphi(n);
write_to_bfile(1,rgs_transform(vector(10000,n,A000010(n))),"b286610.txt");

A303757 a(1) = 1 and for n > 1, a(n) = number of values of k, 2 <= k <= n, with A000010(k) = A000010(n), where A000010 is Euler totient function phi.

Original entry on oeis.org

1, 1, 1, 2, 1, 3, 1, 2, 2, 3, 1, 4, 1, 3, 1, 2, 1, 4, 1, 3, 2, 2, 1, 4, 1, 3, 2, 4, 1, 5, 1, 2, 2, 3, 1, 5, 1, 3, 2, 4, 1, 6, 1, 3, 3, 2, 1, 5, 2, 4, 1, 4, 1, 4, 2, 5, 2, 2, 1, 6, 1, 2, 3, 2, 1, 5, 1, 3, 1, 6, 1, 7, 1, 4, 3, 5, 2, 8, 1, 4, 1, 4, 1, 9, 1, 3, 1, 5, 1, 10, 2, 2, 3, 2, 3, 5, 1, 4, 4, 6, 1, 6, 1, 2, 3

Offset: 1

Antti Karttunen, Apr 30 2018

nonn

Ordinal transform of f, where f(1) = 0 and f(n) = A000010(n) for n > 1.
After a(1)=1 and a(4)=2, the positions of the rest of records is given by A081375(n) = 6, 12, 30, 42, 72, 78, 84, 90, 190, ..., for n >= 3.
Apart from a(2) = 1, the other positions of 1's is given by A210719.

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A081373, A081375, A210719, A303754, A303758, A303777.

With[{s = EulerPhi@ Range@ 105}, MapAt[# + 1 &, Table[Count[s[[2 ;; n]], ?(# == s[[n]] &)], {n, Length@ s}], 1]] (* _Michael De Vlieger, Nov 23 2018 *)

up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
Aux303757(n) = if(1==n,0,eulerphi(n));
v303757 = ordinal_transform(vector(up_to,n,Aux303757(n)));
A303757(n) = v303757[n];

Except for a(2) = 1, a(n) = A081373(n).

A090127 Distinct values of phi(n) in order of appearance as n increases.

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 8, 16, 18, 22, 20, 28, 30, 24, 36, 40, 42, 46, 32, 52, 58, 60, 48, 66, 44, 70, 72, 78, 54, 82, 64, 56, 88, 96, 100, 102, 106, 108, 112, 110, 80, 126, 84, 130, 136, 138, 92, 120, 148, 150, 156, 104, 132, 162, 166, 172, 116, 178, 180, 144, 160, 190, 192

Offset: 1

Labos Elemer, Jan 16 2004

nonn

A permutation of A002202. - Amiram Eldar, Nov 14 2024

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Cf. A000010, A002202, A210719.

a090127 n = a090127_list !! (n-1)
a090127_list = f a000010_list [] where
  f (x:xs) phis | x `elem` phis = f xs phis
                | otherwise     = x : f xs (x : phis)
-- Reinhard Zumkeller, Dec 18 2012

t=Table[EulerPhi[w], {w, 1, 100}]; s=Sort[t];u=Union[t]; Table[Count[s, Part[u, j]], {j, 1, Length[u]}]; g=Table[Min[Flatten[Position[t, Part[u, j]]]], {j, 1, Length[u]}]; uu=Union[g]; Table[Part[t, Part[uu, j]], {j, 1, Length[g]}]
DeleteDuplicates[EulerPhi[Range[200]]] (* Harvey P. Dale, Jan 20 2013 *)

a(n) = A000010(A210719(n)). - Reinhard Zumkeller, Dec 18 2012

A303777 Ordinal transform of A081373; ordinal transform of {the ordinal transform of A000010}.

Original entry on oeis.org

1, 1, 2, 2, 3, 1, 4, 3, 4, 2, 5, 1, 6, 3, 7, 5, 8, 2, 9, 4, 6, 7, 10, 3, 11, 5, 8, 4, 12, 1, 13, 9, 10, 6, 14, 2, 15, 7, 11, 5, 16, 1, 17, 8, 9, 12, 18, 3, 13, 6, 19, 7, 20, 8, 14, 4, 15, 16, 21, 2, 22, 17, 10, 18, 23, 5, 24, 11, 25, 3, 26, 1, 27, 9, 12, 6, 19, 1, 28, 10, 29, 11, 30, 1, 31, 13, 32, 7, 33, 1, 20, 21, 14, 22, 15, 8

Offset: 1

Antti Karttunen, Apr 30 2018

nonn

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A000010, A081373, A081375 (positions of ones), A210719 (positions of records), A286610.

b:= proc() 0 end: g:= proc() 0 end:
h:= proc(n) option remember; local t;
      t:= numtheory[phi](n); b(t):= b(t)+1
    end:
a:= proc(n) option remember; local t;
      t:= h(n); g(t):= g(t)+1
    end:
seq(a(n), n=1..120);  # Alois P. Heinz, Apr 30 2018

b[] = 0; g[] = 0;
h[n_] := h[n] = With[{t = EulerPhi[n]}, b[t] = b[t]+1];
a[n_] := a[n] = With[{t = h[n]}, g[t] = g[t]+1];
Array[a, 120] (* Jean-François Alcover, Dec 19 2021, after Alois P. Heinz *)

up_to = 65537;
ordinal_transform(invec) = { my(om = Map(), outvec = vector(length(invec)), pt); for(i=1, length(invec), if(mapisdefined(om,invec[i]), pt = mapget(om, invec[i]), pt = 0); outvec[i] = (1+pt); mapput(om,invec[i],(1+pt))); outvec; };
v081373 = ordinal_transform(vector(up_to,n,eulerphi(n)));
A081373(n) = v081373[n];
v303777 = ordinal_transform(vector(up_to,n,A081373(n)));
A303777(n) = v303777[n];

A074987 a(n) is the least m not equal to n such that phi(m) = phi(n).

Original entry on oeis.org

2, 1, 4, 3, 8, 3, 9, 5, 7, 5, 22, 5, 21, 7, 16, 15, 32, 7, 27, 15, 13, 11, 46, 15, 33, 13, 19, 13, 58, 15, 62, 17, 25, 17, 39, 13, 57, 19, 35, 17, 55, 13, 49, 25, 35, 23, 94, 17, 43, 25, 64, 35, 106, 19, 41, 35, 37, 29, 118, 17, 77, 31, 37, 51, 104, 25, 134, 51, 92, 35, 142

Offset: 1

Joseph L. Pe, Oct 02 2002

In 1922, Carmichael asked if for any given natural number n there exists a natural number m different from n such that phi(m) = phi(n). A. Schlafly and S. Wagon showed in 1994 that if there is an n such that phi(m) != phi(n) for all m distinct from n, then n must be greater than 10^(10^7). [Improved to 10^(10^10) by Kevin Ford. - Pontus von Brömssen, May 15 2020]
I conjecture that a(n) <= 2n. I have checked this for all n <= 10^4. (It is not possible to do better than the 2n upper bound since a(11) = 2*11.)
For odd n the conjecture is true because phi(n)=phi(2n). - T. D. Noe, Oct 18 2006
From Robert Israel, Aug 12 2016: (Start)
If a(n) > n then a(a(n)) = n.
If n is in A138537 then a(n) = 2*n. (End)
From David A. Corneth, May 12 2018: (Start)
A210719 has values n such that a(n) > n, so a(A210719(n)) = n.
Its complement, A296214, has values n such that a(n) < n. (End)

			phi(5) = 4 and 8 is the least natural number k different from 5 such phi(k) = 4. Hence phi(5) = 8.

J. Tattersall, "Elementary Number Theory in Nine Chapters", Cambridge University Press, 2001, pp. 162-163.

T. D. Noe, Table of n, a(n) for n = 1..10000
K. Ford, The distribution of totients, arXiv:1104.3264 [math.NT], 2011.
A. Schlafly and S. Wagon, Carmichael's conjecture on the Euler function is valid below 10^{10,000,000}, Mathematics of Computation, 63 No. 207(1994), 415-419.
Wikipedia, Carmichael's_totient_function_conjecture

Cf. A138537, A210719, A296214.

N:= 1000: # to get a(n) for n <= N
todo:= N;
for n from 1 while todo > 0 do
  v:= numtheory:-phi(n);
  if assigned(R[v]) then
    if n <= N then
      A[n]:= R[v]; todo:= todo-1;
    fi;
    if R[v] <= N and not assigned(A[R[v]])  then
      A[R[v]]:= n; todo:= todo-1;
    fi;
  else
    R[v]:= n
  fi
od:
seq(A[n],n=1..N); # Robert Israel, Aug 12 2016

l = {}; Do[ e = EulerPhi[n]; i = 1; While[e != EulerPhi[i] || n == i, i++ ]; l = Append[l, i], {n, 1, 100}]; l
(* Second program: *)
Module[{nn=300,lst},lst=Table[{n,EulerPhi[n]},{n,nn}];Take[Table[ SelectFirst[ lst,#[[2]] == lst[[k,2]] && #[[1]]!=lst[[k,1]]&],{k,nn}],100]][[All,1]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, Oct 23 2020 *)

a(n) = my(t=eulerphi(n), m=1); while ((eulerphi(m) != t) || (m==n), m++); m; \\ Michel Marcus, May 15 2020

from sympy import totient
def A074987(n):
  m=1
  while totient(m)!=totient(n) or m==n:
    m+=1
  return m # Pontus von Brömssen, May 15 2020

cp's OEIS Frontend

A081373 Number of values of k, 1 <= k <= n, with phi(k) = phi(n), where phi is Euler totient function, A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A286610 Restricted growth sequence computed for Euler totient function phi, A000010.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A303757 a(1) = 1 and for n > 1, a(n) = number of values of k, 2 <= k <= n, with A000010(k) = A000010(n), where A000010 is Euler totient function phi.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A090127 Distinct values of phi(n) in order of appearance as n increases.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A303777 Ordinal transform of A081373; ordinal transform of {the ordinal transform of A000010}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A074987 a(n) is the least m not equal to n such that phi(m) = phi(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python