A290732 Number of distinct values of X*(3*X-1)/2 mod n.

1, 2, 3, 4, 3, 6, 4, 8, 9, 6, 6, 12, 7, 8, 9, 16, 9, 18, 10, 12, 12, 12, 12, 24, 11, 14, 27, 16, 15, 18, 16, 32, 18, 18, 12, 36, 19, 20, 21, 24, 21, 24, 22, 24, 27, 24, 24, 48, 22, 22, 27, 28, 27, 54, 18, 32, 30, 30, 30, 36

Offset

1,2

Links

Andrew Howroyd, Table of n, a(n) for n = 1..10000

Andreas Enge, William Hart, Fredrik Johansson, Short addition sequences for theta functions, arXiv:1608.06810 [math.NT], (24-August-2016). See Table 6.

Formula

a(3^n) = 3^n. - Hugo Pfoertner, Aug 25 2018

a(n) = A317623(n) * A040001(n). - Andrew Howroyd, Oct 27 2018

Multiplicative with a(2^e) = 2^e, a(3^e) = 3^e, a(p^e) = 1 + floor( p^(e+1)/(2*p+2) ) for prime p >= 5. - Andrew Howroyd, Nov 03 2018

Example

The values taken by (3*X^2-X)/2 mod n for small n are:
   1, [0]
   2, [0, 1]
   3, [0, 1, 2]
   4, [0, 1, 2, 3]
   5, [0, 1, 2]
   6, [0, 1, 2, 3, 4, 5]
   7, [0, 1, 2, 5]
   8, [0, 1, 2, 3, 4, 5, 6, 7]
   9, [0, 1, 2, 3, 4, 5, 6, 7, 8]
  10, [0, 1, 2, 5, 6, 7]
  11, [0, 1, 2, 4, 5, 7]
  12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
  ...

Maple

a:=[]; M:=80;
for n from 1 to M do
q1:={};
for i from 0 to 2*n-1 do q1:={op(q1), i*(3*i-1)/2 mod n}; od;
s1:=sort(convert(q1, list));
a:=[op(a), nops(s1)];
od:
a;

Mathematica

a[n_] := Table[PolynomialMod[X(3X-1)/2, n], {X, 0, 2*n-1}]// Union // Length;
Array[a, 60] (* Jean-François Alcover, Sep 01 2018 *)

Prog

(PARI) a(n)={my(v=vector(n)); for(i=0, 2*n-1, v[i*(3*i-1)/2%n + 1]=1); vecsum(v)} \\ Andrew Howroyd, Oct 27 2018
(PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my([p, e]=f[i, ]); if(p<=3, p^e, 1 + p^(e+1)\(2*p+2)))} \\ Andrew Howroyd, Nov 03 2018

Crossrefs

Cf. A000224 (analog for X^2), A014113, A290729, A290730, A290731, A317623.

Sequence in context: A138796 A186970 A064380 * A353201 A229110 A229949

Adjacent sequences: A290729 A290730 A290731 * A290733 A290734 A290735

Keyword

nonn,mult

Author

N. J. A. Sloane, Aug 10 2017

Extensions

Even terms corrected by Andrew Howroyd, Nov 03 2018

Status

approved