%I #56 Oct 02 2024 14:31:39
%S 1,2,4,6,8,10,12,16,18,20,24,30,32,34,36,40,42,48,50,54,60,64,68,72,
%T 78,80,84,90,96,100,102,108,110,114,120,126,128,136,144,150,156,160,
%U 162,168,170,180,192,200,204,210,216,220,222,228,234,240,250,252,256,270
%N Numbers k such that every prime that divides phi(k) also divides k.
%C Alternative descriptions:
%C (a) For every prime p|n and every prime q|p-1 we have q|n;
%C (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.
%C These numbers are "valid bases".
%C Numbers n such that radical of phi(n) divides n. - _Michel Marcus_, Nov 06 2017
%C Pollack and Pomerance call these numbers "phi-deficient numbers". - _Amiram Eldar_, Jun 02 2020
%H Paolo P. Lava, <a href="/A151999/b151999.txt">Table of n, a(n) for n = 1..10000</a>
%H Paul Pollack and Carl Pomerance, <a href="http://www.emis.de/journals/INTEGERS/papers/a14self/a14self.Abstract.html">Prime-Perfect Numbers</a>, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 12a, Paper A14, 2012.
%H J. Jimenez Urroz and J. Luis A. Yebra, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Yebra/yebra4.html">On the equation a^x=x mod b^n</a>, Journal of Integer Sequences, Vol. 12 (2009), Article 09.8.8.
%p A151999 := proc(n)
%p if n = 1 then
%p 2;
%p else
%p for a from procname(n-1)+1 do
%p pdvs := numtheory[factorset](a) ;
%p aworks := true;
%p for p in numtheory[factorset](a) do
%p for q in numtheory[factorset](p-1) do
%p if a mod q = 0 then
%p ;
%p else
%p aworks := false;
%p end if;
%p end do:
%p end do:
%p if aworks then
%p return a;
%p end if;
%p end do:
%p end if;
%p end proc: # _R. J. Mathar_, Jun 01 2013
%t Rad[n_]:=Times@@Transpose[FactorInteger[n]][[1]]; Select[1 + Range[300], Mod[Rad[#], Rad[EulerPhi[#]]]==0 &] (* _José María Grau Ribas_, Jan 09 2012 *)
%o (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
%o (PARI) isok(n) = (n % factorback(factor(eulerphi(n))[, 1])) == 0; \\ _Michel Marcus_, Nov 04 2017
%o (Magma) [n: n in [1..300] | forall{d: d in PrimeDivisors(EulerPhi(n)) | IsIntegral(n/d)}]; // _Bruno Berselli_, Nov 04 2017
%o (Sage)
%o for n in range(1, 271):
%o if euler_phi(n)**2 == euler_phi(euler_phi(n) * n): print(n, end=', ') # _Torlach Rush_, Oct 01 2024
%Y Cf. A005117, A055744, A073539.
%Y Cf. A007947 (radical of n), A007694 (phi(n) divides n, a subsequence).
%Y Cf. A080400 (radical of phi(n)).
%Y Cf. A152000.
%K easy,nonn
%O 1,2
%A J. Luis A. Yebra and J. Jimenez Urroz (yebra(AT)mat.upc.es), Nov 19 2008
%E Corrected by _Michel Marcus_, Jun 01 2013
%E Edited by _N. J. A. Sloane_, Jun 02 2013 at the suggestion of _Michel Marcus_, merging this with A204010
%E Deleted erroneous comment and added correct b-file by _Paolo P. Lava_, Nov 06 2017