{"entities":{"Q5612612":{"pageid":7642172,"ns":120,"title":"Item:Q5612612","lastrevid":110050877,"modified":"2026-11-15T02:33:58Z","type":"item","id":"Q5612612","labels":{"en":{"language":"en","value":"A Simple Estimate for the Number of Steps in the Euclidean Algorithm"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3335209"}},"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":"Q5612612$18A7D849-A56E-448B-A673-1852C54ECD73","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e8b28f80cc33604f0b2162810c54799d74de4586","datavalue":{"value":{"text":"A Simple Estimate for the Number of Steps in the Euclidean Algorithm","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5612612$CD666D55-2D23-42DE-AD1D-211A10C7BC00","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0410f18331cfd37c2c905201791f56859546c207","datavalue":{"value":"0211.37401","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5612612$B5859062-6DAB-4F10-BA6D-25EB3A32AACC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8760b9d1bc863cc7d0adbd2467deb8880f891c32","datavalue":{"value":"10.2307/2316901","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5612612$0A6C39A4-9D90-448B-82C9-8384324CC493","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"cb96b4ac991d1c9fabb6ef3d281db52e4eb2e155","datavalue":{"value":{"entity-type":"item","numeric-id":93751,"id":"Q93751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5612612$AEE0F5E2-0012-450E-8679-DEE17877E483","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"652ad65ffdd573691be68fbfe67aa0cdf6812549","datavalue":{"value":{"time":"+1971-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":"Q5612612$2DB5BE0C-0EEF-4CC9-988E-895CCA16377F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5f6f2e73ebe360c69b5f99d6be8e06f538650497","datavalue":{"value":"11A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5612612$BA859333-926A-4537-9402-30FFB25A36A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"223fe586607c60b0738504f3419a7d40d2a118fe","datavalue":{"value":"11A55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5612612$AF889766-F170-4FCC-9643-48C0B42168A0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8295693b9d392abdcf8179b995cca0291ea00561","datavalue":{"value":"3335209","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5612612$E30A2452-A537-428B-B6E7-CDE1124BEA04","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ec2c4a0d44ae34eab5ccd9f92e18d689ea45b236","datavalue":{"value":{"entity-type":"item","numeric-id":590084,"id":"Q590084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5612612$C3FDA1D9-8038-4E2A-BFD7-A1FD573C9B62","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":"Q5612612$1A280086-3488-4DD2-9E30-9649CB19B98B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"794d6fcb9eae14ef6a4a5e0c8322376df556e201","datavalue":{"value":"https://doi.org/10.2307/2316901","type":"string"},"datatype":"url"},"type":"statement","id":"Q5612612$46B245DA-D913-4FBF-9AC8-0832BFC6EF13","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"891e466d9ae49a635f0f81110ad64f92671f0f0b","datavalue":{"value":"W4255646663","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5612612$6651B622-6824-4B6E-A151-9998903AC76E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b718e70e9aac283d7303eee916cc2f95af203bb","datavalue":{"value":{"entity-type":"item","numeric-id":5921064,"id":"Q5921064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1061c3ee0bfda010b016ac872191089f8f70a353","datavalue":{"value":{"amount":"+0.8927937746047974","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":"Q5612612$AA4038A3-2918-4CD5-8E58-95A0E1134191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"35fef5014728061e6188fcfa21d447f69964f0af","datavalue":{"value":{"entity-type":"item","numeric-id":1172658,"id":"Q1172658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7287caf6218f352073a496e3e4990969512e88ce","datavalue":{"value":{"amount":"+0.8386254906654358","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":"Q5612612$C8BC29DD-913E-48B9-9C44-13D3411F9036","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"348f09bc7a3673a070e82fbe63a6e869612a7851","datavalue":{"value":{"entity-type":"item","numeric-id":5000138,"id":"Q5000138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ce64b6188561e29df5a53b042403e885f2493537","datavalue":{"value":{"amount":"+0.8225347995758057","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":"Q5612612$D0CA9B56-2BE3-494E-9613-04EEC724F084","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5cbce212e699b775d1734ebac6f89b924759ee58","datavalue":{"value":{"entity-type":"item","numeric-id":3677809,"id":"Q3677809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b65141d51a3e11affebcfeccdca8ba674d2d0ae4","datavalue":{"value":{"amount":"+0.8148818016052246","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":"Q5612612$1A86A7DA-A0CE-4388-8AC4-DE90EC5B2CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a309499618e65cc8c42807254fdb7d590b021bc","datavalue":{"value":{"entity-type":"item","numeric-id":5504844,"id":"Q5504844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9f05f3500e2ccb8d40b63024b32e060e7bc2eab","datavalue":{"value":{"amount":"+0.8012214303016663","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":"Q5612612$9A1F58F4-B41C-4886-91F0-08285641FC93","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cc9d83b6dc4f0f4f8ad8cc0dfb8526ffc3337c2c","datavalue":{"value":"For any pair of integers \\(0<u\\le v\\) we define \\(L(u,v)\\) to be the number of steps required in the Euclidean algorithm to calculate the greatest common denominator. Consider the values of \\(L(u,v)\\) when \\(0 <u\\le v\\le x\\). It is a classical result that \\(L(u,v) \\le 2.1(\\log x+1)\\); the worst cases are when \\(u\\) and \\(u\\) are consecutive Fibonacci numbers. The author recently proved (using results from metric number theory) that for each \\(\\varepsilon>0\\) the inequality \\[ \\vert L(u,v) - (12\\pi^{-2} \\log 2) \\log x\\vert < (\\log x)^{1/2+ \\varepsilon} \\] holds for almost all pairs \\(u,v\\) as \\(x\\to\\infty\\) [the author, J. Number Theory 2, 414--422 (1970; Zbl 0206.33502)]. The present note shows how to prove a weaker (but qualitatively correct) result in a few lines. Specifically it is shown that the proportion of pairs \\(u,v\\) which fail to satisfy \\[ \\tfrac12 \\log x \\le L(u,v) \\le 2.1(\\log x+ 1)\\] tends to 0 as ''fast'' as \\(x^{-1/100}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q5612612$748F40FF-8242-4901-A7BD-DD08112325D9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A Simple Estimate for the Number of Steps in the Euclidean Algorithm","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_Simple_Estimate_for_the_Number_of_Steps_in_the_Euclidean_Algorithm"}}}}}