A066676 -id:A066676 - cp's OEIS frontend

A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.

1, 3, 7, 5, 11, 7, 29, 15, 19, 11, 23, 13, 53, 29, 31, 17, 103, 19, 191, 25, 43, 23, 47, 35, 101, 53, 81, 29, 59, 31, 311, 51, 67, 103, 71, 37, 149, 191, 79, 41, 83, 43, 173, 69, 181, 47, 283, 65, 197, 101, 103, 53, 107, 81, 121, 87, 229, 59, 709, 61, 367, 311, 127, 85

Offset: 1

Melvin J. Knight (knightmj(AT)juno.com), May 25 2001

nonn

Conjecture: a(n) is odd for all n. Verified up to n <= 3*10^5. - Jianing Song, Feb 21 2021

The conjecture above is false because a(16842752) = 33817088; see A002181 and A143510. - Flávio V. Fernandes, Oct 08 2023

			a(48) = 65 because phi(65) = phi(5)*phi(13) = 4*12 = 48 and no smaller integer m has phi(m) divisible by 48.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from T. D. Noe)
Ho-joo Lee and Gerald Myerson, Consecutive Integers Whose Totients Are Multiples of n: 10837, The American Mathematical Monthly, Vol. 110, No. 2 (Feb., 2003), pp. 158-159.
Pieter Moree and Hans Roskam, On an arithmetical function related to Euler's totient and the discriminator, Fib. Quart., Vol. 33, No. 4 (1995), pp. 332-340.
József Sándor, On the Euler minimum and maximum functions, Notes on Number Theory and Discrete Mathematics, Volume 15, 2009, Number 3, pp. 1-8.

Cf. A000010, A066674, A066675, A066676, A066678, A067005.
Cf. A233516, A233517 (records).
Cf. A005179 (analog for number of divisors), A070982 (analog for sum of divisors).

a = ConstantArray[1, 64]; k = 1; While[Length[vac = Rest[Flatten[Position[a, 1]]]] > 0, k++; a[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; a  (* Ivan Neretin, May 15 2015 *)

a(n) = my(s=1); while(eulerphi(s)%n, s++); s;
vector(100, n, a(n))

from sympy import totient as phi
def a(n):
  k = 1
  while phi(k)%n != 0: k += 1
  return k
print([a(n) for n in range(1, 65)]) # Michael S. Branicky, Feb 21 2021

Sequence is unbounded; a(n) <= n^2 since phi(n^2) is always divisible by n.
If n+1 is prime then a(n) = n+1.
a(n) = min{ k : phi(k) == 0 (mod n) }.
a(n) = a(2n) for odd n > 1. - Jianing Song, Feb 21 2021

A066678 Totients of the least numbers for which the totient is divisible by n.

Original entry on oeis.org

1, 2, 6, 4, 10, 6, 28, 8, 18, 10, 22, 12, 52, 28, 30, 16, 102, 18, 190, 20, 42, 22, 46, 24, 100, 52, 54, 28, 58, 30, 310, 32, 66, 102, 70, 36, 148, 190, 78, 40, 82, 42, 172, 44, 180, 46, 282, 48, 196, 100, 102, 52, 106, 54, 110, 56, 228, 58, 708, 60, 366, 310, 126, 64

Offset: 1

Labos Elemer, Dec 22 2001

nonn

From Alonso del Arte, Feb 03 2017: (Start)
One of the less obvious consequences of Dirichlet's theorem on primes in arithmetic progression is that this sequence is well-defined for all positive integers.
Suppose n is a nontotient (see A007617). Obviously a(n) != n. Dirichlet's theorem assures us that, if nothing else, there are infinitely many primes of the form nk + 1 for k positive (and in this case, k > 1). Then phi(nk + 1) = nk, suggesting a(n) = nk corresponding to the smallest k.
Of course not all a(n) are 1 less than a prime, such as 8, 20, 24, 54, etc. (End)

			a(23) = 46 because there is no solution to phi(x) = 23 but there are solutions to phi(x) = 46, like x = 47.
a(24) = 24 because there are solutions to phi(x) = 24, such as x = 35.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..5000 from Vincenzo Librandi)

Cf. A000010, A066674, A066675, A066676, A066677, A067005, A061026.

EulerPhi[mulTotientList = ConstantArray[1, 70]; k = 1; While[Length[vac = Rest[Flatten[Position[mulTotientList, 1]]]] > 0, k++; mulTotientList[[Intersection[Divisors[EulerPhi[k]], vac]]] *= k]; mulTotientList] (* Vincenzo Librandi Feb 04 2017 *)
a[n_] := For[k=1, True, k++, If[Divisible[t = EulerPhi[k], n], Return[t]]];
Array[a, 64] (* Jean-François Alcover, Jul 30 2018 *)

list(len) = {my(v = vector(len), c = 0, k = 1, e); while(c < len, e = eulerphi(k); fordiv(e, d, if(d <= len && v[d] == 0, v[d] = e; c++)); k++); v;} \\ Amiram Eldar, Mar 07 2025

def A066678(n):
    s = 1
    while euler_phi(s) % n: s += 1
    return euler_phi(s)
print([A066678(n) for n in (1..64)]) # Peter Luschny, Feb 05 2017

a(n) = A000010(A061026(n)).

A066675 a(n) = A066674(n)-1 divided by the n-th prime.

Original entry on oeis.org

1, 2, 2, 4, 2, 4, 6, 10, 2, 2, 10, 4, 2, 4, 6, 2, 12, 6, 4, 8, 4, 4, 2, 2, 4, 6, 6, 6, 10, 2, 4, 2, 6, 4, 8, 6, 10, 4, 14, 2, 2, 6, 2, 4, 18, 4, 10, 12, 24, 12, 2, 2, 6, 2, 6, 6, 8, 6, 4, 2, 6, 2, 4, 6, 6, 26, 6, 10, 6, 10, 14, 2, 6, 4, 12, 12, 24, 6, 8, 4, 2, 10, 2, 4, 10, 2, 8, 30, 6, 12, 6, 8, 4

Offset: 1

Labos Elemer, Dec 19 2001

nonn

Is this a duplicate of A035096? - R. J. Mathar, Dec 15 2008

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

Cf. A000010, A000040, A035096, A066674, A066675, A066676, A066677, A066678.

a(n) = min{m : phi(m) == 0 (mod p(n))} = min{m : A000010(m) == 0 (mod A000040(n))}.

a(2) corrected by R. J. Mathar, Dec 15 2008

A067005 Totient of A061026(n) divided by n.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 4, 1, 2, 1, 2, 1, 4, 2, 2, 1, 6, 1, 10, 1, 2, 1, 2, 1, 4, 2, 2, 1, 2, 1, 10, 1, 2, 3, 2, 1, 4, 5, 2, 1, 2, 1, 4, 1, 4, 1, 6, 1, 4, 2, 2, 1, 2, 1, 2, 1, 4, 1, 12, 1, 6, 5, 2, 1, 2, 1, 4, 2, 2, 1, 8, 1, 4, 2, 2, 3, 6, 1, 4, 1, 2, 1, 2, 1, 12, 2, 4, 1, 2, 2, 6, 1, 4, 3, 2, 1, 4, 2, 2, 1

Offset: 1

Labos Elemer, Dec 22 2001

nonn

			n = 24: a(24) = 1 = phi(A061026(24))/24 = phi(35)/24 = 24/24;
n = 85: a(85) = 12 = phi(A061026(85))/85 = 1020/85.

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Zak Seidov)

