login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000086 Number of solutions to x^2 - x + 1 == 0 (mod n). 30
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET
1,7
COMMENTS
Number of elliptic points of order 3 for Gamma_0(n).
Equivalently, number of fixed points of Gamma_0(n) of type rho.
Values are 0 or a power of 2.
Shadow transform of central polygonal numbers A002061. - Michel Marcus, Jun 06 2013
Empirical: a(n) == A001615(n) (mod 3) for all natural numbers n. - John M. Campbell, Apr 01 2018
From Jianing Song, Jul 03 2018: (Start)
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).
Equivalently, number of solutions to x^2 + x + 1 == 0 (mod n). (End)
REFERENCES
Bruno Schoeneberg, Elliptic Modular Functions, Springer-Verlag, NY, 1974, p. 101.
Goro Shimura, Introduction to the Arithmetic Theory of Automorphic Functions, Princeton, 1971, see p. 25, Eq. (3).
LINKS
Harriet Fell, Morris Newman, and Edward Ordman, Tables of genera of groups of linear fractional transformations, J. Res. Nat. Bur. Standards Sect. B 67B (1963), 61-68.
Lorenz Halbeisen and Norbert Hungerbuehler, Number theoretic aspects of a combinatorial function, Notes on Number Theory and Discrete Mathematics 5(4) (1999), 138-150; see Definition 7 for the shadow transform.
N. J. A. Sloane, Transforms.
FORMULA
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
a(A226946(n)) = 0; a(A034017(n)) > 0. - Reinhard Zumkeller, Jun 23 2013
a(2*n) = a(3*n + 2) = a(9*n) = a(9*n + 6) = 0. - Michael Somos, Aug 14 2015
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
EXAMPLE
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 + ...
MAPLE
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
MATHEMATICA
Array[ Function[ n, If[ EvenQ[ n ] || Mod[ n, 9 ]==0, 0, Count[ Array[ Mod[ #^2-#+1, n ]&, n, 0 ], 0 ] ] ], 84 ]
a[ n_] := If[ n < 1, 0, Length[ Select[ (#^2 - # + 1)/n & /@ Range[n], IntegerQ]]]; (* Michael Somos, Aug 14 2015 *)
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 *)
PROG
(PARI) {a(n) = if( n<1, 0, sum( x=0, n-1, (x^2 - x + 1)%n==0))}; \\ Nov 15 2002
(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
(Haskell)
a000086 n = if n `mod` 9 == 0 then 0
else product $ map ((* 2) . a079978 . (+ 2)) $ a027748_row $ a038502 n
-- Reinhard Zumkeller, Jun 23 2013
CROSSREFS
Cf. A341422 (without zeros).
Sequence in context: A349797 A055668 A045839 * A363858 A045838 A350139
KEYWORD
nonn,easy,nice,mult
AUTHOR
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 11:14 EDT 2024. Contains 371278 sequences. (Running on oeis4.)