login
A290731
Number of distinct values of X*(X+1) mod n.
12
1, 1, 2, 2, 3, 2, 4, 4, 4, 3, 6, 4, 7, 4, 6, 8, 9, 4, 10, 6, 8, 6, 12, 8, 11, 7, 11, 8, 15, 6, 16, 16, 12, 9, 12, 8, 19, 10, 14, 12, 21, 8, 22, 12, 12, 12, 24, 16, 22, 11, 18, 14, 27, 11, 18, 16, 20, 15, 30, 12, 31, 16, 16, 32, 21, 12, 34, 18, 24, 12, 36, 16, 37, 19, 22, 20, 24, 14, 40, 24
OFFSET
1,3
COMMENTS
Also the number of distinct values of X^2+X+1 mod n. - N. J. A. Sloane, Oct 05 2024
LINKS
Andreas Enge, William Hart, Fredrik Johansson, Short addition sequences for theta functions, arXiv:1608.06810 [math.NT], (24-August-2016). See Table 5.
FORMULA
Multiplicative with a(2^e) = 2^(e-1), a(p^2) = 1 + floor(p^(e+1)/(2*p+2)) for odd prime p. - Andrew Howroyd, Aug 01 2018
EXAMPLE
The values taken by X^2+X mod n for small n are:
1, [0]
2, [0]
3, [0, 2]
4, [0, 2]
5, [0, 1, 2]
6, [0, 2]
7, [0, 2, 5, 6]
8, [0, 2, 4, 6]
9, [0, 2, 3, 6]
10, [0, 2, 6]
11, [0, 1, 2, 6, 8, 9]
12, [0, 2, 6, 8]
...
MAPLE
a:=[]; M:=80;
for n from 1 to M do
q1:={};
for i from 0 to n-1 do q1:={op(q1), (i^2+i) mod n}; od;
s1:=sort(convert(q1, list));
a:=[op(a), nops(s1)];
od:
a;
MATHEMATICA
a[n_] := Product[{p, e} = pe; If[p==2, 2^(e-1), 1+Quotient[p^(e+1), (2p+2)]], {pe, FactorInteger[n]}];
Array[a, 100] (* Jean-François Alcover, Aug 05 2018, after Andrew Howroyd *)
PROG
(PARI) a(n)={my(v=vector(n)); for(i=0, n-1, v[i*(i+1)%n + 1]=1); vecsum(v)} \\ Andrew Howroyd, Aug 01 2018
(PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my([p, e]=f[i, ]); if(p==2, 2^(e-1), 1 + p^(e+1)\(2*p+2)))} \\ Andrew Howroyd, Aug 01 2018
(Python)
from math import prod
from sympy import factorint
def A290731(n): return prod((p**(e+1)//(p+(q:=p>2))>>1)+q for p, e in factorint(n).items()) # Chai Wah Wu, Oct 07 2024
CROSSREFS
Cf. A000224 (analog for X^2), A290732.
Sequence in context: A066589 A007897 A180783 * A106289 A332436 A165418
KEYWORD
nonn,mult
AUTHOR
N. J. A. Sloane, Aug 10 2017
STATUS
approved