The Kitchen Sink and Other Oddities

Atabey Kaygun

Hexadecimal digits of \(\pi\)

Some theory

There is a non-recursive formula that computes \(\pi\) given as \[ \sum_{k=0}^\infty \sum_{i=1}^7 \frac{a_i}{16^k(8k+i)} = \sum_{i=1}^7 \sum_{k=0}^\infty \frac{a_i}{16^k(8k+i)} \] where \[ a_1 = 4,\quad a_2 = a_3 = a_7 = 0,\quad a_4 = -2,\quad a_5 = a_6 = -1 \] This is known as the Bailey–Borwein–Plouffe formula. One can use this series to calculate the hexadecimal digits of \(\pi\) as follows: First, we consider this sum in separate summands as \[ \sum_{k=0}^\infty \frac{a_i}{16^k(8k+i)} \] for \(i=1,\ldots,7\). In order to get the n-th hexadecimal digit we need to multiply the whole series by \(16^n\). \[ \sum_{k=0}^\infty \frac{a_i\cdot 16^n}{16^k(8k+i)} = a_i \cdot \sum_{k=0}^\infty \frac{16^{n-k}}{8k+i} \] and the relevant part of the sum for us is the integer value of the sum \[ a_i\cdot \sum_{k=0}^n \frac{16^{n-k}}{8k+i} \] modulo 16, again for \(i=1,\ldots,7\).

Implementation

The lisp code that generates the n-th hexadecimal digit.

