A290732 - OEIS

%I #33 Nov 03 2018 19:45:34

%S 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,

%T 15,18,16,32,18,18,12,36,19,20,21,24,21,24,22,24,27,24,24,48,22,22,27,

%U 28,27,54,18,32,30,30,30,36

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

%H Andrew Howroyd, <a href="/A290732/b290732.txt">Table of n, a(n) for n = 1..10000</a>

%H Andreas Enge, William Hart, Fredrik Johansson, <a href="http://arxiv.org/abs/1608.06810">Short addition sequences for theta functions</a>, arXiv:1608.06810 [math.NT], (24-August-2016). See Table 6.

%F a(3^n) = 3^n. - _Hugo Pfoertner_, Aug 25 2018

%F a(n) = A317623(n) * A040001(n). - _Andrew Howroyd_, Oct 27 2018

%F 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

%e The values taken by (3*X^2-X)/2 mod n for small n are:

%e    1, [0]

%e    2, [0, 1]

%e    3, [0, 1, 2]

%e    4, [0, 1, 2, 3]

%e    5, [0, 1, 2]

%e    6, [0, 1, 2, 3, 4, 5]

%e    7, [0, 1, 2, 5]

%e    8, [0, 1, 2, 3, 4, 5, 6, 7]

%e    9, [0, 1, 2, 3, 4, 5, 6, 7, 8]

%e   10, [0, 1, 2, 5, 6, 7]

%e   11, [0, 1, 2, 4, 5, 7]

%e   12, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

%e   ...

%p a:=[]; M:=80;

%p for n from 1 to M do

%p q1:={};

%p for i from 0 to 2*n-1 do q1:={op(q1), i*(3*i-1)/2 mod n}; od;

%p s1:=sort(convert(q1,list));

%p a:=[op(a),nops(s1)];

%p od:

%p a;

%t a[n_] := Table[PolynomialMod[X(3X-1)/2, n], {X, 0, 2*n-1}]// Union // Length;

%t Array[a, 60] (* _Jean-François Alcover_, Sep 01 2018 *)

%o (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

%o (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

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

%K nonn,mult

%O 1,2

%A _N. J. A. Sloane_, Aug 10 2017

%E Even terms corrected by _Andrew Howroyd_, Nov 03 2018