A058213 Triangular arrangement of solutions of phi(x) = 2^n (n >= 0), where phi=A000010 is Euler's totient function. Each row corresponds to a particular n and its length is n+2 for 0 <= n <= 31, 32 for n >= 32. (This assumes that there are only 5 Fermat primes.)

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, 255, 256, 272, 320, 340, 384, 408, 480, 510, 257, 512, 514, 544, 640, 680, 768, 816, 960, 1020, 771, 1024, 1028, 1088

Offset

0,2

Comments

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.

Links

T. D. Noe, Table of n, a(n) for n = 0..1000

Example

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},
  ...

Mathematica

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

Crossrefs

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

Sequence in context: A080738 A032447 A224531 * A348711 A080997 A151942

Adjacent sequences: A058210 A058211 A058212 * A058214 A058215 A058216

Keyword

nonn,tabf

Author

Labos Elemer, Nov 30 2000

Extensions

Edited by Dean Hickerson, Jan 25 2002

Status

approved