0,2

phi(x) is a power of 2 if and only if x is a power of 2 multiplied by a product of distinct Fermat primes. So if, as is conjectured, there are only 5 Fermat primes, then there are only 32 possibilities for the odd part of x, namely the divisors of 2^32-1, given in A004729.

The same numbers, in increasing order, are given in A003401.

The first entry in row n is the n-th divisor of 2^32-1 for 0<=n<=31 (A004729) and is 2^(n+1) for n>=32. The last entry in row n is given in A058215.

Triangle begins {1,2}, {3,4,6}, {5,8,10,12}, {15,16,20,24,30}, {17,32,34,40,48,60}, {51,64,68,80,96,102,120}, {85,128,136,160,170,192,204,240}, ...

phiinv[ n_, pl_ ] := Module[ {i, p, e, pe, val}, If[ pl=={}, Return[ If[ n==1, {1}, {} ] ] ]; val={}; p=Last[ pl ]; For[ e=0; pe=1, e==0||Mod[ n, (p-1)pe/p ]==0, e++; pe*=p, val=Join[ val, pe*phiinv[ If[ e==0, n, n*p/pe/(p-1) ], Drop[ pl, -1 ] ] ] ]; Sort[ val ] ]; phiinv[ n_ ] := phiinv[ n, Select[ 1+Divisors[ n ], PrimeQ ] ]; Join@@(phiinv[ 2^# ]&/@Range[ 0, 10 ]) (* phiinv[ n, pl ] = list of x with phi(x)=n and all prime divisors of x in list pl. phiinv[ n ] = list of x with phi(x)=n *)

Cf. A000010, A001317, A003401, A004729, A019434, A045544, A047999, A053576, A054432, A058214, A058215.

Adjacent sequences: A058210 A058211 A058212 this_sequence A058214 A058215 A058216

Sequence in context: A118316 A080738 A032447 this_sequence A080997 A054582 A099884

nonn,tabf

Labos E. (labos(AT)ana.sote.hu), Nov 30 2000

Edited by Dean Hickerson (dean(AT)math.ucdavis.edu), Jan 25 2002