26

Re: QR-code

Hello, rg45, you wrote: R> I counted separately slices of central columns and separately square matrixes, well and  , here that triple of items and turned out. Clearly. Cool. I, when considered, did not think of the form "", IMHO it is possible to take any

27

Re: QR-code

Hello, Brice Tribbiani, you wrote: BT> For two 6 maximum. BT> 1. One corner black (3 more turn out its rotation) BT> 2. One side black (3 more turn out rotation) BT> 3. One diagonal black (one more turns out its rotation) BT> 4. One corner white (3 more turn out its rotation) BT> 5. All black. BT> 6. All white. Super! I would enumerate them hardly differently. 1 - 5 - + 1 But for 3 to leave number of black pixels only two pictures + - - + - + + - and 4 pictures to deliver in correspondence 6 ++ + - - + - - + - - + ++ And it is possible more?

28

Re: QR-code

Hello, Erop, you wrote: E> it is clear. Cool. I when considered did not think of the form "", IMHO it is possible any To me only now to take cunning, about what you asked in the root message. Well so same it is simple. It is necessary to count separately total of variants; then, an amount of variants with an axis of symmetry of the second order and to throw out from total half of this number; well and, at last, an amount of variants with an axis of symmetry of 4th order and to throw out from total three quarters of this number. With an axis of symmetry of the fourth order we already counted an amount of variants, it is necessary same  to count an amount of variants with an axis of 2nd order, well and to simplify, for . To consider laziness.

29

Re: QR-code

Hello, rg45, you wrote: R> me only now reached, about what you asked in the root message. Well so same it is simple. It is necessary to count separately total of variants; then, an amount of variants with an axis of symmetry of the second order and to throw out from total half of this number; well and, at last, an amount of variants with an axis of symmetry of 4th order and to throw out from total three quarters of this number. With an axis of symmetry of the fourth order we already counted an amount of variants, it is necessary same  to count an amount of variants with an axis of 2nd order, well and to simplify, for . To consider laziness. Still well to prove that it is impossible more. Well and well to check up that at least for N == 1 and N == 2 formula works

30

Re: QR-code

Hello, Erop, you wrote: E> And it is possible more? No. At me all rotational invariants, and in brackets - an amount of alternative combinations which are given by each of them are enumerated. Discarding from 16 theoretical 10, we receive 6. To receive it is more, we should encode orientation in one pixel that does not turn out. For 33 it is already more favourable to encode orientation.

31

Re: QR-code

Hello, Erop, you wrote: E> Still well to prove that it is impossible more. E> Well and well to check up that at least for N == 1 and N == 2 formula works You as though the first year on . Simply you invert presumptions and let the opponent proves the reverse

32

Re: QR-code

Hello, Brice Tribbiani, you wrote: BT> For 33 it is already more favourable to encode orientation. This very suspicious statement. You can justify it somehow? p. s. For orientation coding it is necessary, a minimum of 3 pixels?

33

Re: QR-code

Hello, Erop, you wrote: E> Hello, Brice Tribbiani, you wrote: BT>> For 33 it is already more favourable to encode orientation. E> this very suspicious statement. You can justify it somehow? Orientation is precisely encoded by three , that is we lose 8 variants, all remaining our bits. Perhaps it is possible and is cheaper, but I do not know as. In a square 33 I quickly counted 8 projections of invariants (one black corner, a corner and adjacent , the black side, here to you and 9). On idea, you take the formula which was deduced by you with rg45, and you compare to my of the first answer. Only something you for N=2 is not true, I do not know as for the big.

34

Re: QR-code

