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

%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