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

%I #22 Nov 11 2024 05:20:59

%S 3,13,35,105,231,581,1315,3225,6711,15221,32755,74505,154407,339397,

%T 718115,1589145,3243831,6946421,14482675,31259145,63894567,135588037,

%U 281203235,601400985,1219907127,2557715317,5267017715,11123540745,22600784679,47205887429

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

%H Amiram Eldar, <a href="/A058214/b058214.txt">Table of n, a(n) for n = 0..1000</a> (terms 0..100 from T. D. Noe)

%H Max Alekseyev, <a href="https://oeis.org/wiki/User:Max_Alekseyev/gpscripts">PARI/GP Scripts for Miscellaneous Math Problems</a> (invphi.gp).

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

%e 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.

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

%o (PARI) a(n) = vecsum(invphi(2^n)); \\ _Amiram Eldar_, Nov 11 2024, using _Max Alekseyev_'s invphi.gp

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

%K nonn

%O 0,1

%A _Labos Elemer_, Nov 30 2000

%E Edited by _Dean Hickerson_, Jan 25 2002

%E a(28)-a(29) from _Donovan Johnson_, Oct 22 2011