A042968 Numbers not divisible by 4.

1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 18, 19, 21, 22, 23, 25, 26, 27, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 49, 50, 51, 53, 54, 55, 57, 58, 59, 61, 62, 63, 65, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 81, 82, 83, 85, 86, 87, 89, 90, 91, 93, 94, 95, 97, 98, 99, 101, 102

Offset: 1

Author

N. J. A. Sloane, Dec 11 1999

Keywords

• nonn
• easy

Comments

Equivalently, numbers whose square part is odd. Cf. A028982. - Peter Munn, Jul 14 2020

More generally the sequence of numbers not divisible by some fixed integer m >= 2 is given by a(n,m) = 1 + n + floor(n/(m-1)). - Benoit Cloitre, Jul 11 2009

Also a(n,m) = floor((m*n-1)/(m-1)) [with offset 1]. - Gary Detlefs, May 14 2011

Numbers not having more even than odd divisors: A048272(a(n)) >= 0. - Reinhard Zumkeller, Jan 21 2012

Extending the comments of Benoit Cloitre (Jul 11 2009) and Gary Detlefs (May 14 2011), the g.f. is A(m,x) = (1-x^m) / ((1-x^(m-1))*(1-x)^2) where m >= 2 is fixed. - Werner Schulte, Apr 26 2018

Examples

			G.f. = 1 + 2*x + 3*x^2 + 5*x^3 + 6*x^4 + 7*x^5 + 9*x^6 + 10*x^7 + 11*x^8 + ... - _Michael Somos_, Jun 17 2018
		

Links

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

Crossrefs

Cf. A001651, A001935, A028982, A070048, A042965, A064680.

Cf. A071619 (partial sums); A008586 (complement).

Numbers that are congruent to {k0,k1,k2} mod 4: A004772, A004773, A042965, a(n).

Programs

Haskell

a042968 = (`div` 3) . (subtract 1) . (* 4)
a042968_list = filter ((/= 0) . (`mod` 4)) [1..]
-- Reinhard Zumkeller, Sep 02 2012

Magma

[n+1+Floor(n/3): n in [0..80]]; // Vincenzo Librandi, Aug 03 2015

Maple

seq(n+floor((n-1)/3), n=1..80); # Muniru A Asiru, Feb 17 2019

Mathematica

Select[Table[n,{n,200}], Mod[#,4] != 0&] (* Vladimir Joseph Stephan Orlovsky, Feb 18 2011 *)
LinearRecurrence[{1,0,1,-1},{1,2,3,5},80]  (* or *) Drop[Range[110],{4,-1,4}] (* Harvey P. Dale, Jan 07 2023 *)

PARI

{a(n) = 1 + n + n\3};

Python

def A042968(n): return n+(n-1)//3 # Chai Wah Wu, Apr 13 2025

Sage

[1+n+floor(n/3) for n in (0..80)] # G. C. Greubel, Feb 17 2019

Formula

a(n) = a(n-1) + a(n-3) - a(n-4).

a(n) = a(n-3) + 4, with a(1) = 1.

G.f.: x * (1+x) * (1+x^2) / ( (1+x+x^2)*(1-x)^2 ). - Michael Somos, Jan 12 2000

A064680(A064680(a(n))) = a(n). - Reinhard Zumkeller, Oct 19 2001

Nearest integer to (Sum_{k>n} 1/k^4)/(Sum_{k>n} 1/k^5). - Benoit Cloitre, Jun 12 2003

a(n) = n + 1 + floor(n/3). - Benoit Cloitre, Jul 11 2009

a(n) = floor((4*n+3)/3). - Gary Detlefs, May 14 2011

A214546(a(n)) >= 0 for n > 0. - Reinhard Zumkeller, Jul 20 2012

a(n) = 2*n - ceiling(2*n/3) + 1. - Arkadiusz Wesolowski, Sep 21 2012

Sum_{k=0..n} a(n) = A071619(n+1). - L. Edson Jeffery, Jul 30 2014

The g.f. A(x) satisfies x*A(x)^2 = (B(x)/x)^2 + (B(x)/x), where B(x) is the o.g.f. of A042965. - Peter Bala, Apr 12 2017

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

Euler transform of length 4 sequence [2, 0, 1, -1]. - Michael Somos, Jun 17 2018

a(n) = -a(-1-n) for all n in Z. - Michael Somos, Jun 17 2018

E.g.f.: (2/3)*exp(x)*(1 + 2*x) + (1/9)*exp(-x/2)*(3*cos(sqrt(3)*x/2) + sqrt(3)*sin(sqrt(3)*x/2)). - Stefano Spezia, Nov 16 2019

a(n) = (12*n + 6 + w^(2*n)*(w + 2) - w^n*(w - 1))/9 where w = (-1 + sqrt(-3))/2. - Guenther Schrack, Jun 07 2021

Sum_{n>=1} (-1)^(n+1)/a(n) = (2*sqrt(2)-1)*Pi/8. - Amiram Eldar, Dec 05 2021

Extensions

Edited by Peter Munn, Nov 16 2019

I restored my original (1999) definition and offset, which in the intervening 21 years had been lost. - N. J. A. Sloane, Jun 12 2021