Hello, Erop, you wrote: E> Our QR-code of the size NxN is a small square from N x N pixels. Each pixel black or white. E> difficulty consists that when we scan the code, we do not know, what side turns a square. 4 variants (0, 90, 180 and 270 degrees) E> the Question are possible all? How many different unique numbers it is possible to encode such code so, what the read out number did not depend on square orientation. It is obvious that without the registration of turns it is possible to encode 2^n^2 numbers. After all it simply binary string of length n^2. And further, one of variants optimal (on the size) codings which is steady against turns, becomes elementarily: it is enough to take function which for any coloring and its turns will always return the same coloring, and then simply to enumerate all various results of application of this function to various 2^n^2 to a coloring. It is obvious that for a role of such function minimum function (or a maximum) approaches for example. In general, it already allows to make numerical experiment: n the unique codes 1 2 2 6 3 140 4 16456 5 8390720 6 17179934976 And to pick up the answer: the number of the unique codes = (2 ^ (n^2) + 2*2 ^ ((n^2 + 3 * (n mod 2))/4) + 2 ^ ((n^2 + (n mod 2))/2))/4 To put it briefly, at first sight is clear to any that it is sequence A047937 E> We develop the standard of a QR-code. I hope there is an understanding that coding in already existing QR is selected suboptimal at all that could not invent more dense, and that possibility to process a recognition error was necessary. Well that is in practice the knowledge of the maximum number of the possible codes appears it is not especially useful. Though it and an interesting mathematical problem

35

Re: QR-code

Hello, Brice Tribbiani, you wrote: BT> Orientation is precisely encoded by three , that is we lose 8 variants, all remaining our bits. Perhaps it is possible and is cheaper, but I do not know as. Well abruptly to prove, what it is impossible to eat Actually the obvious decision with two bits of an overhead projector (interesting, the term "waybills" would be clear?) Instead of three BT> in a square 33 I quickly counted 8 projections of invariants (one black corner, a corner and adjacent , the black side, here to you and 9). For the coding of 9 numbers it is enough to consider a prime number of black pixels But here look, from obvious, there are 4 angular pixels, 4 "side" and 1 center Number angular - 5 variants, number side - 5 variants, and central - 2 variants. It already 50 variants. It, of course, is less 2 ^ (9-3), but, it is possible to note that in both 4-kah pixels, it is possible to apply the same coding, as on a square 22 that already gives 72 variants... BT> On idea, you take the formula which was deduced by you with rg45, and you compare to my of the first answer. BT> only something you for N=2 is not true, I do not know as for the big. We deduced the formula of number of the pictures which are playing back at turn on 90. For N == 2 it gave 2 variants. Like true - all white and all black...

36

Re: QR-code

Hello, watchmaker, you wrote: W> And to pick up the answer: W> W> number of the unique codes = (2 ^ (n^2) + 2*2 ^ ((n^2 + 3 * (n mod 2))/4) + 2 ^ ((n^2 + (n mod 2))/2))/4 W> Super! Similar on truth, but the answer it is possible not to select, of course, and to receive analytically. W> well that is in practice the knowledge of the maximum number of the possible codes appears it is not especially useful. Though it and an interesting mathematical problem Well, so, an etude

37

Re: QR-code

Hello, Erop, you wrote: Pzz>> That did not depend, or that it was possible to recognize orientation and to recover the encoded? E> it is necessary to be able to distinguish one number from another, to recover orientation I am not necessary I understand how to encode (N^2 - 3) a bit. , like, (N^2 - 2). But how to beat off one more bit, somehow not , it is invented only, as the half-bit to beat off (i.e., (N^2 - 3) *3 variants)

38

Re: QR-code

Hello, Erop, you wrote: E> 1) At all is not present. It is possible to use more artful codings. E> well, say, it is possible to color always three salient points in white, and one in black, and a square to turn so, what a black corner on the right-above. Remaining pixels to renumber and we receive 2 ^ (N*N-4) numbers that for N = 10 it is strong more than your estimation... And one more bit can be encoded, if or one salient point white, and remaining black, or on the contrary, one black, the remaining white. And still a half-bit it is possible to encode, selecting between such variants of a coloring of salient points: *--* - ** - ** But how to beat off still the half-bit, I cannot invent

39

Re: QR-code

