# How to create a sublist of elements with a congruence relation

I generated a list made up of lists of four elements such as:

n = {{49, 9, 9, 5}, {57, 13, 9, 5}, {81, 21, 13, 5}, {95, 19, 19, 7},...}


I would like to create a sublist that only contains lists whose elements are all congruent to 1 mod 4. How can I do this?

You can write a very explicit and readable code by using Select and AllTrue

n = {{49, 9, 9, 5}, {57, 13, 9, 5}, {81, 21, 13, 5}, {95, 19,
19, 7}};

Select[n, AllTrue[Mod[#, 4] == 1 &]]

(* {{49, 9, 9, 5}, {57, 13, 9, 5}, {81, 21, 13, 5}} *)


but in my experience, casting the problem in term of Pick gives often the fastest code.

n = RandomInteger[100, {10^5, 4}];

sub1 = Select[n, AllTrue[Mod[#, 4] == 1 &]]; // RepeatedTiming
sub2 = DeleteCases[Pick[n, Mod[n, 4], {1, 1, 1, 1}], {}]; // RepeatedTiming

(* {0.15, Null} *)

(* {0.0700, Null} *)

sub1 === sub2

(*  True *)


Indeed, Pick is very fast. A bit faster is using some integer vector arithmetic to create a scalar condition for picking:

n = RandomInteger[100, {10^2, 5}];
sub1 = Select[n, AllTrue[Mod[#, 4] == 1 &]]; // RepeatedTiming // First
sub2 = DeleteCases[Pick[n, Mod[n, 4], {1, 1, 1, 1}], {}]; // RepeatedTiming // First

sub3 = Pick[n, Mod[n - 1, 4].ConstantArray[1, 4], 0]; // RepeatedTiming // First
sub1 == sub2 == sub3


0.132

0.045

0.0030

True

• True. If you have time, it's always better to simplify the pattern to a simple expression with no parts like True/False or 1/0. Commented May 7, 2018 at 8:11
• Note also that Pick[n, Mod[n, 4], {1, 1, 1, 1}] creates an unpacked array and that arrays with True and False cannot be packed. (Btw., I consider this a shortcoming of Mathematica) Commented May 7, 2018 at 9:13
• This is because there is no native bit data type. The best you can get is a byte image or a ByteArray but there's not much support for those yet outside their respective domain. Commented May 7, 2018 at 21:31
• That's what I meant... Commented May 7, 2018 at 21:42

Another way using pattern matching and replacement (probably slower than the other implementations):

n = {{49, 9, 9, 5}, {57, 13, 9, 5}, {81, 21, 13, 5}, {95, 19, 19, 7}};
n /. list_List?(! And @@ Thread[Mod[#, 4] == 1] &) -> Sequence[]
(*{{49, 9, 9, 5}, {57, 13, 9, 5}, {81, 21, 13, 5}}*)


Edit:

One could also use Nothing instead of Sequence[] to represent an element that will automatically be removed.