A382171 a(0) = 0; for n >= 1, one quarter of the number of points on the elliptic curve y^2 = x^3 - x defined over GF(3^n).

0, 1, 4, 7, 16, 61, 196, 547, 1600, 4921, 14884, 44287, 132496, 398581, 1196836, 3587227, 10758400, 32285041, 96864964, 290565367, 871666576, 2615088301, 7845353476, 23535794707, 70607118400, 211822152361, 635467254244, 1906399371247, 5719195722256, 17157594341221, 51472790198116

Offset

0,3

Comments

A divisibility sequence by construction: a(n) divides a(m) if n divides m.

Links

Jianing Song, Table of n, a(n) for n = 0..1000

Wikipedia, Elliptic curves over finite fields

Index entries for linear recurrences with constant coefficients, signature (4,-6,12,-9).

Formula

a(n) = (3^n + 1 - (sqrt(3)*i)^n - (-sqrt(3)*i)^n)/4, i = sqrt(-1).

G.f.: (1/(1-3*x) + 1/(1-x) - 2/(1+3*x^2))/4.

E.g.f.: (exp(3*x) + exp(x) - 2*cos(sqrt(3)*x))/4.

Example

For n = 1, the points on y^2 = x^3 - x in GF(3) are the point of infinity, (-1,0), (0,0), and (1,0), so a(1) = 4/4 = 1. This implies that the number of points in GF(3^n) is 3^n + 1 - alpha^n - beta^n, where alpha + beta = 3+1-4 = 0 and alpha*beta = 3.

Mathematica

A382171[n_] := (If[OddQ[n], 3^n + 1, ((-3)^(n/2) - 1)^2])/4; Array[A382171, 30, 0] (* or *)
LinearRecurrence[{4, -6, 12, -9}, {0, 1, 4, 7}, 30] (* Paolo Xausa, Jan 22 2026 *)

Prog

(PARI) a(n) = if(n%2, 3^n+1, ((-3)^(n/2)-1)^2)/4

Crossrefs

Cf. A382170 (in GF(5^n)).

Sequence in context: A340600 A013625 A182929 * A361733 A367744 A363642

Adjacent sequences: A382168 A382169 A382170 * A382172 A382173 A382174

Keyword

nonn,easy

Author

Jianing Song, Mar 17 2025

Status

approved