cp's OEIS Frontend

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

%I A290731 #23 Oct 08 2024 21:50:55
%S A290731 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,
%T A290731 16,12,9,12,8,19,10,14,12,21,8,22,12,12,12,24,16,22,11,18,14,27,11,18,
%U A290731 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
%N A290731 Number of distinct values of X*(X+1) mod n.
%C A290731 Also the number of distinct values of X^2+X+1 mod n. - _N. J. A. Sloane_, Oct 05 2024
%H A290731 Andrew Howroyd, <a href="/A290731/b290731.txt">Table of n, a(n) for n = 1..10000</a>
%H A290731 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 5.
%F A290731 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
%e A290731 The values taken by X^2+X mod n for small n are:
%e A290731 1, [0]
%e A290731 2, [0]
%e A290731 3, [0, 2]
%e A290731 4, [0, 2]
%e A290731 5, [0, 1, 2]
%e A290731 6, [0, 2]
%e A290731 7, [0, 2, 5, 6]
%e A290731 8, [0, 2, 4, 6]
%e A290731 9, [0, 2, 3, 6]
%e A290731 10, [0, 2, 6]
%e A290731 11, [0, 1, 2, 6, 8, 9]
%e A290731 12, [0, 2, 6, 8]
%e A290731 ...
%p A290731 a:=[]; M:=80;
%p A290731 for n from 1 to M do
%p A290731 q1:={};
%p A290731 for i from 0 to n-1 do q1:={op(q1), (i^2+i) mod n}; od;
%p A290731 s1:=sort(convert(q1,list));
%p A290731 a:=[op(a),nops(s1)];
%p A290731 od:
%p A290731 a;
%t A290731 a[n_] := Product[{p, e} = pe; If[p==2, 2^(e-1), 1+Quotient[p^(e+1), (2p+2)]], {pe, FactorInteger[n]}];
%t A290731 Array[a, 100] (* _Jean-François Alcover_, Aug 05 2018, after _Andrew Howroyd_ *)
%o A290731 (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
%o A290731 (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
%o A290731 (Python)
%o A290731 from math import prod
%o A290731 from sympy import factorint
%o A290731 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
%Y A290731 Cf. A000224 (analog for X^2), A290732.
%K A290731 nonn,mult
%O A290731 1,3
%A A290731 _N. J. A. Sloane_, Aug 10 2017