A058215 -id:A058215 - cp's OEIS frontend

A053576 Smallest number whose Euler totient is divisible by 2^n.

1, 3, 5, 15, 17, 51, 85, 255, 257, 771, 1285, 3855, 4369, 13107, 21845, 65535, 65537, 196611, 327685, 983055, 1114129, 3342387, 5570645, 16711935, 16843009, 50529027, 84215045, 252645135, 286331153, 858993459, 1431655765, 4294967295, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776

Offset: 0

Labos Elemer, Jan 18 2000

nonn

n = 32 is the first place where this differs from A001317, since 2^32 + 1 is not prime. - Mitch Harris, May 02 2007
a(8589934592) is the first unknown term; it is 2^8589934593 if F(33) = 2^(2^33)+1 is composite or F(33) otherwise. - Charles R Greathouse IV, Jul 15 2013
a(n) is the only odd element of the set phi-1(2^n), the totient inverses of 2^n. All other elements are 2*a(n), and the even elements of phi-1(2^(n-1)) * 2. - Torlach Rush, Sep 05 2017

			1,2,4,8,...,131072 divide phi of 2,3,5,15,...,196611 = 3*65537 respectively.

Charles R Greathouse IV, Table of n, a(n) for n = 0..3320

Cf. A000010, A003401, A001317, A045544, A058213, A058214, A058215.

Not the same as A001317.

With[{s = Array[EulerPhi, 10^6]}, Table[FirstPosition[s, ?(Divisible[#, 2^n] &)][[1]], {n, 0, 19}]] (* _Michael De Vlieger, Sep 05 2017 *)

a(n)={
  if(n >= 8589934592 && valuation(n>>5,2)>27,
    warning("Result is conjectural on the nonexistence of Fermat primes >= F(33).")
  );
  if(n>31,
    return(2<Charles R Greathouse IV, Jul 15 2013

More odd terms from Jud McCranie, Jan 25 2000

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

Original entry on oeis.org

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

Labos Elemer, Nov 30 2000

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

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

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

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

Edited by Dean Hickerson, Jan 25 2002

A058214 Sum of solutions of phi(x) = 2^n.

Original entry on oeis.org

3, 13, 35, 105, 231, 581, 1315, 3225, 6711, 15221, 32755, 74505, 154407, 339397, 718115, 1589145, 3243831, 6946421, 14482675, 31259145, 63894567, 135588037, 281203235, 601400985, 1219907127, 2557715317, 5267017715, 11123540745, 22600784679, 47205887429

Offset: 0

Labos Elemer, Nov 30 2000

nonn

			For n = 6, 2^n = 64; the solutions of phi(x) = 64 are {85,128,136,160,170,192,204,240}, whose sum is a(6) = 1315.

Amiram Eldar, Table of n, a(n) for n = 0..1000 (terms 0..100 from T. D. Noe)
Max Alekseyev, PARI/GP Scripts for Miscellaneous Math Problems (invphi.gp).

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

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]]; Table[Plus@@phiinv[2^n], {n, 0, 30}] (* 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 *)

a(n) = vecsum(invphi(2^n)); \\ Amiram Eldar, Nov 11 2024, using Max Alekseyev's invphi.gp

If there are only five Fermat primes, then a(n) = 2^(n-30) * 99852066765 for n > 31. - T. D. Noe, Jun 21 2012

Edited by Dean Hickerson, Jan 25 2002

a(28)-a(29) from Donovan Johnson, Oct 22 2011

cp's OEIS Frontend

A053576 Smallest number whose Euler totient is divisible by 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A058214 Sum of solutions of phi(x) = 2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions