A151999 Numbers k such that every prime that divides phi(k) also divides k.

1, 2, 4, 6, 8, 10, 12, 16, 18, 20, 24, 30, 32, 34, 36, 40, 42, 48, 50, 54, 60, 64, 68, 72, 78, 80, 84, 90, 96, 100, 102, 108, 110, 114, 120, 126, 128, 136, 144, 150, 156, 160, 162, 168, 170, 180, 192, 200, 204, 210, 216, 220, 222, 228, 234, 240, 250, 252, 256, 270

Offset

1,2

Comments

Alternative descriptions:

(a) For every prime p|n and every prime q|p-1 we have q|n;

(b) Numbers n such that radical of phi(n) divides radical of n, where phi is Euler's totient function and radical is the squarefree kernel function.

These numbers are "valid bases".

Numbers n such that radical of phi(n) divides n. - Michel Marcus, Nov 06 2017

Pollack and Pomerance call these numbers "phi-deficient numbers". - Amiram Eldar, Jun 02 2020

Links

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

Paul Pollack and Carl Pomerance, Prime-Perfect Numbers, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.

J. Jimenez Urroz and J. Luis A. Yebra, On the equation a^x=x mod b^n, Journal of Integer Sequences, Vol. 12 (2009), Article 09.8.8.

Maple

A151999 := proc(n)
    if n = 1 then
        2;
    else
        for a from procname(n-1)+1 do
            pdvs := numtheory[factorset](a) ;
            aworks := true;
            for p in numtheory[factorset](a) do
                for q in numtheory[factorset](p-1) do
                    if a mod q = 0 then
                        ;
                    else
                        aworks := false;
                    end if;
                end do:
            end do:
            if aworks then
                return a;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Jun 01 2013

Mathematica

Rad[n_]:=Times@@Transpose[FactorInteger[n]][[1]]; Select[1 + Range[300], Mod[Rad[#], Rad[EulerPhi[#]]]==0 &] (* José María Grau Ribas, Jan 09 2012 *)

Prog

(PARI) isok(n) = {fp = factor(n); for (i=1, #fp[, 1], fq = factor(fp[i, 1] - 1); for (j=1, #fq[, 1], if (n % fq[j, 1], return (0)); ); ); return (1); } \\ Michel Marcus, Jun 01 2013
(PARI) isok(n) = (n % factorback(factor(eulerphi(n))[, 1])) == 0; \\ Michel Marcus, Nov 04 2017
(Magma) [n: n in [1..300] | forall{d: d in PrimeDivisors(EulerPhi(n)) | IsIntegral(n/d)}]; // Bruno Berselli, Nov 04 2017

Crossrefs

Cf. A005117, A055744, A073539.

Cf. A007947 (radical of n), A007694 (phi(n) divides n, a subsequence).

Cf. A080400 (radical of phi(n)).

Cf. A152000.

Sequence in context: A213708 A371176 A239063 * A267817 A177917 A071594

Adjacent sequences: A151996 A151997 A151998 * A152000 A152001 A152002

Keyword

easy,nonn

Author

J. Luis A. Yebra and J. Jimenez Urroz (yebra(AT)mat.upc.es), Nov 19 2008

Extensions

Corrected by Michel Marcus, Jun 01 2013

Edited by N. J. A. Sloane, Jun 02 2013 at the suggestion of Michel Marcus, merging this with A204010

Deleted erroneous comment and added correct b-file by Paolo P. Lava, Nov 06 2017

Status

approved