A378636 -id:A378636 - cp's OEIS frontend

A069932 Number of k, 1<=k<=n, such that phi(k) divides n.

1, 2, 2, 4, 2, 5, 2, 7, 2, 5, 2, 11, 2, 5, 2, 11, 2, 9, 2, 10, 2, 5, 2, 19, 2, 5, 2, 9, 2, 11, 2, 16, 2, 5, 2, 20, 2, 5, 2, 18, 2, 9, 2, 10, 2, 5, 2, 32, 2, 7, 2, 9, 2, 13, 2, 15, 2, 5, 2, 26, 2, 5, 2, 22, 2, 11, 2, 9, 2, 7, 2, 38, 2, 5, 2, 9, 2, 9, 2, 30, 2, 5, 2, 23, 2, 5, 2, 17, 2, 17, 2, 10, 2, 5

Offset: 1

Benoit Cloitre, May 05 2002

Unlike A070633, this sequence does not give the number of all integers of the form phi(k) dividing n (for some n and some m > n, phi(m) divides n).

Antti Karttunen, Table of n, a(n) for n = 1..65537
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).
Vaclav Kotesovec, Plot of Sum_{k=1..n} a(k)/(n*log(n)) for n = 2..65537 (based on b-file).

Cf. A000010, A070633, A378642.

Row lengths of A378636.

