A036913 -id:A036913 - cp's OEIS frontend

A287918 Union of nonprime 1 <= t <= m for m in A036913, with gcd(t,m) = 1.

1, 25, 35, 49, 55, 65, 77, 85, 91, 95, 115, 119, 121, 125, 133, 143, 145, 155, 161, 169, 185, 187, 203, 205, 209, 215, 217, 221, 235, 247, 253, 259, 265, 287, 289, 295, 299, 301, 305, 319, 323, 325, 329, 335, 341, 343, 355, 361, 365, 371, 377, 391, 395, 403

Offset: 1

Jamie Morken and Michael De Vlieger, Jun 11 2017

nonn

List of nonprime totatives t of m for m in A036913.
Nonprime 1 is coprime to all numbers, thus a(1) = 1.
The integers {175, 245, 275} are absent, distinguishing this sequence from A038509 and A067793. These terms have factors 5^2 * 7, 5 * 7^2, 5^2 * 11. Only the terms in positions {2, 3, 4, 6, 8, 11, 18} of A036913 (i.e., {6, 12, 18, 42, 66, 126, 462}) are larger and coprime to 5. Of these only 462 is greater than these three terms, however 462 is divisible by 7 and 11. Thus {175, 245, 275} are not terms.
Squared primes q^2 for q >= 5 appear in the sequence at positions {2, 4, 13, 20, 35, 48, 71, 107, 123, 173, ...}. These are coprime to and smaller than {42, 60, 126, 210, 330, 420, ...} at indices {6, 7, 11, 13, 16, 17, 20, 25, 25, 28, 30, 30, 31, 40, 33, 35, ...} in A036913.

			From _Michael De Vlieger_, Jun 14 2017: (Start)
List of nonprime totatives 1 <= t <= m for m <= 210 in A036913:
    m: 1 <= t <= m
    2: 1;
    6: 1;
   12: 1;
   18: 1;
   30: 1;
   42: 1, 25;
   60: 1, 49;
   66: 1, 25, 35, 49, 65;
   90: 1, 49, 77;
  120: 1, 49, 77, 91, 119;
  126: 1, 25, 55, 65, 85, 95, 115, 121, 125;
  150: 1, 49, 77, 91, 119, 121, 133, 143;
  210: 1, 121, 143, 169, 187, 209;
       ...
Indices of A036913 of first and last terms m such that gcd(a(n),m)=1:
   n   a(n)   Freq.  First   Last
  -------------------------------
   1      1     oo       1     oo
   2     25      4       6     18
   3     35      1       8      8
   4     49     14       7     40
   5     55      1      11     11
   6     65      3       8     18
   7     77      8       9     24
   8     85      2      11     18
   9     91     11      10     40
  10     95      2      11     18
  11    115      2      11     18
  12    119      9      10     27
  13    121     75      11    308
  14    125      2      11     18
  15    133     10      12     40
  16    143     36      12    107
  17    145      1      18     18
  18    155      1      18     18
  19    161      8      14     40
  20    169     96      13    248
  ...
Positions of squared primes q^2 in a(n):
        q^2           q
    n   a(n)  sqrt(a(n))     k    m = A036913(k)
  ----------------------------------------------
    2     25          5      6       42
    4     49          7      7       60
   13    121         11     11      126
   20    169         13     13      210
   35    289         17     16      330
   48    361         19     17      420
   71    529         23     20      630
  107    841         29     25     1050
  123    961         31     25     1050
  173   1369         37     28     1470
  210   1681         41     30     1890
  234   1849         43     30     1890
  283   2209         47     31     2310
  303   2401         49     40     5610
  359   2809         53     33     2940
  456   3481         59     35     3570
  486   3721         61     36     3990
  598   4489         67     37     4620
  676   5041         71     39     5460
  721   5329         73     39     5460
  ...
(End)

Cf. A001248, A036913, A038509, A067793, A285784, A287917.

