A275985 Least k such that n divides phi(k!) (k > 0).

1, 3, 6, 4, 10, 6, 14, 4, 7, 10, 22, 6, 26, 14, 10, 5, 34, 7, 38, 10, 14, 22, 46, 6, 11, 26, 9, 14, 58, 10, 62, 5, 22, 34, 14, 7, 74, 38, 26, 10, 82, 14, 86, 22, 10, 46, 94, 6, 21, 11, 34, 26, 106, 9, 22, 14, 38, 58, 118, 10, 122, 62, 14, 6, 26, 22, 134, 34, 46, 14, 142, 7, 146

Offset

1,2

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

From Robert Israel, Aug 15 2016: (Start)

If m and n are coprime then a(m*n) = max(a(m),a(n)).

a(n) <= 2n, with equality iff n is an odd prime.

Suppose p is an odd prime. Then

a(p) = 2p

If 2p+1 is prime then a(p^2) = 2p+1 and a(p^3) = 3p.

Otherwise a(p^2) = 3p and a(p^3) = 4p. (End)

Example

a(4) = 4 because 4 divides phi(4!) = 8.

Maple

A:= proc(n) option remember;
    local F, p, e, t, k;
    F:= ifactors(n)[2];
    if nops(F)=1 then
      p:= F[1][1];
      e:= F[1][2];
      if p = 2 then
         t:= 1; if e=1 then return 3 fi;
      else
         t:= 0
      fi;
      for k from 2*p by p do
        t:= t + padic:-ordp(k, p);
        if t >= e then return k fi;
        if isprime(k+1) then
          t:= t+padic:-ordp(k, p);
          if t >= e then return(k+1) fi;
        fi;
      od
    else
      max(seq(procname(t[1]^t[2]), t=F))
    fi
end proc:
A(1):= 1:
map(A, [$1..100]); # Robert Israel, Aug 15 2016

Mathematica

With[{ep=Table[{EulerPhi[k!], k}, {k, 200}]}, Table[SelectFirst[ep, Divisible[#[[1]], n]&], {n, 80}]][[All, 2]] (* Requires Mathematica version 10 or later *) (* Harvey P. Dale, May 22 2018 *)

Prog

(PARI) a(n) = {my(k = 1); while(eulerphi(k!) % n, k++); k; }

Crossrefs

Cf. A048855.

Sequence in context: A316478 A242224 A294671 * A163294 A168577 A122634

Adjacent sequences: A275982 A275983 A275984 * A275986 A275987 A275988

Keyword

nonn,look

Author

Altug Alkan, Aug 15 2016

Status

approved