a[n_] := Boole[ Divisible[n, EulerPhi[#]]] & /@ Range[n] // Total; Table[a[n], {n, 1, 94}] (* Jean-François Alcover, May 23 2013 *)

for(n=1,150,print1(sum(i=1,n,if(n%eulerphi(i),0,1)),","))

a(n)=if(n<1,0,polcoeff(sum(k=1,n,1/(1-x^eulerphi(k)),x*O(x^n)),n))

A069932(n) = sum(k=1, n, !(n%eulerphi(k))); \\ Antti Karttunen, Sep 10 2018

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

Asymptotically (still conjectured): Sum_{k=1..n} a(k) = C*n*log(n) + o(n*log(n)) with C = 1.5...
G.f.: Sum_{k>=1} 1/(1-x^phi(k)).
a(n) <= A070633(n). - Antti Karttunen, Sep 10 2018
a(n) = Sum_{k=1..n} (1 - ceiling(n/phi(k)) + floor(n/phi(k))). - Wesley Ivan Hurt, Apr 21 2023
a(n) = n - A378642(n). - Paolo Xausa, Dec 06 2024

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

Original entry on oeis.org

1, 2, 1, 2, 3, 4, 6, 1, 2, 1, 2, 3, 4, 5, 6, 8, 10, 12, 1, 2, 1, 2, 3, 4, 6, 7, 9, 14, 18, 1, 2, 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 1, 2, 1, 2, 3, 4, 6, 11, 22, 1, 2, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 14, 18, 21, 26, 28, 36, 42, 1, 2, 1, 2, 3, 4, 6, 1, 2

Offset: 1

Paolo Xausa, Dec 03 2024

If n is odd, row n is {1, 2}.

If n is even, row n begins with {1, 2, 3, 4}.

			Triangle begins:
  n\k| 1  2  3  4  5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20 ...
  ----------------------------------------------------------------------------------
   1 | 1, 2;
   2 | 1, 2, 3, 4, 6;
   3 | 1, 2;
   4 | 1, 2, 3, 4, 5,  6,  8, 10, 12;
   5 | 1, 2;
   6 | 1, 2, 3, 4, 6,  7,  9, 14, 18;
   7 | 1, 2;
   8 | 1, 2, 3, 4, 5,  6,  8, 10, 12, 15, 16, 20, 24, 30;
   9 | 1, 2;
  10 | 1, 2, 3, 4, 6, 11, 22;
  11 | 1, 2;
  12 | 1, 2, 3, 4, 5,  6,  7,  8,  9, 10, 12, 13, 14, 18, 21, 26, 28, 36, 42;
  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, 20, 24, 30, 32, 34, 40, 48, 60;
  17 | 1, 2;
  18 | 1, 2, 3, 4, 6,  7,  9, 14, 18, 19, 27, 38, 54;
  19 | 1, 2;
  20 | 1, 2, 3, 4, 5,  6,  8, 10, 11, 12, 22, 25, 33, 44, 50, 66;
  ...

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

Cf. A070633 (row lengths), A319048 (right border), A378639 (row sums).
Supersequence of A378636.
Cf. A000010.

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

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

T(n,k) <= n^2, for n > 2 (see A319048).

A378637 Largest m <= n such that phi(m) divides n, where phi is the Euler totient function (A000010).

Original entry on oeis.org

1, 2, 2, 4, 2, 6, 2, 8, 2, 6, 2, 12, 2, 6, 2, 16, 2, 18, 2, 12, 2, 6, 2, 24, 2, 6, 2, 12, 2, 22, 2, 32, 2, 6, 2, 36, 2, 6, 2, 33, 2, 18, 2, 23, 2, 6, 2, 48, 2, 22, 2, 12, 2, 54, 2, 30, 2, 6, 2, 50, 2, 6, 2, 64, 2, 46, 2, 12, 2, 22, 2, 72, 2, 6, 2, 12, 2, 18, 2, 75

Offset: 1

Paolo Xausa, Dec 03 2024

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

Right border of A378636.

Cf. A000010, A319048, A378641.

A378637[n_] := If[OddQ[n] && n > 2, 2, Module[{m = n}, While[!Divisible[n, EulerPhi[m]], m--]; m]];
Array[A378637, 100]

a(n) = my(m=n); while (n % eulerphi(m), m--); m; \\ Michel Marcus, Dec 05 2024

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

A378641 Largest m <= n such that phi(m) does not divide n, or -1 if no such m exists, where phi is the Euler totient function (A000010).

Original entry on oeis.org

-1, -1, 3, -1, 5, 5, 7, 7, 9, 10, 11, 11, 13, 14, 15, 14, 17, 17, 19, 20, 21, 22, 23, 23, 25, 26, 27, 28, 29, 30, 31, 31, 33, 34, 35, 35, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 47, 49, 50, 51, 52, 53, 53, 55, 56, 57, 58, 59, 60, 61, 62, 63, 63, 65, 66, 67, 68, 69

Offset: 1

Paolo Xausa, Dec 05 2024

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

Cf. A000010, A378636, A378637, A378640, A378642.

A378641[n_] := Module[{m = n}, While[m > 0 && Divisible[n, EulerPhi[m]], m--]; If[m == 0, -1, m]];
Array[A378641, 100]

a(n) = n if n is an odd number >= 3.

A362469 Sum of the numbers k, 1 <= k <= n, such that phi(k) | n.

Original entry on oeis.org

1, 3, 3, 10, 3, 16, 3, 29, 3, 16, 3, 67, 3, 16, 3, 82, 3, 64, 3, 62, 3, 16, 3, 208, 3, 16, 3, 51, 3, 97, 3, 205, 3, 16, 3, 269, 3, 16, 3, 247, 3, 64, 3, 74, 3, 16, 3, 660, 3, 49, 3, 51, 3, 202, 3, 185, 3, 16, 3, 481, 3, 16, 3, 502, 3, 133, 3, 51, 3, 49, 3, 1034, 3, 16, 3, 51, 3

Offset: 1

Wesley Ivan Hurt, Apr 21 2023

			a(4) = 10: for the numbers 1..4, phi(1)=1|4, phi(2)=1|4, phi(3)=2|4, and phi(4)=2|4. Their sum is then 1+2+3+4 = 10.

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

Cf. A000010, A069932.

Row sums of A378636.

a[n_] := Sum[If[Divisible[n, EulerPhi[k]], k, 0], {k, 1, n}]; Array[a, 100] (* Amiram Eldar, Apr 22 2023 *)

a(n) = sum(k=1, n, if (!(n % eulerphi(k)), k)); \\ Michel Marcus, Apr 22 2023

a(n) = Sum_{k=1..n} k * (1 - ceiling(n/phi(k)) + floor(n/phi(k))).

cp's OEIS Frontend

A069932 Number of k, 1<=k<=n, such that phi(k) divides n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A378637 Largest m <= n such that phi(m) divides n, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A378641 Largest m <= n such that phi(m) does not divide n, or -1 if no such m exists, where phi is the Euler totient function (A000010).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A362469 Sum of the numbers k, 1 <= k <= n, such that phi(k) | n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula