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

Author

Labos Elemer, Nov 30 2000

Keywords

• nonn
• tabf

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.

Examples

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

Links

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

Crossrefs

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

Programs

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

Extensions

Edited by Dean Hickerson, Jan 25 2002