A290731 Number of distinct values of X*(X+1) mod n.

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

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

Cf. A000224 (analog for X^2), A290732.

Sequence in context: A066589 A007897 A180783 * A106289 A332436 A165418

Adjacent sequences: A290728 A290729 A290730 * A290732 A290733 A290734

Keyword

nonn,mult

Author

N. J. A. Sloane, Aug 10 2017

Status

approved