cp's OEIS Frontend

A042963 Numbers congruent to 1 or 2 mod 4.

%I A042963 #129 Feb 16 2025 08:32:38
%S A042963 1,2,5,6,9,10,13,14,17,18,21,22,25,26,29,30,33,34,37,38,41,42,45,46,
%T A042963 49,50,53,54,57,58,61,62,65,66,69,70,73,74,77,78,81,82,85,86,89,90,93,
%U A042963 94,97,98,101,102,105,106,109,110,113,114,117,118,121,122,125,126,129,130,133,134,137,138
%N A042963 Numbers congruent to 1 or 2 mod 4.
%C A042963 Complement of A014601. - _Reinhard Zumkeller_, Oct 04 2004
%C A042963 Let S(x) = (1, 2, 2, 2, ...). Then A042963 = ((S(x))^2 + S(x^2))/2 = ((1, 4, 8, 12, 16, 20, ...) + (1, 0, 2, 0, 2, 0, 2, ...))/2 = (1, 2, 5, 6, 9, 10, ...). - _Gary W. Adamson_, Jan 03 2011
%C A042963 (a(n)*(a(n) + 1 + 4*k))/2 is odd, for k >= 0. - _Gionata Neri_, Jul 19 2015
%C A042963 Equivalent to the following variation on Fermat's Diophantine m-tuple: 1 + the product of any two distinct terms is not a square; this sequence, which we'll call sequence S, is produced by the following algorithm. At the start, S is initially empty. At stage n, starting at n = 1, the algorithm checks whether there exists a number m already in the sequence, such that mn+1 is a perfect square. If such a number m is found, then n is not added to the sequence; otherwise, n is added. Then n is incremented to n + 1, and we repeat the procedure. Proof by Clark R. Lyons: We prove by strong induction that n is in the sequence S if and only if n == 1 (mod 4) or n == 2 (mod 4). Suppose now that this holds for all k < n. In case 1, either n == 1 (mod 4) or n == 2 (mod 4), and we wish to show that n does indeed enter the sequence S. That is, we wish to show that there does not exist m < n, already in the sequence at this point such that mn+1 is a square. By the inductive hypothesis m == 1 (mod 4) or m == 2 (mod 4). This means that both m and n are one of 1, 2, 5, or 6 mod 8. Using a multiplication table mod 8, we see that this implies mn+1 is congruent to one of 2, 3, 5, 6, or 7 mod 8. But we also see that mod 8, a perfect square is congruent to 0, 1, or 4. Thus mn+1 is not a perfect square, so n is added to the sequence. In case 2, n == 0 (mod 4) or n == 3 (mod 4), and we wish to show that n is not added to the sequence. That is, we wish to show that there exists m < n already in the sequence such that mn+1 is a perfect square. For this we let m = n - 2, which is positive since n >= 3. By the inductive hypothesis, since m == 1 (mod 4) or m == 2 (mod 4) and m < n, m is already in the sequence. And we have m*n + 1 = (n - 2)*n + 1 = n^2 - 2*n + 1 = (n - 1)^2, so mn+1 is indeed a perfect square, and so n is not added to the sequence. Thus n is added to the sequence if and only if n == 1 (mod 4) or n == 2 (mod 4). This completes the proof. - _Robert C. Lyons_, Jun 30 2016
%C A042963 Also the number of maximal cliques in the (n + 1) X (n + 1) black bishop graph. - _Eric W. Weisstein_, Dec 01 2017
%C A042963 Lexicographically earliest sequence of distinct positive integers such that the average of any two or more consecutive terms is never an integer. (For opposite property see A005408.) - _Ivan Neretin_, Dec 21 2017
%C A042963 Numbers whose binary reflected Gray code (A014550) ends with 1. - _Amiram Eldar_, May 17 2021
%C A042963 Also: append its negated last bit to n-1. - _M. F. Hasler_, Oct 17 2022
%H A042963 David Lovler, <a href="/A042963/b042963.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from Reinhard Zumkeller)
%H A042963 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/BlackBishopGraph.html">Black Bishop Graph</a>.
%H A042963 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/MaximalClique.html">Maximal Clique</a>.
%H A042963 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1).
%F A042963 a(n) = 1 + A042948(n-1). [Corrected by _Jianing Song_, Oct 06 2018]
%F A042963 From _Michael Somos_, Jan 12 2000: (Start)
%F A042963 G.f.: x*(1 + x + 2*x^2)/((1 - x)^2*(1 + x)).
%F A042963 a(n) = a(n-1) + 2 + (-1)^n, a(0) = 1. (End) [This uses offset 0. - _Jianing Song_, Oct 06 2018]
%F A042963 A014493(n) = A000217(a(n)). - _Reinhard Zumkeller_, Oct 04 2004, Feb 14 2012
%F A042963 a(n) = Sum_{k=0..n} (A001045(k) mod 4). - _Paul Barry_, Mar 12 2004
%F A042963 A145768(a(n)) is odd. - _Reinhard Zumkeller_, Jun 05 2012
%F A042963 a(n) = A005843(n-1) + A059841(n-1). - _Philippe Deléham_, Mar 31 2009 [Corrected by _Jianing Song_, Oct 06 2018]
%F A042963 a(n) = 4*n - a(n-1) - 5 for n > 1. [Corrected by _Jerzy R Borysowicz_, Jun 09 2023]
%F A042963 From _Ant King_, Nov 17 2010: (Start)
%F A042963 a(n) = a(n-1) + a(n-2) - a(n-3).
%F A042963 a(n) = (4*n - 3 - (-1)^n)/2. (End)
%F A042963 a(n) = (n mod 2) + 2*n - 2. - _Wesley Ivan Hurt_, Oct 10 2013
%F A042963 A163575(a(n)) = n - 1. - _Reinhard Zumkeller_, Jul 22 2014
%F A042963 E.g.f.: 2 + (2*x - 1)*sinh(x) + 2*(x - 1)*cosh(x). - _Ilya Gutkovskiy_, Jun 30 2016
%F A042963 E.g.f.: 2 + (2*x - 1)*exp(x) - cosh(x). - _David Lovler_, Jul 19 2022
%F A042963 Sum_{n>=1} (-1)^(n+1)/a(n) = Pi/8 + log(2)/4. - _Amiram Eldar_, Dec 05 2021
%p A042963 A046923:=n->(n mod 2) + 2n - 2; seq(A046923(n), n=1..100); # _Wesley Ivan Hurt_, Oct 10 2013
%t A042963 Select[Range[109], Or[Mod[#, 4] == 1, Mod[#, 4] == 2] &] (* _Ant King_, Nov 17 2010 *)
%t A042963 Table[(4 n - 3 - (-1)^n)/2, {n, 20}] (* _Eric W. Weisstein_, Dec 01 2017 *)
%t A042963 LinearRecurrence[{1, 1, -1}, {1, 2, 5}, 20] (* _Eric W. Weisstein_, Dec 01 2017 *)
%t A042963 CoefficientList[Series[(1 + x + 2 x^2)/((-1 + x)^2 (1 + x)), {x, 0, 20}], x] (* _Eric W. Weisstein_, Dec 01 2017 *)
%o A042963 (PARI) a(n)=2*n-1-(n-1)%2 \\ _Jianing Song_, Oct 06 2018; adapted to offset by _Michel Marcus_, Sep 09 2022
%o A042963 (PARI) apply( A042963(n)=n*2-2+n%2, [1..99]) \\ _M. F. Hasler_, Oct 17 2022
%o A042963 (Magma) [ n : n in [1..165] | n mod 4 eq 1 or n mod 4 eq 2 ]; // _Vincenzo Librandi_, Jan 25 2011
%o A042963 (Haskell)
%o A042963 a042963 n = a042963_list !! (n-1)
%o A042963 a042963_list = [x | x <- [0..], mod x 4 `elem` [1,2]]
%o A042963 -- _Reinhard Zumkeller_, Feb 14 2012
%Y A042963 Cf. A153284 (first differences), A014848 (partial sums).
%Y A042963 Cf. A014550, A046712 (subsequence).
%Y A042963 Union of A016813 and A016825.
%K A042963 nonn,easy
%O A042963 1,2
%A A042963 _N. J. A. Sloane_
%E A042963 Offset corrected by _Reinhard Zumkeller_, Feb 14 2012
%E A042963 More terms by _David Lovler_, Jul 19 2022