Cf. A000010, A061026, A066674, A066675, A066676, A066677, A066678.

Table[m = 1; While[! Divisible[Set[k, EulerPhi@ m], n], m++]; k/n, {n, 100}] (* Michael De Vlieger, Mar 18 2017 *)

for(n=1,100, s=1; while((e=eulerphi(s))%n>0, s++); print1(e/n ", ")); \\ Zak Seidov, Feb 22 2014

list(len) = {my(v = vector(len), c = 0, k = 1, e); while(c < len, e = eulerphi(k); fordiv(e, d, if(d <= len && v[d] == 0, v[d] = e/d; c++)); k++); v; } \\ Amiram Eldar, Mar 08 2025

from sympy.ntheory import totient
def k(n):
    m=1
    while totient(m)%n: m+=1
    return m
print([totient(k(n))//n for n in range(1, 101)]) # Indranil Ghosh, Mar 18 2017

a(n) = A000010(A061026(n))/n.

a(n) = A066678(n)/n. - Amiram Eldar, Mar 08 2025

A067006 Smallest number for which the totient is divisible by the n-th nontotient number, that is, the n-th term of A007617.

Original entry on oeis.org

7, 11, 29, 19, 23, 53, 29, 31, 103, 191, 43, 47, 101, 53, 81, 59, 311, 67, 103, 71, 149, 191, 79, 83, 173, 181, 283, 197, 101, 103, 107, 121, 229, 709, 367, 311, 127, 131, 269, 137, 139, 569, 293, 149, 151, 229, 463, 317, 163, 167, 1021, 173, 349, 179, 181, 547

Offset: 1

Labos Elemer, Dec 22 2001

nonn

			14 = A007617(7) is not totient of any other number, but phi(29) = 28 is divisible by 14 and 29 is the smallest number of which the totient is a multiple of 14, so a(7)=29.

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

Cf. A000010, A007617, A066674, A066675, A066676, A066677, A066678, A067005.

a(n) = min_{x : mod(phi(x), A007617(n)) = 0}. For all nontotient numbers x, q*x+1 is prime with large enough q and a divisor of phi(q*x+1) = q*x is x, the selected nontotient number. [Corrected by Sean A. Irvine, Nov 28 2023]

cp's OEIS Frontend

A061026 Smallest number m such that phi(m) is divisible by n, where phi = Euler totient function A000010.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A066678 Totients of the least numbers for which the totient is divisible by n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A066675 a(n) = A066674(n)-1 divided by the n-th prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A067005 Totient of A061026(n) divided by n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

A067006 Smallest number for which the totient is divisible by the n-th nontotient number, that is, the n-th term of A007617.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula