View unanswered posts | View active topics It is currently Fri Nov 21, 2014 4:22 pm



← Back to the Calcudoku puzzle page




Reply to topic  [ 7 posts ] 
 Full tables: "mod function" and "bitwise OR" (in the 8x8's) 
Author Message

Posted on: Fri Oct 14, 2011 10:55 pm




Posts: 585
Joined: Fri May 13, 2011 4:51 pm
Post Full tables: "mod function" and "bitwise OR" (in the 8x8's)
Full tables: “mod function” and “bitwise OR” (in the 8x8’s).

Image

(this easy illustration has a unique solution)

Here is the full table for the “mod function” (the number of combinations for each case is shown in parenthesis). The “mod” function, xmod, works dividing the two numbers inside the cage, considering any of them as the dividend and the other as the divisor, thus obtaining a quotient and a remainder x, this remainder is considered the result of the operation, for instance, in 5 / 7, the quotient is 0, the remainder is 5, so the pair 57 is a valid solution for a 5mod (among others); but considering 7 / 5 (the “natural” division), the quotient is 1, and the remainder is 2, so the pair 57 is a valid solution for 2mod (among others).

Mod:

Here is the full table:

7mod: 78 (1 combination)
6mod: 67 68 (2)
5mod: 56 57 58 (3)
4mod: 45 46 47 48 (4)
3mod: 34 35 36 37 38 and additionally 85 74 (7)
2mod: 23 24 25 26 27 28 and 86 83 75 64 53 (11)
1mod: 12 13 14 15 16 17 18 and 87 76 73 72 65 54 52 43 32 (16)
0mod: 12 13 14 15 16 17 18 and 84 82 63 62 42 (12).
Total of possible combinations: 56.

The main tips are:
1) A number x can never be inside a cage ymod if x < y, for instance, 2 can never go inside a cage 3mod, 4mod, 5mod, 6mod or 7mod.
2) In a cage 0mod or 1mod "any" number (from 1 to 8) can initially be present.
3) In cages 4mod, 5mod, 6mod and 7mod, the 4, 5, 6 and 7, respectively, must be present; the cages 1mod, 2mod and 3mod are possible without the respective 1, 2 or 3. The cage 0mod has pairs that are multiples or a 1 is inside, what in fact is a particular case of the multiples.
There are a few combinations (if you forget any when solving, the full puzzle may collapse) but less than in the "bitwise OR".

Some comments:

The total number of possible combinations, 56, is twice the total number of combinations (below) for the “bitwise OR”, 28, in the case of 2 cells (in an 8x8 “bitwise OR” from 1 to 8, the actual type of puzzle) but, in general, considering that in the “bitwise OR” puzzles the 3 cells L-shape cages and the 3 cells in-line cages may be present, the total number of combinations for the “bitwise OR” is much greater, 193. Actually the mod function is not using 3 cells cages, and 4 cells cages are not being used in the bitwise OR.

Bitwise OR:

Below is the full table and a few tips for the “bitwise OR” (at the end of the post there is a little appendix explaining how this operation works). In the actual 8x8 puzzles we are using numbers 1 thru 8, so 1|, 2|, 4| and 8| in 2 cells or 3 cells cages are non-valid results; the 9|, 10| and 12| are possible in 2 cells cages and in 3 cells L-shape cages, but impossible in 3-cells “in-line” cages, as shown in the table [another curious thing is that, if we had a puzzle 8x8 with numbers in the range 0-7, we could have cages 1| (0 and 1), 2| (0 and 2), 4| (0 and 4) with 2 cells and 3 cells L-shape cages with 1| (001 or 110), 2| (002 or 220) and 4| (004 or 440)].

The 7| in 3 cells L-shape cages is the more complex (and, by the way, a very common cage) and may contain 56 different combinations (unless mistakes, corrections welcome) (the 7| in 3 cells in-line cages has also the maximum number of combinations, 29, in this group).

Here is the full table for the “bitwise OR”:

2 cells:

3| 12 13 23 (3)
5| 14 15 45 (3)
6| 24 26 46 (3)
7| 17 27 37 47 57 67 16 25 34 35 36 56 (12)
9| 18 (1)
10| 28 (1)
11| 38 (1)
12| 48 (1)
13| 58 (1)
14| 68 (1)
15| 78 (1)
Total of combinations: 28

3 cells L-shape:

3| 112 113 122 123 133 223 233 (7)
5| 114 115 144 145 155 445 455 (7)
6| 224 226 244 246 266 446 466 (7)
7| (56 combinations):

……7-1-7 7-2-7 7-3-7 7-4-7 7-5-7 7-6-7
……7-1-6 7-2-6 7-3-6 7-4-6 7-5-6 7-6-6
……7-1-5 7-2-5 7-3-5 7-4-5 7-5-5
……7-1-4 7-2-4 7-3-4 7-4-4
……7-1-3 7-2-3 7-3-3
……7-1-2 7-2-2
……7-1-1

……6-1-6 6-3-6 6-5-6
……6-1-5 6-3-5 6-5-5
……6-1-4 6-3-4 6-5-4
……6-1-3 6-3-3 6-5-2
……6-1-2 6-3-2
……6-1-1

……5-2-5 5-3-5
……5-2-4 5-3-4
……5-2-3 5-3-3
……5-2-2 5-3-1
……5-2-1

……4-2-1

……4-3-4
……4-3-3
……4-3-2
……4-3-1

9| 118 188 (2)
10| 228 288 (2)
11| 338 388 128 138 238 (5)
12| 448 488 (2)
13| 558 588 148 158 458 (5)
14| 668 688 248 268 468 (5)
15| 778 788 178 278 378 478 578
..……678 168 258 348 358 368 568 (14)
Total of combinations: 112

3 cells in line:

3| 123 (1)
5| 145 (1)
6| 246 (1)
7| 127 137 147 157 167 237 247 257
……267 347 357 367 457 467 567
..…124 125 126 134 135 136 146
..…234 235 236 245 256 345 346 (29)
9| Non-valid
10| Non-valid
11| 128 138 238 (3)
12| Non-valid
13| 148 158 458 (3)
14| 248 268 468 (3)
15| 178 278 378 478 578 678
..……168 258 348 358 368 568 (12)
Total of combinations: 53

Total bitwise OR (the three groups): 193

Some comments:

We have seen, for instance, that for a 3 cells L-shape cage with “7|” (in an 8x8 puzzle from 1 to 8), let’s say in cells a1-a2-b1, knowing that the operand 8 can not be in, the whole set of combinations is obtained with the 4-2-1 and all of the type 7-x-y, 6-1-x, 6-3-x, 6-5-x, 5-2-x, 5-3-x and 4-3-x (where x and/or y take all values ranging from 1 to 7; of course no operand can be present more than twice in any combination, placing in this case the duplicated operand in the opposite corner of the triangle). This number of solutions (combinations, supressing the redundant) is really big (56) (the “possibilities” increase if we take into account that any of these combinations may be permuted or “rotated”), it must be said that in cases like this it is not necessary to analyze all combinations, of course, only to clearly know how the operator works, the “|” in a cage modifies our conventional thinking, being relevant the binary expression of the “numbers” 1 to 8 and having no meaning its “value”.

Some tips:

1) There are many combinations that produce the “7|” without the number 7 inside the cage.

2) “6|” (2 cells) is only made with 2-4, 2-6 and 4-6.

3) “5|” (2cells) is only possible with 1-4, 1-5 and 4-5.

4) ”3|” (2 cells) is only made with 1-2, 1-3 and 2-3.

5) “n|“, with n higher that 8, contains the 8, being the operands the numbers 8 and n-8 if the cage is of 2 cells.

6) m can not be inside a cage “n|” if m > n, for instance, 8 in cages “7|”, “6|”, “5|” or “3|”, 7 in cages “6|”, “5|” or “3|”, 6 in cages “5|” or “3|”, and 5 in cages “3|”.

7) 1|, 2|, 4| and 8| will never appear in a cage (in 8x8’s from 1 to 8).

Appendix:

In the decimal system, a number, i.e, 7593, is a convention in which the “position” of a digit determines its “value”, 5 represents 500. So:

7593 = 7 x (10 ^ 3) + 5 x (10 ^ 2) + 9 x (10 ^ 1) + 3 x (10 ^ 0); 10 ^ 0 = 1, so this expression is usually simplified writing the last monomial as only 3; 7593 = 7000 + 500 + 90 +3. In this system, with base 10 (the base of the successive powers), we have 10 different symbols or digits, from 0 to 9 (the coefficients of the polynomial).

In the binary system, the “base” is 2, and there are only two symbols or digits, 0 and 1 (the language of the computers). Now a number like this:

1101 = 1 x (2 ^ 3) + 1 x (2 ^ 2) + 0 x (2 ^ 1) + 1 x (2 ^ 0) = 1 x 8 + 1 x 4 + 0 x 2 + 1 (since 2 ^ 0 = 1) = 8 + 4 + 0 + 1 = 13 (is equivalent to 13 in our decimal system).

Inversely, to obtain the binary expression of any “decimal” number, for instance, 13, we divide it by 2, with a quotient of 6 and a remainder of 1; later we divide that quotient 6 again by 2, with a new quotient of 3 and a remainder of 0, and the 3 again by 2, with a quotient of 1 and a remainder of 1. Now taking this last quotient and all the remainders in inverse sequence we obtain the binary representation for 13, which is 1101. Here are the numbers 1 thru 15 represented in binary:

1………0001
2………0010
3………0011
4………0100
5………0101
6………0110
7………0111
8.......1000
9.......1001
10…….1010
11…….1011
12…….1100
13…….1101
14…….1110
15…….1111.

Now, the bitwise OR operation is performed bit by bit (for each position) with the binary expression of the two operands, with the only rule that 0 and 0 give a 0, while 0 and 1, 1 and 0 and 1 and 1 all produce a 1. Two examples:

3……0011
6……0110
--------------
……..0111 = 7. Then a 3 and a 6 “bitwise ORed” give a 7.

5……0101
7……0111
--------------
..……0111 = 7. Here we see that a 5 and a 7 “bitwise ORed” reproduce the 7.

Clearly, the operands are commutable, that is, if N1 and N2 are binary numbers, N1 bitwise OR N2 = N2 bitwise OR N1.

Finally, if we have, i.e., 13|, this means that two numbers must produce 1101 but the higher number in an 8x8 puzzle is 8 (= 1000), so the 8 must be present, being the 5 the other number (it must be lower than 8) because 5 = 0101, to fill the necessary one’s since the 8 has all zeros in the bit positions 1, 2 and 3.

The bitwise OR with three or more numbers follows the same rules, for instance:

6……0110
3……0011
4……0100
--------------
......0111 = 7. That is, 6, 3 and 4 "bitwise ORed" result in a 7 (7|).

4……0100
5……0101
8……1000
--------------
……..1101 = 13. That is, 4, 5 and 8 "bitwise ORed" result in 13 (13|).

The operation is also associative, that is, if N1, N2 and N3 are binary numbers, N1 bitwise OR N2 bitwise OR N3 = (N1 bitwise OR N2) bitwise OR N3 = N1 bitwise OR (N2 bitwise OR N3).

Now we see why, i.e., the 4| does not exist since 4 = 0100 and it is not possible to find two different numbers to obtain that result, one of them should be the 4, 0100, and “any” other different would activate a bit in a position different than the third, so leaving a final result different than 4.


Last edited by clm on Sat Oct 15, 2011 5:56 am, edited 1 time in total.



Profile

Posted on: Sat Oct 15, 2011 5:33 am