Hello, Erop, you wrote: E> Hello, Brice Tribbiani, you wrote: BT>> Orientation is precisely encoded by three , that is we lose 8 variants, all remaining our bits. Perhaps it is possible and is cheaper, but I do not know as. E> Well abruptly to prove, what it is impossible E> Actually there is an obvious decision with two bits of an overhead projector (interesting, the term "waybills" would be clear?) Instead of three What? BT>> in a square 33 I quickly counted 8 projections of invariants (one black corner, a corner and adjacent , the black side, here to you and 9). E> for the coding of 9 numbers it is enough to consider a prime number of black pixels E> But here look, from obvious, there are 4 angular pixels, 4 "side" and 1 center E> Number angular - 5 variants, number side - 5 variants, and central - 2 variants. E> it already 50 variants. It, of course, is less 2 ^ (9-3), but, it is possible to note that in both 4-kah pixels, it is possible to apply the same coding, as on a square 22 that already gives 72 variants... Yes, I there , it is necessary not to subtract 8, and to divide on 8 Then yes, orientation not the most favourable. BT>> on idea, you take the formula which was deduced by you with rg45, and you compare to my of the first answer. BT>> only something you for N=2 is not true, I do not know as for the big. E> we deduced the formula of number of the pictures which are playing back at turn on 90. For N == 2 it gave 2 variants. E> like true - all white and all black... Aha, understood. Yes, then your formula works, but to compare to it it is not necessary

40

Re: QR-code

Hello, Erop! Number of the unique codes = (2 ^ (n^2) + 2*2 ^ ((n^2 + 3 * (n mod 2))/4) + 2 ^ ((n^2 + (n mod 2))/2))/4 E> Super! Similar on truth, but the answer it is possible not to select, of course, and to receive analytically. https://math.stackexchange.com/question … two-colors

41

Re: QR-code

Hello, Erop, you wrote: E> it is not assured that it here was, and is not assured that it for programmers. E> but to backs. E> we develop the standard of a QR-code. E> our QR-code of the size NxN is a small square from N x N pixels. Each pixel black or white. E> difficulty consists that when we scan the code, we do not know, what side turns a square. 4 variants (0, 90, 180 and 270 degrees) E> the Question are possible all? How many different unique numbers it is possible to encode such code so, what the read out number did not depend on square orientation. Without turn it is possible to encode M_0=2 ^ (n*n) combinations. Number of symmetric in relation to turn on 180 degrees: for even n, M_180 (n) =2 ^ (n*n/2) (we fill with the information only half of cells) For odd n, M_180 (n) =2 ^ ((n*n-1)/2 +1) (separately we consider the central bit). We generalize: M_180 (n) =2 ^ (((n*n) +1 * (n%2))/2) it is similar: M_90 (n) =2 ^ (n*n/4), if n%2 == 0 M_90 (n) =2 ^ ((n*n-1)/4+1), if n%2 == 1 M_90 (n) =2 ^ (((n*n) +3 * (n%2))/4), generally. The general M which we can encode: M (n) = (M_0 (n) - M_180 (n))/4 + (M_180 (n) - M_90 (n))/2 + M_90 (n) If all to substitute, the sequence resulted watchmaker th, probably turns out. Numerically coincides: 2, 6, 140, 16456, 8390720, 17179934976L, 140737496748032L, 4611686019501162496L, 604462909807864344215552L

42

Re: QR-code

Hello, Qulac, you wrote: Q> Hello, Erop, you wrote: E>> it is not assured that it here was, and is not assured that it for programmers. E>> but to backs. E>> we develop the standard of a QR-code. E>> our QR-code of the size NxN is a small square from N x N pixels. Each pixel black or white. E>> difficulty consists that when we scan the code, we do not know, what side turns a square. 4 variants (0, 90, 180 and 270 degrees) E>> the Question are possible all? How many different unique numbers it is possible to encode such code so, what the read out number did not depend on square orientation. Q> not  will be, if the square consists of identical quarters whereas do not turn - it will be identical to look. Not. It is Enough to place orientation mark to understand where a reference point. For example, 22 at corners.

43

Re: QR-code

