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
Examples
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] ...
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.
Programs
-
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 *) -
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
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
Comments