Posts: 248
Location: Lisbon, Portugal
Joined: Sun Sep 18, 2011 3:40 pm
Post Re: Full tables: "mod function" and "bitwise OR" (in the 8x8
Interesting thread!
And useful to those who don't know to do the operations and don't have yet the tables.
And some particulars I hadn't notice.
Thanks, clm.

_________________
Visit http://www.calcudoku.org the most interesting and addictive site of puzzles.


Profile

Posted on: Mon Oct 17, 2011 2:02 pm




Posts: 585
Joined: Fri May 13, 2011 4:51 pm
Post Re: Full tables: "mod function" and "bitwise OR" (in the 8x8
jomapil wrote:
... And useful to those who don't know to do the operations and don't have yet the tables...Thanks, clm.


Welcome. The actual four special 8x8's puzzles ("mod function", "bitwise OR", "exponentiation" and "from 0") can be of different levels of difficulty, it is difficult to affirm that one is more difficult than the other (I am sure the difficulty can be adjusted by the program). Probably the "mod function" and the "bitwise OR" represent a bigger problem for most people because those are not very usual operations. When I joined the page, at the beginning, it was very useful for me to have a handy list of the combinations, so I prepared one. The "from 0" looks initially easier though the operations with the 0 are not "natural" and that's why some discussion took place in the past, in the Forum, with respect to multiplications and divisions (obviously, two or more 0's could be inside a cage "0x" but never two 0's can go inside a cage "0:" due to the well known "uncertainty"). I hope, then, that the tables may be useful.


Profile

Posted on: Fri Apr 13, 2012 12:14 am




Posts: 19
Joined: Fri May 13, 2011 9:45 am
Post Re: Full tables: "mod function" and "bitwise OR" (in the 8x8
what about 10x10 with mods?

what are the possibilities?
i have the possibilities from 0 till 8
but 9 and 10 aren't included


Profile

Posted on: Fri Apr 13, 2012 8:10 am




Posts: 36
Joined: Fri May 13, 2011 8:23 am
Post Re: Full tables: "mod function" and "bitwise OR" (in the 8x8
Image


Profile

Posted on: Fri Apr 13, 2012 12:25 pm




Posts: 585
Joined: Fri May 13, 2011 4:51 pm
Post Re: Full tables: "mod function" and "bitwise OR" (in the 8x8
veryevilking wrote:
what about 10x10 with mods?

what are the possibilities?
i have the possibilities from 0 till 8
but 9 and 10 aren't included


When the tables were made (six months ago and in fact until this moment) the main page was only showing the mod function in puzzles up to 8x8 (actually in an 8x8 and a 7x7 "manyop" every week). I understand that, for intance, in the books, they appear larger puzzles with the mod function, even in the 12x12 format.

Apart of the recent very handy table just provided by honkhonk, I'm sending in a separate post an Appendix to the original tables going now to 12x12 (the philosophy is the same).


Profile

Posted on: Fri Apr 13, 2012 12:33 pm




Posts: 585
Joined: Fri May 13, 2011 4:51 pm
Post Appendix 1: “mod function” full tables (up to 12x12’s).
Appendix 1: “mod function” full tables (up to 12x12’s).

Here is the full table for the “mod function” (the number of combinations for each case is shown in brackets). The “mod” function, xmod, works dividing the two numbers inside the cage, considering any of them as the dividend and the other as the divisor, thus obtaining a quotient and a remainder x, this remainder is considered the result of the operation, for instance, in 4 / 11, the quotient is 0, the remainder is 4, so the pair 4-11 is a valid solution for a 4mod (among others); but considering 11 / 4 (the “natural” division), the quotient is 2, and the remainder is 3, so the pair 4-11 is a valid solution for 3mod (among others).

Mod:

Here is the full table (mistakes reported welcome):

11mod: 11-12 (1 combination)
10mod: 10-11 10-12 (2)
9mod: 9-10 9-11 9-12 (3)
8mod: 89 8-10 8-11 8-12 (4)
7mod: 78 79 7-10 7-11 7-12 (5)
6mod: 67 68 69 6-10 6-11 6-12 (6)
5mod: 56 57 58 59 5-10 5-11 5-12 and additionally 12-7 11-6 (9)
4mod: 45 46 47 48 49 4-10 4-11 4-12 and 12-8 11-7 10-6 9-5 (12)
3mod: 34 35 36 37 38 39 3-10 3-11 3-12 and 12-9 11-8 11-4 10-7 96 85 74 (16)
2mod: 23 24 25 26 27 28 29 2-10 2-11 2-12 and 12-10 12-5 11-9 11-3 10-8 10-4 97 86 83 75 64 53 (22)
1mod: 12 13 14 15 16 17 18 19 1-10 1-11 1-12 and 12-11 11-10 11-5 10-9 10-3 98 94 92 87 76 73 72 65 54 52 43 32 (28)
0mod: 12 13 14 15 16 17 18 19 1-10 1-11 1-12 and 12-6 12-4 12-3 12-2 10-5 10-2 93 84 82 63 62 42 (23).
Total of possible combinations: 131.

The main tips are:
1) A number x can never be inside a cage ymod if x < y, for instance, 2 can never go inside a cage 3mod, 4mod, 5mod, 6mod, … .
2) In a cage 0mod or 1mod "any" number (from 1 to 12) can initially be present.
3) In cages 6mod, 7mod, 8mod, 9mod, 10mod and 11mod, the 6, 7, 8, 9, 10 and 11, respectively, must be present; the cages 1mod, 2mod, 3mod, 4mod and 5mod are possible without the respective 1, 2, 3, 4 or 5. The cage 0mod has pairs that are multiples or a 1 is inside, what in fact is a particular case of the multiples.


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 7 posts ] 

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.