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

Author

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

Keywords

• easy
• nonn

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.

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.

Programs

Magma

[n: n in [1..300] | forall{d: d in PrimeDivisors(EulerPhi(n)) | IsIntegral(n/d)}]; // Bruno Berselli, Nov 04 2017

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 *)

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

Sage

for n in range(1, 271):
    if euler_phi(n)**2 == euler_phi(euler_phi(n) * n): print(n, end=', ') # Torlach Rush, Oct 01 2024

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