login
Number of solutions to x^2 - x + 1 == 0 (mod n).
35

%I #81 Oct 11 2022 07:41:00

%S 1,0,1,0,0,0,2,0,0,0,0,0,2,0,0,0,0,0,2,0,2,0,0,0,0,0,0,0,0,0,2,0,0,0,

%T 0,0,2,0,2,0,0,0,2,0,0,0,0,0,2,0,0,0,0,0,0,0,2,0,0,0,2,0,0,0,0,0,2,0,

%U 0,0,0,0,2,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,4,0,2,0,0,0,2,0,0,0,0,0,2,0,0

%N Number of solutions to x^2 - x + 1 == 0 (mod n).

%C Number of elliptic points of order 3 for Gamma_0(n).

%C Equivalently, number of fixed points of Gamma_0(n) of type rho.

%C Values are 0 or a power of 2.

%C Shadow transform of central polygonal numbers A002061. - _Michel Marcus_, Jun 06 2013

%C Empirical: a(n) == A001615(n) (mod 3) for all natural numbers n. - _John M. Campbell_, Apr 01 2018

%C From _Jianing Song_, Jul 03 2018: (Start)

%C The comment above is true. Since both a(n) and A001615(n) are multiplicative we just have to verify that for prime powers. Note that A001615(p^e) = (p+1)*p^(e-1). For p == 1 (mod 3), p+1 == 2 (mod 3) so (p+1)*p^(e-1) == 2 (mod 3); for p == 2 (mod 3), p+1 is a multiple of 3 so (p+1)*p^(e-1) == 0 (mod 3). For p = 3, if e = 1 then p+1 == 1 (mod 3); if e > 1 then (p+1)*p^(e-1) == 0 (mod 3).

%C Equivalently, number of solutions to x^2 + x + 1 == 0 (mod n). (End)

%D Bruno Schoeneberg, Elliptic Modular Functions, Springer-Verlag, NY, 1974, p. 101.

%D Goro Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (3).

%H Christian G. Bower, <a href="/A000086/b000086.txt">Table of n, a(n) for n = 1..2000</a>

%H Harriet Fell, Morris Newman, and Edward Ordman, <a href="http://archive.org/details/jresv67Bn1p61">Tables of genera of groups of linear fractional transformations</a>, J. Res. Nat. Bur. Standards Sect. B 67B (1963), 61-68.

%H Lorenz Halbeisen and Norbert Hungerbuehler, <a href="https://www.semanticscholar.org/paper/Number-theoretic-aspects-of-a-combinatorial-Halbeisen-Hungerb%C3%BChler/5743ff2f9c14d22d1a9e570d6951a7c9ef79a612">Number theoretic aspects of a combinatorial function</a>, Notes on Number Theory and Discrete Mathematics 5(4) (1999), 138-150; see Definition 7 for the shadow transform.

%H John S. Rutherford, <a href="http://dx.doi.org/10.1107/S010876730804333X">Sublattice enumeration. IV. Equivalence classes of plane sublattices by parent Patterson symmetry and colour lattice group type</a>, Acta Cryst. A65 (2009), 156-163. [See Table 4.]

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>.

%F Multiplicative with a(p^e) = 1 if p = 3 and e = 1; 0 if p = 3 and e > 1; 2 if p == 1 (mod 3); 0 if p == 2 (mod 3). - _David W. Wilson_, Aug 01 2001

%F a(A226946(n)) = 0; a(A034017(n)) > 0. - _Reinhard Zumkeller_, Jun 23 2013

%F a(2*n) = a(3*n + 2) = a(9*n) = a(9*n + 6) = 0. - _Michael Somos_, Aug 14 2015

%F Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 2*sqrt(3)/(3*Pi) = 0.367552... (A165952). - _Amiram Eldar_, Oct 11 2022

%e G.f. = x + x^3 + 2*x^7 + 2*x^13 + 2*x^19 + 2*x^21 + 2*x^31 + 2*x^37 + 2*x^39 + ...

%p with(numtheory); A000086 := proc (n) local d, s; if modp(n,9) = 0 then RETURN(0) fi; s := 1; for d in divisors(n) do if isprime(d) then s := s*(1+eval(legendre(-3,d))) fi od; s end: # _Gene Ward Smith_, May 22 2006

%t Array[ Function[ n, If[ EvenQ[ n ] || Mod[ n, 9 ]==0, 0, Count[ Array[ Mod[ #^2-#+1, n ]&, n, 0 ], 0 ] ] ], 84 ]

%t a[ n_] := If[ n < 1, 0, Length[ Select[ (#^2 - # + 1)/n & /@ Range[n], IntegerQ]]]; (* _Michael Somos_, Aug 14 2015 *)

%t a[n_] := a[n] = Product[{p, e} = pe; Which[p==1 || p==3 && e==1, 1, p==3 && e>1, 0, Mod[p, 3]==1, 2, Mod[p, 3]==2, 0, True, a[p^e]], {pe, FactorInteger[n]}]; Array[a, 105] (* _Jean-François Alcover_, Oct 18 2018 *)

%o (PARI) {a(n) = if( n<1, 0, sum( x=0, n-1, (x^2 - x + 1)%n==0))}; \\ Nov 15 2002

%o (PARI) {a(n) = if( n<1, 0, direuler( p=2, n, if( p==3, 1 + X, if( p%3==2, 1, (1 + X) / (1 - X)))) [n])}; \\ Nov 15 2002

%o (Haskell)

%o a000086 n = if n `mod` 9 == 0 then 0

%o else product $ map ((* 2) . a079978 . (+ 2)) $ a027748_row $ a038502 n

%o -- _Reinhard Zumkeller_, Jun 23 2013

%Y Cf. A000089, A000091, A001616, A014683.

%Y Cf. A027748, A079978, A038502, A007949, A165952.

%Y Cf. A341422 (without zeros).

%K nonn,easy,nice,mult

%O 1,7

%A _N. J. A. Sloane_