(let ((mtable (make-hash-table :test 'equal)))
   (defun mpow (n p)
      (cond 
         ((= n 0) 0)
         ((= p 0) 1)
         ((< p 0) (/ (mpow n (- p))))
         ((= p 2) (* n n))
         (t (or (gethash (cons n p) mtable)
                (setf (gethash (cons n p) mtable)
                    (if (evenp p) 
                       (mpow (mpow n (/ p 2)) 2)
                       (* n (mpow n (1- p))))))))))

(defun msum (n i)
   (loop for k from 0 to n 
       sum (/ (mpow 16 (- n k)) 
              (+ i (* 8 k)))))

(defun nth-hexa-digit (n)
   (mod 
      (floor 
         (reduce '+ 
            (mapcar (lambda (i j) (* j (msum n i)))
               (list 1 4 5 6)
               (list 4 -2 -1 -1))))
      16))

So, here is the output for the first 2500 hecadecimal digits:

    3243F6A8885A308D313198A2E03707344A4093822299F31D00
    82EFA98EC4E6C89452821E638D01377BE5466CF34E90C6CC0A
    C29B7C97C50DD3F84D5B5B54709179216D5D98979FB1BD1310
    BA698DFB5AC2FFD72DBD01ADFB7B8E1AFED6A267E96BA7C904
    5F12C7F9924A19947B3916CF70801F2E2858EFC16636920D87
    1574E69A458FEA3F4933D7E0D95748F728EB658718BCD58821
    54AEE7B54A41DC25A59B59C30D5392AF26013C5D1B02328608
    5F0CA417918B8DB38EF8E79DCB0603A180E6C9E0E8BB01E8A3
    ED71577C1BD314B2778AF2FDA55605C60E65525F3AA55AB945
    748986263E8144055CA396A2AAB10B6B4CC5C341141E8CEA15
    486AF7C72E993B3EE1411636FBC2A2BA9C55D741831F6CE5C3
    E169B87931EAFD6BA336C24CF5C7A325381289586773B8F489
    86B4BB9AFC4BFE81B6628219361D809CCFB21A991487CAC605
    DEC8032EF845D5DE98575B1DC262302EB651B8823893E81D39
    6ACC50F6D6FF383F442392E0B4482A484200469C8F04A9E1F9
    B5E21C66842F6E96C9A670C9C61ABD388F06A51A0D2D8542F6
    8960FA728AB5133A36EEF0B6C137A3BE4BA3BF0507EFB2A98A
    1F1651D39AF017666CA593E82430E888CEE8619456F9FB47D8
    4A5C33B8B5EBEE06F75D885C12073401A449F56C16AA64ED3A
    A62363F77061BFEDF72429B023D37D0D724D00A1248DB0FEAD
    349F1C09B075372C980991B7B25D479D8F6E8DEF7E3FE501AB
    6794C3B976CE0BD04C006BAC1A94FB6409F60C45E5C9EC2196
    A246368FB6FAF3E6C53B51339B2EB3B52EC6F6DFC511F9B309
    52CCC814544AF5EBD09BEE3D004DE334AFD660F2807192E4BB
    3C0CBA85745C8740FD20B5F39B9D3FBDB5579C0BD1A60320AD
    6A100C6402C7279679F25FEFB1FA3CC8EA5E9F8DB3222F83C7
    516DFFD616B152F501EC8AD0552AB323DB5FAFD23876053317
    B483E00DF829E5C57BBCA6F8CA01A87562EDF1769DBD542A8F
    6287EFFC3AC6732C68C4F5573695B27B0BBCA58C8E1FFA35DB
    8F011A010FA3D98FD2183B84AFCB56C2DD1D35B9A53E479B6F
    84565D28E49BC4BFB9790E1DDF2DAA4CB7E3362FB1341CEE4C
    6E8EF20CADA36774C01D07E9EFE2BF11FB495DBDA4DAE90919
    8EAAD8E716B93D5A0D08ED1D0AFC725E08E3C5B2F8E7594B78
    FF6E2FBF2122B648888B812900DF01C4FAD5EA0688FC31CD1C
    FF191B3A8C1AD2F2F2218BE0E1777EA752DFE8B021FA1E5A0C
    C0FB56F74E818ACF3D6CE89E299B4A84FE0FD13E0B77CC43B8
    1D2ADA8D9165FA2668095770593CC7314211A1477E6AD20657
    7B5FA86C75442F5FB9D35CFEBCDAF0C7B3E89A0D6411BD3AE1
    E7E4900250E2D2071B35E226800BB57B8E0AF2464369BF009B
    91E5563911D59DFA6AA78C14389D95A537F207D5BA202E5B9C
    5832603766295CFA911C819684E734A41B3472DCA7B14A94A1
    B5100529A532915D60F573FBC9BC6E42B60A47681E6740008B
    A6FB5571BE91FF296EC6B2A0DD915B6636521E7B9F9B6FF340
    52EC585566453B02D5DA99F8FA108BA47996E85076A4B7A70E
    9B5B32944DB75092EC4192623AD6EA6B049A7DF7D9CEE60B88
    FEDB266ECAA8C71699A17FF5664526CC2B19EE1193602A5750
    94C29A0591340E4183A3E3F54989A5B429D656B8FE4D699F73
    FD6A1D29C07EFE830F54D2D38E6F0255DC14CDD20868470EB2
    66382E9C6021ECC5E09686B3F3EBAEFC93C9718146B6A70A16
    87F358452A0E286B79C5305AA5007373E07841C7FDEAE5C8E7

Older Posts

[2024-11-12] Hosoya Index of Balanced Binary Trees

[2024-11-11] Hosoya Index of a Graph

[2024-10-29] The Clique Number of a Simple Graph

[2024-10-28] The Size of Maximally Independent Subsets in a Graph

[2023-11-03] Graph Algorithms in JGraphT with Common Lisp

[2023-10-28] An Implementation of Pandas’ cut and qcut in Lisp

[2023-07-24] A Collatz-like Conjecture for the Projective Line

[2023-03-06] Twin Primes, Cousin Primes, Sexy Primes, and Prime Triplets

[2023-03-02] Set of All Partitions of a Finite Set

[2023-02-14] Non-crossing Partitions and Dyck Words

[2023-02-13] Non-crossing Linear Chords

[2023-02-04] Clojure/Python Interop Examples

[2023-01-14] Graph Algorithms in Clojure with JGraphT

[2022-03-29] 2D-Random Walk

[2022-03-28] Trade Deficit vs Exchange Rate Curve

[2022-03-16] Working with World Bank Data in Python

[2022-03-09] Working with European Central Bank data in python (revisited)

[2022-01-24] A Clique Analysis of Quakers in early modern Britain (1500-1700)

[2021-12-05] Boyer–Moore and Misra-Gries Algorithms in Clojure

[2021-09-12] Tension in Text Plotted

[2021-09-02] Statistical Distributions using Apache Commons Math in Clojure

[2021-08-31] Reduce with Intermediate Results in Common Lisp

[2021-08-21] Multivariate Regression Implemented in Clojure

[2021-05-29] Using Neural Networks to Detect Graph Properties

[2021-04-17] Fast Null-Space Calculation via LU-Decomposition

[2021-02-24] Stoer-Wagner Algorithm in Clojure

[2021-02-19] Calculating Vertex Covers in Clojure

[2021-02-18] Listing All Paths in a Graph

[2021-02-14] Strict Dyck Words and Fibonacci Numbers

[2021-02-14] Kruskal’s Algorithm in Common Lisp

[2021-02-13] Kruskal's Algorithm Implemented in Clojure

[2021-02-10] An integer dynamical system of integers

[2021-02-08] Binary Symmetrization

[2021-01-28] Prüfer Encoding and Decoding of a Tree in Clojure

[2021-01-27] Counting Cycle-Free Paths in a Graph

[2021-01-27] Counting Connected Labeled Graphs

[2020-12-18] Counting Graphs with a Prescribed Degree Sequence

[2020-12-13] Havel–Hakimi Algorithm in Clojure

[2020-12-12] Havel–Hakimi Algorithm in Common-Lisp

[2020-10-23] The Quadratic Casimir Element

[2020-07-04] Collatz Sequence in Binary

[2020-07-02] A Lazy Sequence of Primes in Clojure

[2020-06-10] Yet Another Fizz-Buzz in Common Lisp

[2020-05-12] ECB Data with Clojure and Vega-Lite

[2020-05-06] Processing ECB Data with Common Lisp

[2020-04-17] Next Permutation in the Lexicographical Ordering

[2020-04-13] Turkish Hyphenation in Common Lisp

[2020-04-01] Using JavaPlex with Clojure

[2019-11-05] Constricted Arithmetic Progressions

[2019-11-03] The Number of Arithmetic Progressions of Integers

[2019-05-06] Bron-Kerbosch Algorithm in Clojure

[2019-05-01] An Implementation of Ford-Fulkerson Algorithm in Clojure

[2019-04-22] Document Summarization via Nonnegative Matrix Factorization

[2019-04-20] Latent Semantic Analysis in Clojure

[2019-04-13] K-Nearest Neighbors Algorithm in Clojure

[2019-04-06] K-Means Implemented in Clojure

[2019-03-19] Prüfer Encoding/Decoding of a Tree in Common Lisp

[2019-03-05] Gale-Shaply Algorithm in Common Lisp

[2019-03-02] Calculating The Correct Rank of a Matrix

[2018-12-04] Feed-forward and back-propagation in neural networks as left- and right-fold

[2018-10-31] Nonnegative Matrix Decomposition in Clojure

[2018-10-30] Non-negative Matrix Decomposition in Scala

[2018-08-30] Working with European Central Bank Data in Scala

[2018-07-30] Perverse Sequences

[2018-05-28] Online Perceptron in Common Lisp

[2018-05-26] Online Perceptron

[2018-05-18] Online Regression

[2018-05-06] Knut’s Algorithm-S in Common Lisp

[2018-02-28] Irreducible Dyck Words

[2018-02-19] Optimization with GNU Scientific Library for Lisp

[2018-02-10] Van Eck’s Sequence

[2018-02-09] Hiring networks in mathematics

[2018-02-08] Linus Sequence

[2018-02-05] Egyptian Fractions

[2018-02-01] Listing all Young Tableaux

[2018-01-23] Collatz sequence (yet again)

[2018-01-15] Hofstadter's Q sequence

[2018-01-09] Farey Sequence

[2018-01-09] Catalan's Triangle

[2018-01-06] The Shoelace Formula for the Area of a Polygon

[2017-10-01] Working with European Central Bank Data in Python

[2017-09-27] Expected Value of the Diameter of a Tree

[2017-09-26] Using Quandl with kixi.stats on Clojure

[2017-09-22] Using Quandl with Common Lisp

[2017-08-05] Solving Linear Equations in Natural Numbers

[2017-07-31] Transitive Closure of a Directed Graph or a Relation

[2017-07-20] Steenrod-Milnor and Tournament Sequences

[2017-07-15] A lower bound on the radius of a graph

[2017-07-08] All partitions of an integer

[2017-07-06] Some Hasse Diagrams

[2017-07-04] Shuffles

[2017-07-03] Kaprekar Sequence

[2017-07-01] Lattice of Dyck Words

[2017-06-28] The poset of connected subgraphs of a connected graph

[2017-06-21] Calculating the Diameter and the Radius of a Graph Using Tropic Linear Algebra

[2017-06-19] Generating random regular graphs

[2017-06-14] Estimating the maximum element of a large list

[2017-06-09] A Stochastic Gradient Descent Implementation in Clojure

[2017-06-06] A topology problem

[2017-04-22] Listing duplicate files

[2017-03-14] My First Idris Proof

[2016-12-02] Distinguishing hash functions (part II)

[2016-12-01] Distinguishing hash functions

[2016-10-20] Hofstadter-Conway $10,000 sequence

[2016-08-18] A Solution for Problem 171 of 4Clojure

[2016-08-16] Puzzles and Group Theory

[2016-08-13] Using Weka within Lisp

[2016-07-12] Funniest and Unfunniest Jokes in the Jester Dataset

[2016-07-05] Generating Uniformly Random Connected Graphs

[2016-06-16] The Robinson-Schensted Algorithm

[2016-06-01] Conjugate Partitions

[2016-04-27] Using Word2Vec from Clojure

[2016-04-24] Using Word2Vec from Common Lisp

[2016-04-18] A Migration Analysis

[2016-04-11] Basic Data Analysis with CL without Frameworks

[2016-03-25] Parallel map-reduce in Common Lisp

[2016-02-22] Text Summarization and Topic Analysis

[2016-01-27] Set Covering Problem

[2016-01-25] Kolmogorov-Smirnov Test

[2016-01-20] Eigen-values of the Laplacian and Connected Components of a Graph

[2015-12-12] Dual Graphs

[2015-10-26] Longest Increasing Subsequence Revisited

[2015-10-16] Document Summarization via Markov Chains

[2015-10-07] Computational Literary Analysis

[2015-09-30] Library of Babel in Common Lisp

[2015-09-28] Merging Association Lists in Common Lisp

[2015-07-22] Cheapest Paths via Tropic Matrices

[2015-07-21] Hidden Markov Models via Tropic Matrices

[2015-07-08] A non-technical post

[2015-06-28] An implementation of the Viterbi algorithm in Common Lisp

[2015-05-28] Greatest Common Divisor of Two Rational Numbers

[2015-05-21] Partitions of Equal Measure Whatever the Measure May Be

[2015-05-14] Finding Cliques in a Graph

[2015-05-12] Set Cover Problem

[2015-05-03] Threading Macros in Common Lisp

[2015-05-03] Happy Numbers

[2015-05-01] Collatz Primes

[2015-04-23] Splitting Streams

[2015-04-06] Hamming Distance and Double Hashing

[2015-04-05] Hamming Distance and Hashing Functions

[2015-04-05] Hamming Derivative of Hashing Functions

[2015-04-02] A Topology Problem

[2015-03-21] Curve Fitting is a Gram-Schmidt Reduction

[2015-03-08] Maximum number of characters using keystrokes A, Ctrl+A, Ctrl+C and Ctrl+V

[2015-03-06] Eccentricity, Radius and Diameter in a Graph, Revisited

[2015-03-01] Graphs and Entropy

[2015-02-22] Math PhD Hiring Network (Part 3)

[2015-02-19] Math PhD Hiring Network (Part 2)

[2015-02-18] Math PhD Hiring Network (Part 1)

[2015-02-17] Faculty Networks and Inequality in Hiring Practices in Universities

[2015-02-10] Functional Streams in Lisp Explained

[2015-02-05] Collatz-type Conjectures (Continued)

[2015-02-04] Collatz-type Conjectures (Continued)

[2015-01-31] Collatz-type Conjectures (Continued)

[2015-01-30] Collatz-type Conjectures

[2015-01-28] Experiments with Infinite Recursive Sequences (continued)

[2015-01-17] Experiments with Infinite Recursive Sequences

[2015-01-10] Goldbach Pairs

[2015-01-02] Collatz Lengths (Continued)

[2015-01-01] Functional Streams

[2014-12-27] Polarization in the US Congress

[2014-12-18] Partition a sequence

[2014-11-28] Uniformly Random Permutations

[2014-11-22] An Implementation of Ford-Fulkerson Algorithm in Common Lisp

[2014-11-17] Tropic Calculation of Cheapest Paths

[2014-11-05] Longest common subsequence of two sequences

[2014-10-30] Counting Spanning Trees of a Graph

[2014-10-26] Longest Increasing Subsequence

[2014-10-24] The Number of Inversions in a Sequence

[2014-10-22] Hashes and Entropy

[2014-10-09] Estimating Cardinality with Constant Memory Complexity

[2014-09-30] Landau's Function

[2014-09-29] A Problem on Substitution Ciphers and Group Theory

[2014-09-28] A Morse Code Translator

[2014-09-23] A Memoization Macro for Common Lisp

[2014-09-21] Reducers are Monoid Morphisms

[2014-09-18] Number of isomorphism classes of binary trees

[2014-09-07] CONS is your friend

[2014-08-22] A Zipf's Law Simulation

[2014-08-07] Generating Uniformly Random Trees

[2014-07-09] A Solution for Project Euler #463

[2014-06-12] Entropy of truncated MD5 hashing

[2014-06-08] Hexadecimal digits of π

[2014-02-11] Information content of n-grams

[2014-02-08] Turkish Sentiment Analysis Using Thesaurus Distance

[2014-02-01] Sentiment analysis using word distances

[2014-01-27] Phase transitions in entropy

[2013-12-13] Optimal length of n-grams

[2013-12-10] Counting strings that contain intervals of same letter repetitions

[2013-12-02] Patterns Separating Large Texts

[2013-11-23] Collatz Sequences (Continued)

[2013-11-11] Entropy and approximately one-to-one maps

[2013-10-23] Tree Isomorphism

[2013-10-15] Self Organizing Maps

[2013-09-15] Euler Project #401

[2013-09-15] An additively recursive definition of the Moebius function

[2013-09-11] An Unsuccessful Attempt for Solving Euler Project #401

[2013-09-04] Uniform Sampling from Parametrized Submanifolds in Scala

[2013-09-04] Uniform Sampling from Parametrized Submanifolds

[2013-08-30] Randomly Generated Points Obeying a Distribution

[2013-08-25] Simulated Annealing in Lisp

[2013-08-21] Eigenvalues and Eigenvectors in GSLL

[2013-08-16] Reservoir Sampling

[2013-08-11] Gibbs sampling in lisp compared with C

[2013-08-10] Logistic Regression in lisp

[2013-08-10] Linear Discriminant Analysis in R

[2013-07-17] A Gradient Descent Implementation in Lisp

[2013-07-01] k-Nearest Neighbor Classification Algorithm Implemented in Lisp

[2013-05-19] Newton-Raphson Method

[2013-05-07] Levenshtein Distance

[2013-04-15] Cut points in a graph

[2013-04-01] Experiments on Collatz Lengths (Continued)

[2013-02-18] The sound of the torsion parts of homotopy groups of spheres

[2013-02-12] Monadic Units

[2013-02-07] Distribution of Collatz Lengths (continued)

[2013-02-03] Distribution of Collatz Lengths

[2013-01-31] Quotients of polynomial algebras

[2013-01-12] Path ideals

[2013-01-10] McCarthy91 Terminates

[2013-01-09] Finding all paths in a directed graph

[2013-01-04] A Simple Monte-Carlo Integration Implementation in Lisp

[2012-12-30] A simple problem in Kolmogorov-Chaitin complexity

[2012-12-29] From walks to paths

[2012-12-16] Higher order functions, functors and monads

[2012-12-13] Eccentricity, Radius and Diameter in an Undirected Graph

[2012-11-29] Untitled

[2012-11-25] Strictly Increasing Labels of Directed Graphs

[2012-11-19] Strictly Increasing Labellings of Directed Graphs

[2012-11-17] Nilpotent elements in an artinian algebra

[2012-11-04] Local rings, idempotents and non-invertible elements

[2012-10-18] An implementation of the fixed-radius near neighbor clustering algorithm in lisp

[2012-10-15] Reducing directed graphs

[2012-10-10] An implementation of the k-means clustering algorithm in lisp

[2012-10-08] A comparison of different map functions in lisp

[2012-10-03] Source code entropy

[2012-09-28] Collisions in random walks

[2012-09-26] Transitive closure of a directed graph

[2012-09-26] Solving linear equations in ℕ

[2012-09-26] Listing partitions

[2012-09-26] Inverting formal power series

[2012-09-26] Hasse subgraph of a directed graph