A337775 a(n) is the least natural k which is a multiple of prime(n) such that for some m >= 0, phi(k) = rad(k)^m, where phi(k) = A000010(k) and rad(k) = A007947(k).

2, 18, 250, 6174, 3660250, 1542294, 2839714, 41154, 117793122328750, 7978057537338, 2898701538750, 33734898, 29688151506250, 21107677374, 69834458642125879757481250, 3999523458421521342, 7066893211213901574340818, 78246568560768750, 22125777102050046356250

Offset

1,1

Comments

The number m mentioned above is referred to as the order of the corresponding number a(n). The sequence of these orders is in A337776.

Numbers k such that phi(k) = rad(k)^m with m >= 1 are given in A211413. - Andrew Howroyd, Sep 21 2020

References

J.-M. De Koninck, Ces nombres qui nous fascinent, Entry 108, p. 38, Ellipses, Paris 2008.

J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique Des Nombres, Problème 745 ; pp 95; 317-8, Ellipses Paris 2004.

Links

Max Alekseyev, Table of n, a(n) for n = 1..100

J.-M. De Koninck, When the Totient Is the Product of the Squared Prime Divisors: Problem 10966, Amer. Math. Monthly, 111 (2004), p. 536.

Example

For n=12 the initial prime is prime(12) = 37 and a(12) = 33734898 because phi(33734898) = 10941048, rad(33734898) = 222 and 222^3 = 10941048 and there is no smaller number satisfying the requirements. The order of a(12) is 3.

Mathematica

nn = 16;
Sar = Table[0, {nn}]; Sar[[1]] = 2;
(*It is a list oh the sequence A337775*)
OrdSar = Table[0, {nn}]; OrdSar[[1]] = 0;
(*It is a sequence A337776 - the orders of members in sequence A337775*) For[Index = 2, Index <= nn, Index++,
  InitialPrime = Prime[Index];
  InitialInteger = InitialPrime - 1;
  InitialArray = FactorInteger[InitialInteger];
  For[i = 1, i <= Length[InitialArray], i++,
   CurrentArray =
    FactorInteger[InitialArray[[-i, 1]] - 1] ~Join~ InitialArray;
   InitialInterger =
    Product[CurrentArray[[k, 1]] ^ CurrentArray[[k, 2]], {k, 1,
      Length[CurrentArray]}];
     InitialArray = FactorInteger[InitialInterger];
   ];
  InitialArray = InitialArray ~Join~ {{InitialPrime, 0}};
  Ord = Max[InitialArray[[All, 2]]];
  Lint = Product[
    Power[InitialArray[[k, 1]], Ord - InitialArray[[k, 2]] + 1], {k,
     1, Length[InitialArray]}];
  radn = Product[InitialArray[[k, 1]], {k, 1, Length[InitialArray]}];
  Sar[[Index]] = Lint;
  OrdSar[[Index]] = Ord;
  ];
Print["Sar=  ", Sar]
Print["OrdSar=  ", OrdSar]

Prog

(PARI) rad(n) = factorback(factorint(n)[, 1]);
isok(k) = my(phik=eulerphi(k), radk=rad(k), x=logint(phik, radk)); radk^x == phik;
a(n) = {my(p=prime(n), k=p); while (!isok(k), k+=p); k; } \\ Michel Marcus, Sep 23 2020

Crossrefs

Subsequence of A055744 and A211413.

Cf. A000010 (phi), A000040 (prime), A007947 (rad), A023503, A024619, A105261.

Sequence in context: A379253 A121429 A368466 * A276364 A109517 A213643

Adjacent sequences: A337772 A337773 A337774 * A337776 A337777 A337778

Keyword

nonn

Author

Vladislav Shubin, Sep 20 2020

Extensions

Edited and terms a(17) onward added by Max Alekseyev, Oct 02 2025

Status

approved