A378638 -id:A378638 - cp's OEIS frontend

A319048 a(n) is the greatest k such that A000010(k) divides n where A000010 is the Euler totient function.

2, 6, 2, 12, 2, 18, 2, 30, 2, 22, 2, 42, 2, 6, 2, 60, 2, 54, 2, 66, 2, 46, 2, 90, 2, 6, 2, 58, 2, 62, 2, 120, 2, 6, 2, 126, 2, 6, 2, 150, 2, 98, 2, 138, 2, 94, 2, 210, 2, 22, 2, 106, 2, 162, 2, 174, 2, 118, 2, 198, 2, 6, 2, 240, 2, 134, 2, 12, 2, 142, 2, 270, 2, 6, 2, 12, 2, 158, 2, 330

Offset: 1

Michel Marcus, Sep 09 2018

nonn

Sándor calls this function the totient maximum function and remarks that this function is well-defined, since a(n) can be at least 2, and cannot be greater than n^2 (when n > 6).

Antti Karttunen, Table of n, a(n) for n = 1..16384
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, Pages 1—8.

Cf. A000010 (Euler totient), A061026 (the totient minimum function).
Cf. A319068 (the analog for the sum of divisors).
Cf. A070633, also A057635, A057826, A069932, A071181.
Right border of A378638.

a[n_] := Module[{kmax = If[n <= 6, 10 n, n^2]}, For[k = kmax, True, k--, If[Divisible[n, EulerPhi[k]], Return[k]]]];
Array[a, 80] (* Jean-François Alcover, Sep 17 2018, from PARI *)

a(n) = {my(kmax = if (n<=6, 10*n, n^2)); forstep (k=kmax, 1, -1, if ((n % eulerphi(k)) == 0, return (k)););}

\\ (The first two functions could probably be combined in a smarter way):
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))))} \\ From A014197 by M. F. Hasler
A057635(n) = if(1==n,2,if((n%2),0,my(k=A014197(n),i=n); if(!k, 0, while(k, i++; if(eulerphi(i)==n, k--)); (i))));
A319048(n) = { my(m=0); fordiv(n,d, m = max(m,A057635(d))); (m); }; \\ Antti Karttunen, Sep 09 2018

a(n) = {my(d = divisors(n)); vecmax(vector(#d, i, invphiMax(d[i])));} \\ Amiram Eldar, Nov 29 2024, using Max Alekseyev's invphi.gp

a(n) = Max_{d|n} A057635(d). - Antti Karttunen, Sep 09 2018

A378636 Irregular triangle read by rows: row n lists all m <= n such that phi(m) divides n, where phi is the Euler totient function (A000010).

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 2, 3, 4, 1, 2, 1, 2, 3, 4, 6, 1, 2, 1, 2, 3, 4, 5, 6, 8, 1, 2, 1, 2, 3, 4, 6, 1, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 1, 2, 1, 2, 3, 4, 6, 1, 2, 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 1, 2, 1, 2, 3, 4, 6, 7, 9, 14, 18, 1, 2, 1, 2, 3, 4, 5, 6, 8, 10, 11, 12

Offset: 1

Paolo Xausa, Dec 02 2024

If n = 2 or an odd number >= 3, row n is {1, 2}.

If n is an even number >= 4, row n begins with {1, 2, 3, 4}.

			Triangle begins:
  n\k| 1  2  3  4  5  6  7   8   9  10  11 ...
  --------------------------------------------
   1 | 1;
   2 | 1, 2;
   3 | 1, 2;
   4 | 1, 2, 3, 4;
   5 | 1, 2;
   6 | 1, 2, 3, 4, 6;
   7 | 1, 2;
   8 | 1, 2, 3, 4, 5, 6, 8;
   9 | 1, 2;
  10 | 1, 2, 3, 4, 6;
  11 | 1, 2;
  12 | 1, 2, 3, 4, 5, 6, 7,  8,  9, 10, 12;
  13 | 1, 2;
  14 | 1, 2, 3, 4, 6;
  15 | 1, 2;
  16 | 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16;
  17 | 1, 2;
  18 | 1, 2, 3, 4, 6, 7, 9, 14, 18;
  19 | 1, 2;
  20 | 1, 2, 3, 4, 5, 6, 8, 10, 11, 12;
  ...

Paolo Xausa, Table of n, a(n) for n = 1..11226 (rows 1..1000 of triangle, flattened).

Cf. A069932 (row lengths), A362469 (row sums), A378637 (right border).
Subsequence of A378638.
Cf. A000010.

With[{nmax = 25}, Table[If[OddQ[n] && n > 2, {1, 2}, PositionIndex[Divisible[n, #[[;; n]]]][True]], {n, nmax}] & [EulerPhi[Range[nmax]]]]

row(n) = select(x->!(n % eulerphi(x)), [1..n]); \\ Michel Marcus, Dec 05 2024

A070633 a(n) is the number of k>0 such that phi(k) divides n.

Original entry on oeis.org

2, 5, 2, 9, 2, 9, 2, 14, 2, 7, 2, 19, 2, 5, 2, 20, 2, 13, 2, 16, 2, 7, 2, 34, 2, 5, 2, 11, 2, 13, 2, 27, 2, 5, 2, 31, 2, 5, 2, 30, 2, 13, 2, 14, 2, 7, 2, 51, 2, 7, 2, 11, 2, 15, 2, 19, 2, 7, 2, 37, 2, 5, 2, 35, 2, 13, 2, 9, 2, 9, 2, 63, 2, 5, 2, 9, 2, 11, 2, 46, 2, 7, 2, 31, 2, 5, 2, 25, 2, 17, 2

Offset: 1

Benoit Cloitre, May 13 2002

Inverse Möbius transform of A014197. - Antti Karttunen, Sep 10 2018

Antti Karttunen, Table of n, a(n) for n = 1..65537
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

Cf. A000010, A014197, A069932, A071181, A319048.

Row lengths of A378638.

for(n=1,120,print1(sum(i=1,100*n,if(n%eulerphi(i),0,1)),","));

\\ In contrast to above program, this is safe in any range 1..n:
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))))}; \\ From A014197 by M. F. Hasler
A070633(n) = sumdiv(n, d, A014197(d)); \\ Antti Karttunen, Sep 10 2018

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

From Antti Karttunen, Sep 10 2018: (Start)
a(n) = Sum_{d|n} A014197(d).
a(n) >= A069932(n).
a(A000010(n)) = A071181(n).
(End)

A378639 a(n) = sum of all m such that phi(m) divides n, where phi is the Euler totient function (A000010).

Original entry on oeis.org

3, 16, 3, 51, 3, 64, 3, 156, 3, 49, 3, 265, 3, 16, 3, 387, 3, 202, 3, 302, 3, 85, 3, 991, 3, 16, 3, 138, 3, 190, 3, 968, 3, 16, 3, 1058, 3, 16, 3, 1240, 3, 340, 3, 419, 3, 157, 3, 2736, 3, 49, 3, 210, 3, 445, 3, 620, 3, 193, 3, 1723, 3, 16, 3, 2283, 3, 334, 3, 51, 3, 262

Offset: 1

Paolo Xausa, Dec 03 2024

nonn

Paolo Xausa, Table of n, a(n) for n = 1..1000

Row sums of A378638.

Cf. A000010, A319048, A362469.

f:= proc(n) local d;
  if n::odd then return 3 fi;
  3+add(convert(numtheory:-invphi(d),`+`), d = select(type,numtheory:-divisors(n),even))
end proc:
map(f, [$1..100]); # Robert Israel, Dec 05 2024

With[{nmax = 100}, Table[If[OddQ[n], 3, Total[PositionIndex[Divisible[n, #[[;; Max[n^2, 6]]]]][True]]], {n, nmax}] & [EulerPhi[Range[nmax^2]]]]

a(n) = vecsum(select(x->!(n % eulerphi(x)), [1..max(n^2, 6)])); \\ Michel Marcus, Dec 05 2024

a(2*k+1) = 3, for k >= 0.

A378640 Smallest m such that phi(m) does not divide n, where phi is the Euler totient function (A000010).

Original entry on oeis.org

3, 5, 3, 7, 3, 5, 3, 7, 3, 5, 3, 11, 3, 5, 3, 7, 3, 5, 3, 7, 3, 5, 3, 11, 3, 5, 3, 7, 3, 5, 3, 7, 3, 5, 3, 11, 3, 5, 3, 7, 3, 5, 3, 7, 3, 5, 3, 11, 3, 5, 3, 7, 3, 5, 3, 7, 3, 5, 3, 15, 3, 5, 3, 7, 3, 5, 3, 7, 3, 5, 3, 11, 3, 5, 3, 7, 3, 5, 3, 7, 3, 5, 3, 11, 3, 5

Offset: 1

Paolo Xausa, Dec 05 2024

Up to n = 10^7 the distinct terms of the sequence (which are also the record values) are {3, 5, 7, 11, 15, 17, 19, 23, 29, 47, 51, 53}. Is this A076245 (for n >= 2)?
First differs from A095366 at n = 60.
It appears that a(n) = A095366(n) except when n = 60*(2*k + 1), with k >= 0, where a(n) = 15 while A095366(n) = 17.

Paolo Xausa, Table of n, a(n) for n = 1..10000

Cf. A000010, A076245, A095366, A378638, A378641, A378642.

A378640[n_] := If[OddQ[n], 3, Module[{m = 4}, While[Divisible[n, EulerPhi[++m]]]; m]];
Array[A378640, 100]

a(n) = 3 if n is odd.

cp's OEIS Frontend

A319048 a(n) is the greatest k such that A000010(k) divides n where A000010 is the Euler totient function.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

A378636 Irregular triangle read by rows: row n lists all m <= n such that phi(m) divides n, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A070633 a(n) is the number of k>0 such that phi(k) divides n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

Formula

A378639 a(n) = sum of all m such that phi(m) divides n, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A378640 Smallest m such that phi(m) does not divide n, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula