A087508 Number of k such that mod(k*n,3) = 1 for 0 <= k <= n.

0, 1, 1, 0, 2, 2, 0, 3, 3, 0, 4, 4, 0, 5, 5, 0, 6, 6, 0, 7, 7, 0, 8, 8, 0, 9, 9, 0, 10, 10, 0, 11, 11, 0, 12, 12, 0, 13, 13, 0, 14, 14, 0, 15, 15, 0, 16, 16, 0, 17, 17, 0, 18, 18, 0, 19, 19, 0, 20, 20, 0, 21, 21, 0, 22, 22, 0, 23, 23, 0, 24, 24, 0, 25, 25, 0, 26, 26, 0, 27, 27, 0, 28, 28, 0

Offset: 0

Author

Paul Barry, Sep 11 2003

Keywords

• easy
• nonn

Examples

			a(4) = 2 because k=1 and k=4 satisfy the equation.
		

Links

• G. C. Greubel, Table of n, a(n) for n = 0..10000
• Index entries for linear recurrences with constant coefficients, signature (0,0,2,0,0,-1).

Crossrefs

Cf. A000027, A087507, A087509.

Programs

Magma

I:=[0,1,1,0,2,2]; [n le 6 select I[n] else 2*Self(n-3) - Self(n-6): n in [1..100]]; // Vincenzo Librandi, Sep 22 2015

Mathematica

LinearRecurrence[{0,0,2,0,0,-1}, {0,1,1,0,2,2}, 100] (* Vincenzo Librandi, Sep 22 2015 *)
Table[PadRight[{0},3,n],{n,30}]//Flatten (* Harvey P. Dale, Jan 27 2021 *)

PARI

concat(0,Vec((1+x)/(1-x^3)^2 +O(x^99))) \\ Charles R Greathouse IV, Oct 24 2014

PARI

a(n) = sum(k=0, n, Mod(k*n, 3)==1); \\ Michel Marcus, Sep 27 2017

SageMath

@CachedFunction
def A087508(n):
    if (n<6): return (0,1,1,0,2,2)[n]
    else: return 2*A087508(n-3) - A087508(n-6)
[A087508(n) for n in (0..100)] # G. C. Greubel, Sep 02 2022

Formula

a(n) = A000027(n) - A087509(n) - A087507(n).

a(n) = (2/3)*(floor(n/3)+1)*(1-cos(2*Pi*n/3)).

G.f.: x*(1 + x)/(1 - x^3)^2. - Arkadiusz Wesolowski, May 28 2013

a(n) = sin(n*Pi/3)*((4n+6)*sin(n*Pi/3)-sqrt(3)*cos(n*Pi))/9. - Wesley Ivan Hurt, Sep 24 2017