Sum of primitive roots

[petsie at dordos.net]

Maybe I made an error when coding this problem...
I find the start of this sequence until 162 but no more elements up to 10000.
Is this correct?

Peter

Mathematica code follows:

sumsto[{}, _] = False; 
sumsto[{___, n_, ___}, n_] = True; 
sumsto[{a_, b_, r___}, n_] := If[a + b === n, True, 
   If[a + b < n, sumsto[{b, r}, n - a] || sumsto[{a, r}, n - b] ||
                 sumsto[{r}, n - a - b] || sumsto[{r}, n],
      False]];

PrimitiveRoots[n_Integer?Positive] := Select[Range[n - 1],
  GCD[n, #1] === 1 && MultiplicativeOrder[#1, n] === EulerPhi[n] &]

With[{n = 10000}, Timing[(Complement[#1, 
  Pick[#1, (sumsto[PrimitiveRoots[#1], #1] & ) /@ #1]] & )[
    Union[Flatten[{2, 4, ((Prime[Range[2, PrimePi[Floor[n^(1/#1)]]]]^#1 & ) /@
      Range[Floor[Log[3, n]]]*#1 & ) /@ {1, 2}}]]]]]

(* this gives here:
{1090.703 Second, {2, 3, 4, 6, 7, 9, 11, 14, 18, 22, 38, 54, 162}}
*)

On Tue, 8 Jan 2008, Robert Israel wrote:

> It's interesting to note, btw, that although this sequence contains
> 6=2*3, 18=2*3^2, 54=2*3^3 and 162=2*3^4, it does not contain
> 486=2*3^5, as 47 + 65 + 77 + 83 + 101 + 113 = 486.

> Why not allow all the positive integers that have primitive roots, so 
> include 4, p^n and 2 p^n as candidates (for positive integers n and odd
> primes p)?
> Then I believe you get 2,3,4,6,7,9,11,14,18,22,38,54,162,...
>
> Robert Israel                                israel at math.ubc.ca
> Department of Mathematics        http://www.math.ubc.ca/~israel 
> University of British Columbia            Vancouver, BC, Canada
>
> On Tue, 8 Jan 2008, franktaw at netscape.net wrote:
>
>> 2,3,7,11.
>> 
>> These primes cannot be represented as a sum of their (distinct) 
>> primitive roots (requiring the root to be positive).  Are there any 
>> others?
>> 
>> I have checked up to p = 167.  Note that it is not necessary to check 
>> primes = 1 (mod 4), since for such primes, if k is a primitive root, so 
>> is p - k.  It seems very unlikely that there are any others, but I 
>> don't see  how to prove it.
>> 
>> Assuming that this list is complete, should this be in the OEIS?
>> 
>> Franklin T. Adams-Watters
>> 
>> 
>> ________________________________________________________________________
>> More new features than ever.  Check out the new AIM(R) Mail ! - 
>> http://webmail.aim.com
>> 
>