With[{nn = 403, s = Union@FoldList[Max, Values[#][[All, -1]]] &@ KeySort@ PositionIndex@ EulerPhi@ Range[Product[Prime@ i, {i, 8}]]}, Union@ Flatten@ Map[Function[n, Select[Range@ Min[n, nn], And[CoprimeQ[#, n], ! PrimeQ@ #] &]], s]] (* Michael De Vlieger, Jun 14 2017 *)

A032447 Inverse function of phi( ).

Original entry on oeis.org

1, 2, 3, 4, 6, 5, 8, 10, 12, 7, 9, 14, 18, 15, 16, 20, 24, 30, 11, 22, 13, 21, 26, 28, 36, 42, 17, 32, 34, 40, 48, 60, 19, 27, 38, 54, 25, 33, 44, 50, 66, 23, 46, 35, 39, 45, 52, 56, 70, 72, 78, 84, 90, 29, 58, 31, 62, 51, 64, 68, 80, 96, 102, 120, 37, 57, 63, 74, 76, 108, 114, 126

Offset: 1

Ursula Gagelmann (gagelmann(AT)altavista.net)

Arrange integers in order of increasing phi value; the phi values themselves form A007614.
Inverse of sequence A064275 considered as a permutation of the positive integers. - Howard A. Landman, Sep 25 2001
In the array shown in the example section row no. n gives exactly the N values for which the cyclotomic polynomials cyclotomic(N,x) have degree A002202(n). - Wolfdieter Lang, Feb 19 2012.

			phi(1)=phi(2)=1, phi(3)=phi(4)=phi(6)=2, phi(5)=phi(8)=...=4, ...
From _Wolfdieter Lang_, Feb 19 2012: (Start)
Read as array a(n,m) with row length l(n):=A058277(v(n)) with v(n):= A002202(n), n>=1. a(n,m) = m-th element of the set {m from positive integers: phi(m)=v(n)} when read as an increasingly ordered list.
  l(n): 2, 3, 4, 4, 5, 2, 6, 6, 4, 5, ...
   n, v(n)\m 1  2  3  4  5  6  7  8  9  10 11  12  13  14
   1,  1:    1  2
   2,  2:    3  4  6
   3,  4:    5  8 10 12
   4,  6:    7  9 14 18
   5,  8:   15 16 20 24 30
   6, 10:   11 22
   7, 12:   13 21 26 28 36 42
   8, 16:   17 32 34 40 48 60
   9, 18:   19 27 38 54
  10, 20:   25 33 44 50 66
  ...
Row no. n=4: The cyclotomic polynomials cyclotomic(N,x) with values N = 7,9,14, and 18 have degree 6, and only these.
(End)

Sivaramakrishnan, The many facets of Euler's Totient, I. Nieuw Arch. Wisk. 4 (1986), 175-190.

T. D. Noe, Table of n, a(n) for n = 1..10000 (Corrected by _Dana Jacobsen_, Mar 04 2019)
D. Bressoud, CNT.m Computational Number Theory Mathematica package.
H. Gupta, Euler’s totient function and its inverse, Indian J. pure appl. Math., 12(1): 22-29(1981).
Index entries for sequences that are permutations of the natural numbers

Cf. A000010, A007614.

Cf. A002110, A064275.

import Data.List.Ordered (insertBag)
a032447 n = a032447_list !! (n-1)
a032447_list = f [1..] a002110_list [] where
   f xs'@(x:xs) ps'@(p:ps) us
     | x < p = f xs ps' $ insertBag (a000010' x, x) us
     | otherwise = map snd vs ++ f xs' ps ws
     where (vs, ws) = span ((<= a000010' x) . fst) us
-- Reinhard Zumkeller, Nov 22 2015

Needs["CNT`"]; Flatten[Table[PhiInverse[n], {n, 40}]] (* T. D. Noe, Oct 15 2012 *)
Take[Values@ PositionIndex@ Array[EulerPhi, 10^3], 15] // Flatten (* Michael De Vlieger, Dec 29 2017 *)
SortBy[Table[{n,EulerPhi[n]},{n,150}],Last][[All,1]] (* Harvey P. Dale, Oct 11 2019 *)

M = 9660; /* choose a term of A036913 */
v = vector(M, n, [eulerphi(n),n] );
v = vecsort(v, (x, y)-> if( x[1]-y[1]!=0, sign(x[1]-y[1]), sign(x[2]-y[2]) ) );
P=eulerphi(M);
v = select( x->(x[1]<=P), v );
/* A007614 = vector(#v,n, v[n][1] ) */
A032447 = vector(#v,n, v[n][2] )
/* for (n=1,#v, print(n," ", A032447[n]) ); */ /* b-file */
/* Joerg Arndt, Oct 06 2012 */

use ntheory ":all"; my($n,$k,$i,@v)=(10000,1,0); push @v,inverse_totient($k++) while @v<$n; $#v=$n-1; say ++$i," $" for @v; # _Dana Jacobsen, Mar 04 2019

Example corrected, more terms and program from Olivier Gérard, Feb 1999

A006511 Largest inverse of totient function (A000010): a(n) is the largest x such that phi(x) = m, where m = A002202(n) is the n-th number in the range of phi.

Original entry on oeis.org

2, 6, 12, 18, 30, 22, 42, 60, 54, 66, 46, 90, 58, 62, 120, 126, 150, 98, 138, 94, 210, 106, 162, 174, 118, 198, 240, 134, 142, 270, 158, 330, 166, 294, 276, 282, 420, 250, 206, 318, 214, 378, 242, 348, 354, 462, 254, 510, 262, 414, 274, 278, 426, 630, 298, 302

Offset: 1

N. J. A. Sloane

nonn

Always even, as phi(2n) = phi(n) when n is odd. - Alain Jacques (thegentleway(AT)bigpond.com), Jun 15 2006

J. W. L. Glaisher, Number-Divisor Tables. British Assoc. Math. Tables, Vol. 8, Camb. Univ. Press, 1940, p. 64.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Richard K. Guy, Letter to N. J. A. Sloane, Jun 1991.

Cf. A000010, A002202, A002181, A057826.

For records see A036913, A132154, A036912.

phiinv[n_, pl_] := Module[{i, p, e, pe, val}, If[pl=={}, Return[If[n==1, {1}, {}]]]; val={}; p=Last[pl]; For[e=0; pe=1, e==0||Mod[n, (p-1)pe/p]==0, e++; pe*=p, val=Join[val, pe*phiinv[If[e==0, n, n*p/pe/(p-1)], Drop[pl, -1]]]]; Sort[val]]; phiinv[n_] := phiinv[n, Select[1+Divisors[n], PrimeQ]]; Last/@Select[phiinv/@Range[1, 200], #!={}&] (* phiinv[n, pl] = list of x with phi(x)=n and all prime divisors of x in list pl. phiinv[n] = list of x with phi(x)=n *)

g(n) = if(n%2, 2*(n==1), forstep(k = floor(exp(Euler)*n*log(log(n^2))+2.5*n/log(log(n^2))), n, -1, if(eulerphi(k)==n, return(k)); if(k==n, return(0)))); \\ A057635
lista(nn) = for(m = 1, nn, if(istotient(m), print1(g(m), ", "))); \\ Jinyuan Wang, Aug 29 2019

lista(nmax) = my(s); for(n = 1, nmax, s = invphiMax(n); if(s > 0, print1(s, ", "))); \\ Amiram Eldar, Nov 14 2024, using Max Alekseyev's invphi.gp

use ntheory ":all"; my $k=1; for my $i (1..100) { my @v; do{@v=inverse_totient($k++)} until @v; print "$i $v[-1]\n"; } # Dana Jacobsen, Mar 04 2019

a(n) = A057635(A002202(n)). - T. D. Noe

A036912 Indices of the left-to-right maxima in A057635.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 20, 24, 32, 36, 40, 48, 64, 72, 80, 96, 120, 128, 144, 160, 176, 192, 224, 240, 288, 320, 336, 384, 432, 480, 576, 672, 720, 768, 864, 960, 1056, 1152, 1280, 1296, 1344, 1440, 1536, 1680, 1728, 1920, 2112, 2208, 2304, 2400, 2592, 2688

Offset: 1

David W. Wilson

nonn

A number m belongs to this sequence iff A057635(k) < A057635(m) for all k

Indices of records in A057635(n), the maximal m with phi(m)=n.

The Alekseyev link in A131883 establishes the following explicit relationship between A131883, A036912 and A057635. Namely, for t belonging to A036912, we have t=A131883(A057635(t)-1). In other words, A036912(n) = A131883(A057635(A036912(n))-1) for all n.

T. D. Noe, Table of n, a(n) for n = 1..5000

Cf. A057635, A000010, A006511, A036913, A132154, A131883.

Block[{nn = 10^6, s, t, u}, s = PositionIndex@ Array[EulerPhi, nn]; t = ConstantArray[0, nn]; u = Take[ReplacePart[t, Map[# -> Last@ Lookup[s, #] &, Keys@ s]], 10^(Log10[nn] - 2)]; Map[FirstPosition[u, #][[1]] &, Union@ FoldList[Max, u]]] (* Michael De Vlieger, Oct 24 2017 *)

a(n) = A000010(A036913(n)). - Max Alekseyev, Nov 07 2007

More precise definition from Max Alekseyev, Nov 07 2007

A066412 Number of elements in the set phi_inverse(phi(n)).

Original entry on oeis.org

2, 2, 3, 3, 4, 3, 4, 4, 4, 4, 2, 4, 6, 4, 5, 5, 6, 4, 4, 5, 6, 2, 2, 5, 5, 6, 4, 6, 2, 5, 2, 6, 5, 6, 10, 6, 8, 4, 10, 6, 9, 6, 4, 5, 10, 2, 2, 6, 4, 5, 7, 10, 2, 4, 9, 10, 8, 2, 2, 6, 9, 2, 8, 7, 11, 5, 2, 7, 3, 10, 2, 10, 17, 8, 9, 8, 9, 10, 2, 7, 2, 9, 2, 10, 8, 4, 3, 9, 6, 10, 17, 3, 9, 2, 17, 7

Offset: 1

Vladeta Jovovic, Dec 25 2001

nonn

			invphi(6) = [7, 9, 14, 18], thus a(7) = a(9) = a(14) = a(18) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..10000
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Wikipedia, Euler's totient function (see the last paragraph in section "Some values of the function")

Cf. A000010, A001055, A014197, A032447, A036913, A057826, A071181.

Cf. A070305 (positions where coincides with A000005).

Maple
```
nops(invphi(phi(n)));
```

With[{nn = 120}, Function[s, Take[#, nn] &@ Values@ KeySort@ Flatten@ Map[Function[{k, m}, Map[# -> m &, k]] @@ {#, Length@ #} &@ Lookup[s, #] &, Keys@ s]]@ KeySort@ PositionIndex@ Array[EulerPhi, nn^2 + 10]] (* Michael De Vlieger, Jul 18 2017 *)

for(n=1,150,print1(sum(i=1,10*n,if(n-eulerphi(n)-i+eulerphi(i),0,1)),",")) \\ By the original author(s). Note: the upper limit 10*n for the search range is quite ad hoc, and is guaranteed to miss some cases when n is large enough. Cf. Wikipedia-article. - Antti Karttunen, Jul 19 2017

\\ Here is an implementation not using arbitrary limits:
A014197(n, m=1) = { n==1 && return(1+(m<2)); my(p, q); sumdiv(n, d, if( d>=m && isprime(d+1), sum( i=0, valuation(q=n\d, p=d+1), A014197(q\p^i, p))))} \\ M. F. Hasler, Oct 05 2009
A066412(n) = A014197(eulerphi(n)); \\ Antti Karttunen, Jul 19 2017

a(n) = invphiNum(eulerphi(n)); \\ Amiram Eldar, Nov 14 2024, using Max Alekseyev's invphi.gp

;; A naive implementation requiring precomputed A057826:
(define (A066412 n) (if (<= n 2) 2 (let ((ph (A000010 n))) (let loop ((k (A057826 (/ ph 2))) (s 0)) (if (zero? k) s (loop (- k 1) (+ s (if (= ph (A000010 k)) 1 0)))))))) ;; Antti Karttunen, Jul 18 2017

a(n) = Card( k>0 : cototient(k)=cototient(n) ) where cototient(x) = x - phi(x). - Benoit Cloitre, May 09 2002
From Antti Karttunen, Jul 18 2017: (Start)
a(n) = A014197(A000010(n)).
For all n, a(n) <= A071181(n).
(End)

A132154 Where records occur in A006511.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 10, 12, 15, 16, 17, 21, 27, 30, 32, 37, 46, 48, 54, 58, 64, 69, 80, 85, 98, 107, 112, 127, 138, 153, 179, 205, 219, 230, 257, 281, 306, 330, 361, 367, 379, 403, 427, 466, 477, 524, 571, 595, 619, 645, 689, 713, 737, 761, 806, 828, 875, 894, 963, 986, 1031

Offset: 1

N. J. A. Sloane, Nov 05 2007

nonn

Donovan Johnson, Table of n, a(n) for n = 1..500

Cf. A000010, A006511, A036913, A036912.

A289276 Numbers k such that phi(k) (the totient function A000010) is a power of the number of divisors of k (A000005).

Original entry on oeis.org

1, 2, 3, 5, 8, 10, 17, 18, 24, 30, 34, 63, 76, 85, 128, 136, 170, 257, 315, 333, 364, 380, 436, 444, 514, 640, 680, 972, 1285, 1542, 1820, 1824, 1836, 1875, 2142, 2220, 2907, 3285, 3488, 3796, 4369, 4788, 4860

Offset: 1

Franklin T. Adams-Watters, Jun 30 2017

A019434 is a subsequence. - David A. Corneth, Jun 30 2017

Is the frequency of e such that A000005(a(n))^e = A000010(a(n)) finite? - David A. Corneth, Jul 01 2017

Charles R Greathouse IV, Table of n, a(n) for n = 1..5319 (first 526 terms from Antti Karttunen)

Cf. A000005, A000010, A019434, A020488, A032447, A036913, A051281, A068559, A068560, A114063, A286627.

Join[{1},Select[Range[2,5000],IntegerQ[Log[DivisorSigma[0,#],EulerPhi[#]]]&]] (* Harvey P. Dale, Aug 06 2017 *)

ispowerof(n, k)= if(k==1, return(n==1)); while(n>=k, if(n%k!=0, return(0)); n\=k); n==1
isa(n) = ispowerof(eulerphi(n),numdiv(n)) \\ Quick program, fast enough for early values.

is(n) = if(n==1, return(1)); my(f = factor(n); phi = eulerphi(f), ndiv = numdiv(f), e = logint(phi, ndiv)); ndiv^e == phi \\ David A. Corneth, Jun 30 2017, changed per suggestion of Charles R Greathouse IV

isA289276(n)= if(n==1, return(1)); my(phi = eulerphi(n), ndiv = numdiv(n), v = valuation(phi, ndiv)); ndiv^v == phi; \\ (A variant of above program). - Antti Karttunen, Jun 30 2017

list(lim)=my(v=List([1])); forfactored(n=2,lim\1, my(phi = eulerphi(n), ndiv = numdiv(n)); if(ndiv^valuation(phi,ndiv) == phi, listput(v,n[1]))); Vec(v) \\ Charles R Greathouse IV, Jul 01 2017

A362230 Unitary sparsely totient numbers: numbers k such that m > k implies uphi(m) > uphi(k), where uphi is the unitary totient function (A047994).

Original entry on oeis.org

2, 6, 10, 14, 30, 42, 66, 78, 102, 114, 138, 210, 222, 330, 390, 462, 510, 570, 690, 714, 798, 870, 930, 966, 1110, 1230, 1290, 1302, 1410, 1470, 1590, 1770, 2310, 2730, 3570, 3990, 4290, 4830, 5610, 6090, 6510, 6630, 7770, 8610, 9030, 9870, 10230, 11130, 11310

Offset: 1

Amiram Eldar, Apr 12 2023

nonn

Amiram Eldar, Table of n, a(n) for n = 1..300

The unitary version of A036913.
Record values of A362229.
Cf. A047994, A361966, A362231.

s[n_] := If[(inv = invUPhi[n]) == {}, 0, Max[inv]]; seq[kmax_] := Module[{v = {}, s1, sm = 0}, Do[s1 = s[k]; If[s1 > sm, sm = s1; AppendTo[v, s1]], {k, 1, kmax}]; v]; seq[3000] (* using the function invUPhi from A361966 *)

A362667 Infinitary sparsely totient numbers: numbers k such that m > k implies iphi(m) > iphi(k), where iphi is the infinitary totient function A091732.

Original entry on oeis.org

2, 6, 8, 10, 24, 30, 42, 54, 56, 66, 120, 168, 216, 264, 270, 312, 330, 384, 408, 456, 480, 510, 552, 840, 1080, 1320, 1560, 1920, 2040, 2280, 2376, 2760, 3000, 3192, 3480, 3720, 3864, 4440, 4920, 5160, 5208, 5640, 7560, 9240, 10920, 11880, 13440, 14280, 15960

Offset: 1

Amiram Eldar, Apr 29 2023

nonn

Amiram Eldar, Table of n, a(n) for n = 1..300

The infinitary version of A036913.
Record values of A362666.
Cf. A091732, A362484, A362668.

s[n_] := If[(inv = invIPhi[n]) == {}, 0, Max[inv]]; seq[kmax_] := Module[{v = {}, s1, sm = 0}, Do[s1 = s[k]; If[s1 > sm, sm = s1; AppendTo[v, s1]], {k, 1, kmax}]; v]; seq[3000] (* using the function invIPhi from A362484 *)

Showing 1-10 of 14 results. Next

cp's OEIS Frontend

A355475 Numbers that are sparsely totient (A036913) and of least prime signature (A025487).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A287918 Union of nonprime 1 <= t <= m for m in A036913, with gcd(t,m) = 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A032447 Inverse function of phi( ).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Perl

Extensions

A006511 Largest inverse of totient function (A000010): a(n) is the largest x such that phi(x) = m, where m = A002202(n) is the n-th number in the range of phi.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Perl

Formula

A036912 Indices of the left-to-right maxima in A057635.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A066412 Number of elements in the set phi_inverse(phi(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Scheme

Formula

A132154 Where records occur in A006511.

Views

Author

Keywords

Links

Crossrefs

A289276 Numbers k such that phi(k) (the totient function A000010) is a power of the number of divisors of k (A000005).