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
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 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
KEYWORD
nonn,mult
AUTHOR
N. J. A. Sloane, Aug 10 2017
STATUS
approved