Hello, Pzz, you wrote: Pzz> I understand how to encode (N^2 - 3) a bit. , like, (N^2 - 2). But how to beat off one more bit, somehow not , it is invented only, how the half-bit to beat off (i.e., (N^2 - 3) *3 variants) Whence follow, what the answer - a twain level? 6 for N == 2 as though hints that it not so

44

Re: QR-code

Hello, Chorkov, you wrote: a C> M (n) = (M_0 (n) - M_180 (n))/4 + (M_180 (n) - M_90 (n))/2 + M_90 (n) a C> If all to substitute, the sequence resulted watchmaker th, probably turns out. The C> Numerically coincides: a C> 2, 6, 140, 16456, 8390720, 17179934976L, 140737496748032L, 4611686019501162496L, 604462909807864344215552L Well. I solved somehow as. Only on my taste here there is no argumentation in protection of that it is impossible even more. But it obvious enough, IMHO.

45

Re: QR-code

Hello, Erop, you wrote: Pzz>> I understand how to encode (N^2 - 3) a bit. , like, (N^2 - 2). But how to beat off one more bit, somehow not , it is invented only, how the half-bit to beat off (i.e., (N^2 - 3) *3 variants) E> Whence follow, what the answer - a twain level? E> 6 for N == 2 as though hints that it not so I, as always, am inattentive, and by that moment when wrote the answer, have been assured that the question sounds, how many bits it is possible to encode. And different numbers, my answer 2 ^ (N^2 - 3) * 3 For N == 2 converges

46

Re: QR-code

Hello, Pzz, you wrote: Pzz> And different numbers, my answer 2 ^ (N^2 - 3) * 3 Pzz> For N == 2 converges For 1 converges not especially And for 3 it turns out 192? And how to encode?

47

Re: QR-code

Hello, Erop, you wrote: R>> me only now reached, about what you asked in the root message. Well so same .. To consider laziness. E> Still well to prove that it is impossible more. E> Well and well to check up that at least for N == 1 and N == 2 formula works Two days for me hands were scratched, at last reached. So, went. The number of unique images of a matrix of monochrome pixels of the size NxN about which it is asked in the task, is set by the general formula: where n 1 - the full amount , not possessing turning symmetry (it is formal: 1st order having an axis of symmetry): n 2 - the full amount , 2nd order having an axis of symmetry): For even N: For odd N: n 4 - the full amount , 4th order having an axis of symmetry): For even N: For odd N: Substituting expressions for n 1, n 2 and n 4 in the general formula, after simplification we receive total expressions: For even N: For odd N: If very much it would be desirable, both formulas without special work it is possible to merge in one. Instead of the proof check: N x 0 1 1 2 2 6 3 140 4 16456 5 8390720 6 17179934976 7 140737496748032

48

Re: QR-code

Hello, rg45, you wrote: R> Two days at me were scratched hands, at last reached. So, went. I solved as. But already above someone gave this decision. That on my taste here does not suffice - that substantiation that is impossible more.

49

Re: QR-code

Hello, Erop, you wrote: E> That on my taste here does not suffice - that substantiation that is impossible more. A substantiation very simple - all variants which we discarded,  are repetitions and it is clear already from the decision. Here if it is necessary to worry about something so about a reverse problem - whether and we cut all that was necessary, or, can,  something. But, , here all is simple, as a pig-iron frying pan.

50

Re: QR-code

Hello, Erop, you wrote: E> That on my taste here does not suffice - that substantiation that is impossible more. I, apparently, understood your thought. You mean that, probably that at N, big any certain value, can become favourable to sacrifice three angular  as about it it was told here the Author: Brice Tribbiani Date: 01.02 23:48? And can and not to become. Yes, interesting, it is necessary to ponder. [Upd]: yes, but is not present! Sacrifice  never will be advantageous. From the formulas deduced here the Author: rg45 Date: 03.02 16:43 that that approach provides an estimation "from below": While, sacrificing three , we always will have Exactly personally for me it is far unobvious and simply amazing output: rejection of a part of the images possessing turning symmetry of 2nd and 4th orders ALWAYS truncates result to a lesser degree, than  any unfortunate three pixels!