{"entities":{"Q1069308":{"pageid":1080060,"ns":120,"title":"Item:Q1069308","lastrevid":48890674,"modified":"2026-01-06T02:32:15Z","type":"item","id":"Q1069308","labels":{"en":{"language":"en","value":"On the distribution of de Bruijn sequences of low complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3934421"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$0E451D94-CAAD-4033-AFC7-17871322798A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"914c7c5ff7f67b9edcb8db2469d620874b7fb2ee","datavalue":{"value":{"text":"On the distribution of de Bruijn sequences of low complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069308$79279384-75B3-4B7E-B7C5-B8BF7140F2C4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5d21b95f9e5a4c02d7c074e4d9fe7c8e89143af8","datavalue":{"value":"0583.68036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$094853A3-4344-4DB9-9306-4AF2CA5D0961","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fb00ff25f2e533806900c9c27a6b8d094e48d737","datavalue":{"value":"10.1016/0097-3165(85)90074-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$4A17A559-B064-4D6E-B8E5-281B8A640032","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0466cb04766673ef45f49f26e6ccb66997720ee3","datavalue":{"value":{"entity-type":"item","numeric-id":397157,"id":"Q397157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$6A3A7ECB-A6CB-4586-AA28-8C00779D2253","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1c03f12d2ae232c6413ffedcffaa255461d32f1a","datavalue":{"value":{"entity-type":"item","numeric-id":171729,"id":"Q171729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$0FC7FE98-10F6-4D7B-A32D-1322AA3CB4F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1069308$01CE78DD-C12A-49EB-BF14-D90B64AC4357","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9ebc5ab80b5043a78c912db09cc35d8ac59834c5","datavalue":{"value":"The paper deals with a problem of complexity of de Bruijn sequences of order n, i.e. binary sequences \\(s=s_ 0,\\ldots,s_{2^ n-1}\\) satisfying a recurrence equation of the following type: \\(f(s_ i,\\ldots,s_{i+n-1})+s_{i+n}=0\\) (for \\(0\\leq i\\leq 2^ n-1\\) and with the other coefficients taken modulo \\(2^ n)\\) where n is the smallest number for which such a recurrence holds.    Because of numerous applications, since a long time the problem of synthesis of de Bruijn sequences has been considered, but the complexity problem has been clearly formulated not so long ago. In the last years there appeared papers dealing with the so called linear complexity of de Bruijn sequences meant as the smallest number m such that \\(\\sum^{m}_{j=1}a_ js_{i+m-j}+s_{i+m}=0\\), in GF(2), for some binary digits \\(a_ 1,\\ldots,a_ m\\). It is known that \\(2^{n-1}+n\\leq m\\leq 2^ n-1\\). There exist many open problems for such a notion of complexity. This paper solves some of them for the sequences whose complexity is between \\(2^{n-1}+n\\) and \\(2^{n-1}+2^{n-2}\\). The application of an interesting technique allows to evaluate the number of such sequences and to give a recursive method to generate sequences of complexity \\(2^{n-1}+2^{n-2}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069308$7EC48C30-DD6C-467D-9DBA-0D5E0B0DD061","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"25fe30a6fe5285f54b3a7ea7d7e97ac0b640e4f9","datavalue":{"value":"68R99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$ABD455D3-02CA-4044-94DD-30119A8434FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$54ADE32C-6736-4941-8D76-7B6CC561949C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"44bc3f4b62b406982652a23d68d9c7868a54f1c6","datavalue":{"value":"11B37","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$B22601CA-32DA-415D-80E6-FC4C04B456CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$39ED3481-E6D5-4E28-A95F-16C3D4730BB3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"427d9268858689c30299bb4b260bf7a3acf53247","datavalue":{"value":"3934421","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$8BC3206B-0F66-443D-87F5-0DDCFAB8573E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2e67b1c12be0c27b92cb3751d4f2a1c54be8688","datavalue":{"value":"linear recurrence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069308$38D51DD4-7026-43FD-A83A-C1C719C4FCE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8a55fb7e70a0a30faba9d447ff633fcbf884168f","datavalue":{"value":"linear complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069308$0BEDE609-B5D0-4CAD-B2E7-C19FC9D579F8","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$54860633-7F4F-4FA8-9CE8-E036069C47FF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8dad7ff23bc1ff45a14878d5b99399533a00ae9b","datavalue":{"value":"https://doi.org/10.1016/0097-3165(85)90074-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069308$5D43ACCA-E154-4011-9DB8-3ED890B33A1F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"63ced09ed789ba2d9da9588433b2f353690db857","datavalue":{"value":"W1986762795","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069308$3AD25B87-2AFE-4CEB-AEEF-7984789BF684","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c6677725adbb0d74b2adf9337d70f1369f9f0ab5","datavalue":{"value":{"entity-type":"item","numeric-id":3940837,"id":"Q3940837"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$1A63D76E-D1B6-4493-925D-8535E4775714","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43ec60a46cf0f58891e56fb9eef8c935cf31e340","datavalue":{"value":{"entity-type":"item","numeric-id":1836666,"id":"Q1836666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$1D25B98D-4962-4969-B75E-5D53F57AEFB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c95f18b9feb02cb09186f4924033cea7c39fc993","datavalue":{"value":{"entity-type":"item","numeric-id":3684033,"id":"Q3684033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$21894A26-DB24-401A-B343-79A11BA07ABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f92301941753a5df61b48f92f11818a1ba099dd6","datavalue":{"value":{"entity-type":"item","numeric-id":3964019,"id":"Q3964019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$BD94E766-7662-4601-8E77-EFCA24F94E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b2cde281b82fd62f1d8a9608ad27e3886dcef9f","datavalue":{"value":{"entity-type":"item","numeric-id":5632465,"id":"Q5632465"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069308$E78A0D43-88BC-44D2-9DCA-546635738CB7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f383ca3d409fcc1ec55507de4a270d7b4f5cfb5","datavalue":{"value":{"entity-type":"item","numeric-id":4701313,"id":"Q4701313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"73dad713977f7c5e9d050cba846d90533305a9ad","datavalue":{"value":{"amount":"+0.8909251689910889","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069308$20C84CF1-B055-4A98-83E1-96F2271189F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fc7495b31343619ccdf25072e631392c61e9156","datavalue":{"value":{"entity-type":"item","numeric-id":3684033,"id":"Q3684033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b41349d790e3e98d682ba6015e2318906f035a3","datavalue":{"value":{"amount":"+0.8832084536552429","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069308$7A9B2566-B165-4590-8F77-5C8D1349E11D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04db040757ab7d4e138c1900f1417a8bdf5fee9a","datavalue":{"value":{"entity-type":"item","numeric-id":3698698,"id":"Q3698698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d698a1ca3dcdfc771b8233c70c08c3cb32af9f4c","datavalue":{"value":{"amount":"+0.868428647518158","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069308$F37B07A8-91C7-45BB-A3A1-0BE94AABD866","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4dff18ab7f5f92180a1bac3653b3bfb51cce9e3","datavalue":{"value":{"entity-type":"item","numeric-id":3328448,"id":"Q3328448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5e37700c9d8b991a7a9feaf917194b25913f6209","datavalue":{"value":{"amount":"+0.8479118347167969","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069308$160D6C73-DB16-4C7E-BD6D-E045541B2B10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2133a29530419f6311755de157bab0901da642a7","datavalue":{"value":{"entity-type":"item","numeric-id":3813752,"id":"Q3813752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a695c05cb95c56ea059eeec7b9f005d78923c567","datavalue":{"value":{"amount":"+0.8280585408210754","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1069308$55A3BD42-07B3-4871-8D4C-F6E15E709E5D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1069308","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1069308"}}}}}