[{"id":246968,"date":"2026-04-14T07:19:42","date_gmt":"2026-04-14T12:19:42","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246968"},"modified":"2026-04-14T07:53:50","modified_gmt":"2026-04-14T12:53:50","slug":"artz-parabola","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/14\/artz-parabola\/","title":{"rendered":"Finding a parabola through two points with given slopes"},"content":{"rendered":"<p>The Wikipedia article on modern triangle geometry has an image labled &#8220;Artz parabolas&#8221; with no explanation.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium\" src=\"https:\/\/www.johndcook.com\/artz_triangle.png\" width=\"330\" height=\"247\" \/><\/p>\n<p>A quick search didn&#8217;t turn up anything about Artz parabolas, but apparently the parabolas go through pairs of vertices with tangents parallel to the sides.<\/p>\n<p>The general form of a conic section is<\/p>\n<p style=\"padding-left: 40px;\"><em>ax<\/em>\u00b2 + <em>bxy<\/em> + <em>cy<\/em>\u00b2 + <em>dx<\/em> + <em>ey<\/em> + <em>f<\/em> = 0<\/p>\n<p>and the constraint\u00a0<em>b<\/em>\u00b2 = 4<em>ac<\/em> means the conic will be a parabola.<\/p>\n<p>We have 6 parameters, each determined only up to a scaling factor; you can multiply both sides by any non-zero constant and still have the same conic. So a general conic has 5 degrees of freedom, and the parabola condition <em>b<\/em>\u00b2 = 4<em>ac<\/em> takes us down to 4. Specifying two points that the parabola passes through takes up 2 more degrees of freedom, and specifying the slopes takes up the last two. So it&#8217;s plausible that there is a unique solution to the problem.<\/p>\n<p>There is indeed a solution, unique up to scaling the parameters. The following code finds parameters of a parabola that passes through (<em>x<\/em><sub><em>i<\/em><\/sub>, <em>y<\/em><sub><em>i<\/em><\/sub>) with slope <em>m<\/em><sub><em>i<\/em><\/sub> for <em>i<\/em> = 1, 2.<\/p>\n<pre>def solve(x1, y1, m1, x2, y2, m2):\r\n    \r\n    \u0394x = x2 - x1\r\n    \u0394y = y2 - y1\r\n    \u03bb = 4*(\u0394x*m1 - \u0394y)*(\u0394x*m2 - \u0394y)\/(m1 - m2)**2\r\n    k = x2*y1 - x1*y2\r\n\r\n    a = \u0394y**2 + \u03bb*m1*m2\r\n    b = -2*\u0394x*\u0394y - \u03bb*(m1 + m2)\r\n    c = \u0394x**2 + \u03bb\r\n    d =  2*k*\u0394y + \u03bb*(m1*y2 + m2*y1 - m1*m2*(x1 + x2))\r\n    e = -2*k*\u0394x + \u03bb*(m1*x1 + m2*x2 - y1 - y2)\r\n    f = k**2 + \u03bb*(m1*x1 - y1)*(m2*x2 - y2)\r\n\r\n    return (a, b, c, d, e, f)\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>The Wikipedia article on modern triangle geometry has an image labled &#8220;Artz parabolas&#8221; with no explanation. A quick search didn&#8217;t turn up anything about Artz parabolas, but apparently the parabolas go through pairs of vertices with tangents parallel to the sides. The general form of a conic section is ax\u00b2 + bxy + cy\u00b2 + [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[224],"class_list":["post-246968","post","type-post","status-publish","format-standard","hentry","category-math","tag-geometry"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246968","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246968"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246968\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246968"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246968"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246968"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246966,"date":"2026-04-13T09:33:16","date_gmt":"2026-04-13T14:33:16","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246966"},"modified":"2026-04-13T20:28:23","modified_gmt":"2026-04-14T01:28:23","slug":"the-smallest-math-library","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/13\/the-smallest-math-library\/","title":{"rendered":"Mathematical minimalism"},"content":{"rendered":"<p>Andrzej Odrzywolek recently posted an article on <a href=\"https:\/\/arxiv.org\/abs\/2603.21852v2\">arXiv<\/a> showing that you can obtain all the elementary functions from just the function<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter\" style=\"background-color: white;\" src=\"https:\/\/www.johndcook.com\/eml.svg\" alt=\"\\operatorname{eml}(x,y) = \\exp(x) - \\log(y)\" width=\"224\" height=\"18\" \/><\/p>\n<p>and the constant 1. The following equations, taken from the paper&#8217;s <a href=\"https:\/\/arxiv.org\/src\/2603.21852v2\/anc\/SupplementaryInformation.pdf\">supplement<\/a>, show how to bootstrap addition, subtraction, multiplication, and division from the eml function.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter\" style=\"background-color: white;\" src=\"https:\/\/www.johndcook.com\/elm.svg\" alt=\"\\begin{align*} \\exp(z) &amp;\\mapsto \\operatorname{eml}(z,1) \\\\ \\log(z) &amp;\\mapsto \\operatorname{eml}(1,\\exp(\\operatorname{eml}(1,z))) \\\\ x - y &amp;\\mapsto \\operatorname{eml}(\\log(x),\\exp(y)) \\\\ -z &amp;\\mapsto (\\log 1) - z \\\\ x + y &amp;\\mapsto x - (-y) \\\\ 1\/z &amp;\\mapsto \\exp(-\\log z) \\\\ x \\cdot y &amp;\\mapsto \\exp(\\log x + \\log y) \\end{align*}\" width=\"264\" height=\"193\" \/><\/p>\n<p>See the paper and supplement for how to obtain constants like \u03c0 and functions like square and square root, as well as the standard circular and hyperbolic functions.<\/p>\n<h2>Related posts<\/h2>\n<ul>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2021\/01\/05\/bootstrapping-math-library\/\">Bootstrapping a small math library<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2026\/04\/06\/tofolli-gates\/\">Toffoli gates are all you need<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Andrzej Odrzywolek recently posted an article on arXiv showing that you can obtain all the elementary functions from just the function and the constant 1. The following equations, taken from the paper&#8217;s supplement, show how to bootstrap addition, subtraction, multiplication, and division from the eml function. See the paper and supplement for how to obtain [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[],"class_list":["post-246966","post","type-post","status-publish","format-standard","hentry","category-math"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246966","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246966"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246966\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246966"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246966"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246966"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246963,"date":"2026-04-12T18:42:01","date_gmt":"2026-04-12T23:42:01","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246963"},"modified":"2026-04-12T18:47:36","modified_gmt":"2026-04-12T23:47:36","slug":"lunations","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/12\/lunations\/","title":{"rendered":"Lunar period approximations"},"content":{"rendered":"<h2>The date of Easter<\/h2>\n<p>The church fixed Easter to be the first Sunday after the first full moon after the Spring equinox. They were choosing a date in the Roman (Julian) calendar to commemorate an event whose date was known according to the Jewish lunisolar calendar, hence the reference to equinoxes and full moons.<\/p>\n<p>The <a href=\"https:\/\/www.johndcook.com\/blog\/2026\/04\/12\/orthodox-western-easter\/\">previous post<\/a> explained why the Eastern and Western dates of Easter differ. The primary reason is that both churches use March 21 as the first day of Spring, but the Eastern church uses March 21 on the Julian calendar and the Western church uses March 21 on the Gregorian calendar.<\/p>\n<p>But that&#8217;s not the only difference. The churches chose different algorithms for calculating when the first full moon would be. The date of Easter doesn&#8217;t depend on the date of the full moon per se, but the methods used to predict full moons.<\/p>\n<p>This post will show why determining the date of the full moon is messy.<\/p>\n<h2>Lunation length<\/h2>\n<p>The moon takes between 29 and 30 days between full moons (or between new moons, which are easier to objectively measure). This period is called a <b>lunation<\/b>. The average length of a lunation is <em>L<\/em> = 29.530588853 days. This is not a convenient number to work with, and so there&#8217;s no simple way of reconciling the orbital period of the moon with the rotation period of the earth [1]. Lunar calendars alternate months with 29 and 30 days, but they can&#8217;t be very accurate, so they have to have some fudge factor analogous to leap years.<\/p>\n<p>The value of <em>L<\/em> was known from ancient times. Meton of Athens calculated in 432 BC that 235 lunar cycles equaled 19 tropical years or 6940 days. This corresponds to <em>L<\/em> \u2248 29.5319. Around a century later the Greek scholar Callippus refined this to 940 cycles in 76 years or 27,759 days. This corresponds to <em>L<\/em> \u2248 29.53085.<\/p>\n<p>The problem wasn&#8217;t <em>knowing<\/em> <em>L<\/em> but devising a convenient way of <em>working<\/em> with <em>L<\/em>. There is no way to work with lunations that is as easy as the way the Julian (or even the more complicated Gregorian) calendar reconciles days with years.<\/p>\n<h2>Approximations<\/h2>\n<p>Let&#8217;s look at the accuracy of several approximations for <em>L<\/em>. We&#8217;d like an approximation that is not only accurate in an absolute sense, but also accurate relative to its complexity. The complexity of a fraction is measured by a <a href=\"https:\/\/www.johndcook.com\/blog\/2023\/09\/17\/rational-height-functions\/\">height function<\/a>. We&#8217;ll use what&#8217;s called the &#8220;classic&#8221; height function: log( max(<em>n<\/em>, <em>d<\/em>) ) where <em>n<\/em> and <em>d<\/em> are the numerator and denominator of a fraction. Since we&#8217;re approximating a number bigger than 1, this will be simply log(<em>n<\/em>).<\/p>\n<p>We will compare the first five convergents, approximations that come from the continued fraction form of <em>L<\/em>, and the approximations of Meton and Callippus. Here&#8217;s a plot.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium\" src=\"https:\/\/www.johndcook.com\/lunation.png\" width=\"480\" height=\"360\" \/><\/p>\n<p>And here&#8217;s the code that produced the plot, showing the fractions used.<\/p>\n<pre>from numpy import log\r\nimport matplotlib.pyplot as plt\r\n\r\nfracs = [\r\n    (30, 1), \r\n    (59, 2),\r\n    (443, 15),\r\n    (502, 17),\r\n    (1447, 49),\r\n    (6940, 235),\r\n    (27759, 940)\r\n]\r\n\r\ndef error(n, d):\r\n    L = 29.530588853    \r\n    return abs(n\/d - L)\r\n\r\nfor f in fracs:\r\n    plt.plot(log(f[0]), log(error(*f)), 'o')\r\nplt.xlabel(\"log numerator\")\r\nplt.ylabel(\"log error\")\r\nplt.show()\r\n<\/pre>\n<p>The approximation 1447\/49 is the best by far, both in absolute terms and relative to the size of the numerator. But it&#8217;s not very useful for calendar design because 1447 is not nicely related to the number of days in a year.<\/p>\n<p>&nbsp;<\/p>\n<p>[1] The time between full moons is a synodic month, the time it takes for the moon to return to the same position relative to the sun. This is longer than a sidereal month, the time it takes the moon to complete one orbit relative to the fixed stars.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The date of Easter The church fixed Easter to be the first Sunday after the first full moon after the Spring equinox. They were choosing a date in the Roman (Julian) calendar to commemorate an event whose date was known according to the Jewish lunisolar calendar, hence the reference to equinoxes and full moons. The [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[305],"class_list":["post-246963","post","type-post","status-publish","format-standard","hentry","category-math","tag-calendars"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246963","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246963"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246963\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246963"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246963"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246963"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246959,"date":"2026-04-12T07:09:13","date_gmt":"2026-04-12T12:09:13","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246959"},"modified":"2026-04-13T17:46:10","modified_gmt":"2026-04-13T22:46:10","slug":"orthodox-western-easter","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/12\/orthodox-western-easter\/","title":{"rendered":"The gap between Eastern and Western Easter"},"content":{"rendered":"<p>Today is Orthodox Easter. Western churches celebrated Easter last week. Why are the Eastern and Western dates of Easter different? Is Eastern Easter always later than Western Easter? How far apart can the two dates be?<\/p>\n<h2>Why the dates differ<\/h2>\n<p>Easter is on the first Sunday after the first full moon in Spring [1]. East and West agree on this. What they disagree on is the details of &#8220;full moon&#8221; and &#8220;Spring.&#8221; The dates are not based on precise astronomical measurements but rather on astronomical approximations codified long ago.<\/p>\n<p>Spring begins on March 21 for the purposes of calculating Easter. But the Western church uses March 21 on the <a href=\"https:\/\/www.johndcook.com\/blog\/2024\/12\/16\/gregorian-calendar\/\">Gregorian calendar<\/a> and the Eastern church uses March 21 on the Julian calendar. This mostly accounts for the difference between Eastern and Western dates for Easter. East and West also use slightly different methods of approximating when the moon will be full. More on that in the <a href=\"https:\/\/www.johndcook.com\/blog\/2026\/04\/12\/lunations\/\">next post<\/a>.<\/p>\n<h2>Pascha never comes before Easter<\/h2>\n<p>The Eastern name for Easter is Pascha. Eastern Pascha and Western Easter can occur on the same day, but otherwise Pascha is always later, never earlier. This is because the Julian year is longer than the Gregorian year, causing fixed dates on the former calendar to occur after the later. Also, the Eastern method of approximating the date of the Paschal full moon gives a later date than the Western method.<\/p>\n<p>The Julian calendar has exactly 365 1\/4 days. The Gregorian calendar has 365 97\/400 days; centuries are not leap years unless they&#8217;re divisible by 400. This complication in the Gregorian calendar was necessary to match the solar year. The date March 21 on the Julian calendar is drifting later in the year from the perspective of the Gregorian calendar, moving further past the astronomical equinox [2].<\/p>\n<h2>Size of the gap<\/h2>\n<p>Eastern and Western dates of Easter can coincide. The were the same last year, and will be the same again in 2028. The gap is always a whole number of weeks because Easter is always on a Sunday.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium\" src=\"https:\/\/www.johndcook.com\/easter_gap3.svg\" width=\"600\" height=\"350\" \/><\/p>\n<p>The gap is usually 1 week. It can be 0, 4, or 5 weeks, but never 2 or 3 weeks.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium\" src=\"https:\/\/www.johndcook.com\/easter_gap4.svg\" width=\"600\" height=\"370\" \/><\/p>\n<p>This is the pattern for now. Sometime in the distant future the Julian and Gregorian calendars will diverge further than the gaps will increase. Presumably Orthodox churches will make some sort of adjustment before the Julian date March 21 drifts into summer or fall.<\/p>\n<h2>Related posts<\/h2>\n<ul>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2024\/12\/31\/cycle-of-new-years-days\/\">Cycle of New Year&#8217;s Days<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2025\/12\/23\/when-was-newton-born\/\">When was Newton born?<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2025\/02\/28\/martian-leap-years\/\">Martian leap years<\/a><\/li>\n<\/ul>\n<p>[1] The reason for this definition is that Christ was crucified at the time of the Passover. Due to the lunisolar design of the Jewish calendar, this would have been during the first full moon after the Spring equinox. Christ rose from the dead the Sunday following the crucifixion, so Easter is on the first Sunday after the first full moon of Spring.<\/p>\n<p>[2] The Julian and Gregorian calendars currently differ by 13 days, and they&#8217;re drifting apart at the rate of 3 days every 400 years. Somewhere around 47,000 years from now the two calendars will agree again, sorta, because the Julian calendar will be a full year behind the Gregorian calendar.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Today is Orthodox Easter. Western churches celebrated Easter last week. Why are the Eastern and Western dates of Easter different? Is Eastern Easter always later than Western Easter? How far apart can the two dates be? Why the dates differ Easter is on the first Sunday after the first full moon in Spring [1]. East [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[305],"class_list":["post-246959","post","type-post","status-publish","format-standard","hentry","category-math","tag-calendars"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246959","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246959"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246959\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246959"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246959"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246959"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246958,"date":"2026-04-10T09:29:49","date_gmt":"2026-04-10T14:29:49","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246958"},"modified":"2026-04-12T11:53:53","modified_gmt":"2026-04-12T16:53:53","slug":"fraction-digits","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/10\/fraction-digits\/","title":{"rendered":"Distribution of digits in fractions"},"content":{"rendered":"<p>There&#8217;s a lot of mathematics just off the beaten path. You can spend a career in math and yet not know all there is to know about even the most basic areas of math. For example, this post will demonstrate something you may not have seen about decimal forms of fractions.<\/p>\n<p>Let <em>p<\/em> &gt; 5 be a prime number and 0 &lt; <em>k<\/em> &lt; <em>p<\/em>. Then the digits in <em>k<\/em>\/<em>p<\/em> might be the same for all <em>k<\/em>, varying only by cyclic permutations. This is the case, for example, when <em>p<\/em> = 7 or <em>p<\/em> = 17. More on these kinds of fractions <a href=\"https:\/\/www.johndcook.com\/blog\/2014\/11\/12\/cyclic-fractions\/\">here<\/a>.<\/p>\n<p>The digits in <em>k<\/em>\/<em>p<\/em> repeat for every <em>k<\/em>, but different values of <em>k<\/em> might have sequences of digits that vary by more than cyclic permutations. For example, let&#8217;s look at the values of <em>k<\/em>\/13.<\/p>\n<pre>&gt;&gt;&gt; for i in range(1, 13):\r\n...   print(i\/13)\r\n...\r\n 1 0.0769230769230769\r\n 2 0.1538461538461538\r\n 3 0.2307692307692307\r\n 4 0.3076923076923077\r\n 5 0.3846153846153846\r\n 6 0.4615384615384615\r\n 7 0.5384615384615384\r\n 8 0.6153846153846154\r\n 9 0.6923076923076923\r\n10 0.7692307692307693\r\n11 0.8461538461538461\r\n12 0.9230769230769231\r\n<\/pre>\n<p>One cycle goes through the digits 076923. You&#8217;ll see this when <em>k<\/em> = 1, 3, 4, 9, 10, or 11. The other cycle goes through 153846 for the rest of the values of <em>k<\/em>. The cycles 076923 and 153846 are called the <strong>distinct repeating sets<\/strong> of 13 in [1].<\/p>\n<p>If we look at fractions with denominator 41, thee are six distinct repeating sets.<\/p>\n<pre>02439\r\n04878\r\n07317\r\n09756\r\n12195\r\n14634\r\n26829\r\n36585\r\n<\/pre>\n<p>You could find these by modifying the Python code above. However, in general you&#8217;ll need more than default precision to see the full periods. You might want to shift over to <code>bc<\/code>, for example.<\/p>\n<p>When you look at all the distinct repeating sets of a prime number, all digits appear almost the same number of times. Some digits may appear one more time than others, but that&#8217;s as uneven as you can get. A corollary in [1] states that if <em>p<\/em> = 10<em>q<\/em> + <em>r<\/em>, with 0 &lt; <em>r<\/em> &lt; 10, then 11 \u2212 <em>r<\/em> digits appear <em>q<\/em> times, and <em>r<\/em> \u2212 1 digits appear <em>q<\/em> + 1 times.<\/p>\n<p>Looking back at the example with <em>p<\/em> = 13, we have <em>q<\/em> = 1 and <em>r<\/em> = 3. The corollary says we should expect 8 digits to appear once and 2 digits to appear twice. And that&#8217;s what we see: in the sets 076923 and 153846 we have 3 and 6 repeated twice and the remaining 8 digits appear once.<\/p>\n<p>In the example with <em>p<\/em> = 41, we have <em>q<\/em> = 4 and <em>r<\/em> = 1. So we expect all 10 digits to appear 4 times, which is the case.<\/p>\n<h2>Related posts<\/h2>\n<ul>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2014\/11\/12\/cyclic-fractions\/\">Cyclic fractions<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2016\/10\/18\/periods-of-fractions\/\">Periods of fractions<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2018\/05\/30\/calendars-and-continued-fractions\/\">Calendars and continued fractions<\/a><\/li>\n<\/ul>\n<p>[1] James K. Schiller. A Theorem in the Decimal Representation of Rationals. The American Mathematical Monthly<br \/>\nVol. 66, No. 9 (Nov., 1959), pp. 797-798<\/p>\n","protected":false},"excerpt":{"rendered":"<p>There&#8217;s a lot of mathematics just off the beaten path. You can spend a career in math and yet not know all there is to know about even the most basic areas of math. For example, this post will demonstrate something you may not have seen about decimal forms of fractions. Let p &gt; 5 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[94],"class_list":["post-246958","post","type-post","status-publish","format-standard","hentry","category-math","tag-number-theory"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246958","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246958"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246958\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246958"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246958"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246958"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246957,"date":"2026-04-09T12:54:21","date_gmt":"2026-04-09T17:54:21","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246957"},"modified":"2026-04-09T12:54:21","modified_gmt":"2026-04-09T17:54:21","slug":"pyramid-speed-of-light","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/09\/pyramid-speed-of-light\/","title":{"rendered":"The Great Pyramid of Giza and the Speed of Light"},"content":{"rendered":"<p>Saw a <a href=\"https:\/\/x.com\/Andercot\/status\/2042088784255447062?s=20\">post<\/a> on X saying that the latitude of the Pyramid of Giza is the same as the speed of light.<\/p>\n<p>I looked into this, expecting it to be approximately true. It&#8217;s <em>exactly<\/em> true in the sense that the speed of light in vacuum is 299,792,458 m\/s and the line of latitude 29.9792458\u00b0 N passes through the pyramid. The exact center of the pyramid is at 29.97917\u00b0 N, 31.13417\u00b0 E.<\/p>\n<p>Of course this is a coincidence. Even if you believe that somehow the ancient Egyptians knew the speed of light, the meter was defined four millennia after the pyramid was built. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Saw a post on X saying that the latitude of the Pyramid of Giza is the same as the speed of light. I looked into this, expecting it to be approximately true. It&#8217;s exactly true in the sense that the speed of light in vacuum is 299,792,458 m\/s and the line of latitude 29.9792458\u00b0 N [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-246957","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246957","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246957"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246957\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246957"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246957"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246957"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246955,"date":"2026-04-09T12:25:08","date_gmt":"2026-04-09T17:25:08","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246955"},"modified":"2026-04-09T12:25:08","modified_gmt":"2026-04-09T17:25:08","slug":"random-hexagon-fractal","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/09\/random-hexagon-fractal\/","title":{"rendered":"Random hexagon fractal"},"content":{"rendered":"<p>I recently ran across a <a href=\"https:\/\/x.com\/LensScientific\/status\/2041951822727016930?s=20\">post<\/a> on X describing a process for creating a random fractal. First, pick a random point <em>c<\/em> inside a hexagon.<\/p>\n<p>Then at each subsequent step, pick a random side of the hexagon and create the triangle formed by that side and\u00a0<em>c<\/em>. Update\u00a0<em>c<\/em> to be the center of the new triangle and plot\u00a0<em>c<\/em>.<\/p>\n<p>Note that you only choose a random <em>point<\/em> inside the hexagon once. After that you randomly choose <em>sides<\/em>.<\/p>\n<p>Now there are <a href=\"https:\/\/faculty.evansville.edu\/ck6\/encyclopedia\/etc.html\">many<\/a> ways to define the center of a triangle. I assumed the original meant barycenter (centroid) when it said &#8220;center&#8221;, and apparently that was correct. I was able to create a similar figure.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium\" src=\"https:\/\/www.johndcook.com\/hex_barycenter.png\" width=\"314\" height=\"355\" \/><\/p>\n<p>But if you define center differently, you get a different image. For example, here&#8217;s what you get when you use the incenter, the center of the largest circle inside the triangle.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-medium\" src=\"https:\/\/www.johndcook.com\/hex_incenter.png\" width=\"314\" height=\"355\" \/><\/p>\n<h2>Related posts<\/h2>\n<ul>\n<li class='link'><a href=\"https:\/\/www.johndcook.com\/blog\/2025\/09\/11\/random-inside-triangle\/\">Randomly selecting points in a triangle<\/a><\/li>\n<li class='link'><a href='https:\/\/www.johndcook.com\/blog\/2023\/09\/09\/triangle-subdivision\/'>Subdividing a triangle with various centers<\/a><\/li>\n<li class='link'><a href='https:\/\/www.johndcook.com\/blog\/2025\/08\/16\/randomly-generated-dragon\/'>Randomly generated dragon fractal<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2017\/07\/08\/the-chaos-game-and-the-sierpinski-triangle\/\">The chaos game and the Sierpinski triangle<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>I recently ran across a post on X describing a process for creating a random fractal. First, pick a random point c inside a hexagon. Then at each subsequent step, pick a random side of the hexagon and create the triangle formed by that side and\u00a0c. Update\u00a0c to be the center of the new triangle [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[224],"class_list":["post-246955","post","type-post","status-publish","format-standard","hentry","category-math","tag-geometry"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246955","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246955"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246955\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246955"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246955"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246955"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246954,"date":"2026-04-08T19:18:57","date_gmt":"2026-04-09T00:18:57","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246954"},"modified":"2026-04-08T19:19:39","modified_gmt":"2026-04-09T00:19:39","slug":"andrica","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/08\/andrica\/","title":{"rendered":"Root prime gap"},"content":{"rendered":"<p>I recently found out about Andrica&#8217;s conjecture: the square roots of consecutive primes are less than 1 apart.<\/p>\n<p>In symbols, Andrica&#8217;s conjecture says that if <em>p<\/em><sub><em>n<\/em><\/sub> and <em>p<\/em><sub><em>n<\/em>+1<\/sub> are consecutive prime numbers, then<\/p>\n<p style=\"padding-left: 40px;\">\u221a<em>p<\/em><sub><em>n<\/em>+1<\/sub> \u2212 \u221a<em>p<\/em><sub><em>n<\/em><\/sub> &lt; 1.<\/p>\n<p>This has been empirically verified for primes up to 2 \u00d7 10<sup>19<\/sup>.<\/p>\n<p>If the conjecture is true, it puts an upper bound on how long you&#8217;d have to search to find the next prime:<\/p>\n<p style=\"padding-left: 40px;\"><em>p<\/em><sub><em>n<\/em>+1<\/sub> &lt; 1 + 2\u221a<em>p<\/em><sub><em>n<\/em><\/sub>\u00a0 + <em>p<\/em><sub><em>n<\/em><\/sub>,<\/p>\n<p>which would be an improvement on the Bertrand-Chebyshev theorem that says<\/p>\n<p style=\"padding-left: 40px;\"><em>p<\/em><sub><em>n<\/em>+1<\/sub> &lt; 2<em>p<\/em><sub><em>n<\/em><\/sub>.<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I recently found out about Andrica&#8217;s conjecture: the square roots of consecutive primes are less than 1 apart. In symbols, Andrica&#8217;s conjecture says that if pn and pn+1 are consecutive prime numbers, then \u221apn+1 \u2212 \u221apn &lt; 1. This has been empirically verified for primes up to 2 \u00d7 1019. If the conjecture is true, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[9],"tags":[94],"class_list":["post-246954","post","type-post","status-publish","format-standard","hentry","category-math","tag-number-theory"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246954","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246954"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246954\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246954"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246954"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246954"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246952,"date":"2026-04-08T18:30:15","date_gmt":"2026-04-08T23:30:15","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246952"},"modified":"2026-04-08T18:30:15","modified_gmt":"2026-04-08T23:30:15","slug":"artemis-1-apollo-12","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/08\/artemis-1-apollo-12\/","title":{"rendered":"A Three- and a Four- Body Problem"},"content":{"rendered":"<p><a href=\"https:\/\/www.johndcook.com\/blog\/2026\/04\/02\/artemis-apollo\/\">Last week<\/a> I wrote about the orbit of Artemis II. The orbit of Artemis I was much more interesting.<\/p>\n<p>Because Artemis I was unmanned, it could spend a lot more time in orbit. The Artemis I mission took 25 days while Artemis II will take 10 days. Artemis I took an unusual path, orbiting the moon the opposite direction of the moon&#8217;s orbit around earth. <a href=\"https:\/\/www.youtube.com\/watch?v=AvVFy3Feb1U&amp;list=WL&amp;index=2\">This video<\/a> by Primal Space demonstrates the orbit both from the perspective of earth and from the perspective of the Moon.<\/p>\n<p><a href=\"https:\/\/www.youtube.com\/watch?v=vLefsklLkqQ&amp;list=WL&amp;index=1\">Another video<\/a> from Primal Space describes the orbit of the third stage of Apollo 12. This stage was supposed to orbit around the sun in 1971, but an error sent it on a complicated unstable orbit of the earth, moon, and sun. It returned briefly to earth in 2002 and expected to return sometime in the 2040s.<\/p>\n<h2>Related posts<\/h2>\n<ul>\n<li class='link'><a href='https:\/\/www.johndcook.com\/blog\/2021\/12\/28\/lagrange-points-l1-and-l2\/'>Finding Lagrange points<\/a><\/li>\n<li class='link'><a href='https:\/\/www.johndcook.com\/blog\/2021\/12\/30\/stable-lagrange-points\/'>When are Lagrange points stable?<\/a><\/li>\n<li class='link'><a href='https:\/\/www.johndcook.com\/blog\/2024\/01\/27\/butterflies-dont-work-that-way\/'>Bad takes on chaos theory<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Last week I wrote about the orbit of Artemis II. The orbit of Artemis I was much more interesting. Because Artemis I was unmanned, it could spend a lot more time in orbit. The Artemis I mission took 25 days while Artemis II will take 10 days. Artemis I took an unusual path, orbiting the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[15],"tags":[],"class_list":["post-246952","post","type-post","status-publish","format-standard","hentry","category-science"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246952","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246952"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246952\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246952"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246952"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246952"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}},{"id":246950,"date":"2026-04-06T19:33:23","date_gmt":"2026-04-07T00:33:23","guid":{"rendered":"https:\/\/www.johndcook.com\/blog\/?p=246950"},"modified":"2026-04-07T06:38:57","modified_gmt":"2026-04-07T11:38:57","slug":"tofolli-gates","status":"publish","type":"post","link":"https:\/\/www.johndcook.com\/blog\/2026\/04\/06\/tofolli-gates\/","title":{"rendered":"Toffoli gates are all you need"},"content":{"rendered":"<p>Landauer&#8217;s principle gives a lower bound on the amount of energy it takes to erase one bit of information:<\/p>\n<p style=\"padding-left: 40px;\"><em>E<\/em> \u2265 log(2) <em>k<\/em><sub><em>B<\/em><\/sub> <em>T<\/em><\/p>\n<p>where <em>k<\/em><sub><em>B<\/em><\/sub> is the Boltzmann constant and <em>T<\/em> is the ambient temperature in Kelvin. The lower bound applies no matter how the bit is physically stored. There is no theoretical lower limit on the energy required to carry out a reversible calculation.<\/p>\n<p>In practice the energy required to erase a bit is around a billion times greater than Landauer&#8217;s lower bound. You might reasonably conclude that reversible computing isn&#8217;t practical since we&#8217;re nowhere near the Landauer limit. And yet in practice reversible circuits have been demonstrated to use less energy than conventional circuits. We&#8217;re far from the ultimate physical limit, but reversibility still provides practical efficiency gains today.<\/p>\n<p>A Toffoli gate is a building block of reversible circuits. A Toffoli gate takes three bits as input and returns three bits as output:<\/p>\n<p style=\"padding-left: 40px;\"><em>T<\/em>(<em>a<\/em>,\u00a0<em>b<\/em>,\u00a0<em>c<\/em>) = (<em>a<\/em>,\u00a0<em>b<\/em>,\u00a0<em>c<\/em> XOR (<em>a<\/em> AND\u00a0<em>b<\/em>)).<\/p>\n<p>In words, a Toffoli gate flips its third bit if and only if the first two bits are ones.<\/p>\n<p>A Toffoli gate is its own inverse, and so it is reversible. This is easy to prove. If <em>a<\/em> =\u00a0<em>b<\/em> = 1, then the third bit is flipped. Apply the Toffoli gate again flips the bit back to what it was. If <em>ab<\/em> = 0, i.e. at least one of the first two bits is zero, then the Toffoli gate doesn&#8217;t change anything.<\/p>\n<p>There is a theorem that any Boolean function can be computed by a circuit made of only NAND gates. We&#8217;ll show that you can construct a NAND gate out of Toffoli gates, which shows any Boolean function can be computed by a circuit made of Toffoli gates, which shows any Boolean function can be computed reversibly.<\/p>\n<p>To compute NAND, i.e. \u00ac (<em>a<\/em> \u2227 <em>b<\/em>), send (<em>a<\/em>,\u00a0<em>b<\/em>, 1) to the Toffoli gate. The third bit of the output will contain the NAND of <em>a<\/em> and <em>b<\/em>.<\/p>\n<p style=\"padding-left: 40px;\"><em>T<\/em><em>(a,\u00a0b<\/em>, 1) = (<em>a<\/em>,\u00a0<em>b<\/em>, \u00ac (<em>a<\/em> \u2227 <em>b<\/em>))<\/p>\n<p>A drawback of reversible computing is that you may have to send in more input than you&#8217;d like and get back more output than you&#8217;d like, as we can already see from the example above. NAND takes two input bits and returns one output bit. But the Toffoli gate simulating NAND takes three input bits and returns three output bits.<\/p>\n<h2>Related posts<\/h2>\n<ul>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2021\/05\/03\/self-reproducing-cellular-automata\/\">Fredkin automata<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2025\/07\/31\/machine-learning-by-satisfiability-solving\/\">Machine learning by satisfiability solving<\/a><\/li>\n<li class=\"link\"><a href=\"https:\/\/www.johndcook.com\/blog\/2020\/11\/19\/minimizing-boolean-expressions\/\">Minimizing Boolean expressions<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Landauer&#8217;s principle gives a lower bound on the amount of energy it takes to erase one bit of information: E \u2265 log(2) kB T where kB is the Boltzmann constant and T is the ambient temperature in Kelvin. The lower bound applies no matter how the bit is physically stored. There is no theoretical lower [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[5],"tags":[68],"class_list":["post-246950","post","type-post","status-publish","format-standard","hentry","category-computing","tag-information-theory"],"acf":[],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246950","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/comments?post=246950"}],"version-history":[{"count":0,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/posts\/246950\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/media?parent=246950"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/categories?post=246950"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.johndcook.com\/blog\/wp-json\/wp\/v2\/tags?post=246950"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}]