login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A299754 Number of distinct sums of n complex n-th roots of 1. 1
1, 3, 10, 25, 126, 127, 1716, 2241, 18469, 15231, 352716, 36973, 5200300, 1799995, 30333601, 24331777, 1166803110, 12247363, 17672631900, 723276561 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

a(n) == 1 (mod n).

Also, a(n) equals the size of the set { f(x) mod Phi_n(x) }, where f(x) runs over the polynomials of degree at most n-1 with nonnegative integer coefficients such that f(1)=n (i.e. the coefficients sum to n), Phi_n(x) is the n-th cyclotomic polynomial. In particular, for prime n, Phi_n(x)=1+x+...+x^(n-1) and thus all f(x) mod Phi_n(x) are distinct, implying that a(n)=binomial(2*n-1,n). - Max Alekseyev, Feb 20 2018

LINKS

Table of n, a(n) for n=1..20.

FORMULA

For prime p, a(p) = binomial(2*p-1,p). - Conjectured by Robert Israel, Feb 18 2018; proved by Max Alekseyev, Feb 20 2018

a(n) = A299807(n,n). - Max Alekseyev, Feb 25 2018

EXAMPLE

From M. F. Hasler, Feb 18 2018: (Start)

For n=2, the n-th roots of unity are U[2] = {-1, 1}, and taking x, y in this set, we can get x + y = -2, 0 or 2.

For n=3, the n-th roots of unity are U[3] = {1, w, w^2} where w = exp(2i*Pi/3) = -1/2 + i sqrt(3)/2, and taking x, y, z in this set, we can get x + y + z to be any of the 10 distinct values { 3, 2 + w, 2 + w^2, 1 + 2w, 1 + 2w^2, 0, w - 1, w^2 - 1, 3w, 3w^2 }. (End)

MAPLE

nexti:= proc(i, N) local ip, j, k;

  ip:= i;

  for k from N to 1 by -1 while i[k]=N-1 do od;

  if k=0 then return NULL fi;

  ip[k]:= ip[k]+1;

  for j from k+1 to N do ip[j]:= ip[k] od;

  ip

end proc:

f:= proc(N) local S, i, P, z;

  S:= {}:

  i:= <(0$N)>:

  P:= numtheory:-cyclotomic(N, z);

  while i <> NULL do

    S:= S union {rem(add(z^i[k], k=1..N), P, z)};

    i:= nexti(i, N);

  od;

  nops(S);

end proc:

seq(f(N), N=1..10); # Robert Israel, Feb 18 2018

MATHEMATICA

a[n_] := (t = Table[Exp[2 k Pi I/n], {k, 0, n - 1}]; b[0] = 1; iter = Table[{b[j], b[j - 1], n}, {j, 1, n}]; msets = Table[Array[b, n], Evaluate[Sequence @@ iter]]; tot = Total /@ (t[[#]] & /@ Flatten[msets, n - 1]) // N; u = Union[tot, SameTest -> (Chop[Abs[#1 - #2]] == 0 &)]; u // Length); Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 1, 10}] (* Jean-Fran├žois Alcover, Feb 19 2018 *)

PROG

(PARI) a(n, U=vector(n, k, bestappr(exp(2*Pi/n*k*I), 5*2^n)), S=[])={forvec(i=vector(n, k, [1, n]), S=setunion(S, [vecsum(vecextract(U, i))]); #S} \\ Not very efficient for n > 8. - M. F. Hasler, Feb 18 2018

CROSSREFS

Cf. A103314, A107754, A107861, A108380, A107848, A107753, A108381.

Sequence in context: A098702 A100001 A227937 * A190529 A212967 A301410

Adjacent sequences:  A299751 A299752 A299753 * A299755 A299756 A299757

KEYWORD

nonn

AUTHOR

David W. Wilson, Feb 18 2018

EXTENSIONS

a(1) through a(11) from Robert Israel, Feb 18 2018

a(12)-a(13) from Chai Wah Wu, Feb 20 2018

a(14)-a(20) from Max Alekseyev, Feb 22 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 22:34 EDT 2019. Contains 328335 sequences. (Running on oeis4.)