Why Does This Recurrence Generate Primes? Eric Rowland 2024-02-06 | The recurrence R(n) = R(n - 1) + gcd(n, R(n - 1)) generates primes. But why? It turns out it's essentially implementing trial division in disguise.Previous video on this sequence: youtu.be/OpaKpzMFOpg----------------Reference:Eric Rowland, A natural prime-generating recurrence, Journal of Integer Sequences 11 (2008) 08.2.8 (13 pages).cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.html----------------0:00 Generating primes1:26 Shortcut4:42 What if 2 n - 1 is prime?9:31 What if 2 n - 1 isn't prime?14:46 Trial division----------------Animated with Manim. https://www.manim.communityMusic by Callistio.Audio recorded at the Lawrence Herbert School of Communication at Hofstra University. https://www.hofstra.edu/communication/Web site: ericrowland.github.ioTwitter: twitter.com/ericrowland
New Breakthrough on a 90-year-old Telephone Question Eric Rowland 2024-09-05 | What numbers do you get when you iteratively scale a table? Approximations of these numbers have been used since the 1930s to predict telephone traffic and in other applications. But mathematically, the exact values are extremely complicated!Our paper identifying the structure behind these numbers:Eric Rowland and Jason Wu, The entries of the Sinkhorn limit of an m × n matrix (25 pages).arxiv.org/abs/2409.02789----------------Other references:Marco Cuturi, Sinkhorn distances: lightspeed computation of optimal transportation distances, Advances in Neural Information Processing Systems 26 (2013) 2292-2300.papers.nips.cc/paper_files/paper/2013/hash/af21d0c97db2e27e13572cbf59eb343d-Abstract.htmlJ. Kruithof, Telefoonverkeersrekening, De Ingenieur 52 (1937) E15-E25.English translation by Pieter-Tjerk de Boer:https://wwwhome.ewi.utwente.nl/~ptdeboer/misc/kruithof-1937-translation.htmlSee Appendix 3d.Melvyn B. Nathanson, Alternate minimization and doubly stochastic matrices, Integers 20A (2020) Article A10 (17 pages).https://math.colgate.edu/~integers/uproc10/uproc10.pdfRobert D. Putnam, Bowling Alone: The Collapse and Revival of American Community (2000) Simon & Schuster.archive.org/details/bowlingalone00robe/page/166/mode/2upRichard Sinkhorn, A relationship between arbitrary positive matrices and doubly stochastic matrices, The Annals of Mathematical Statistics 35 (1964) 876-879.doi.org/10.1214/aoms/1177703591----------------0:00 Predicting telephone traffic1:16 Kruithof's example6:02 2x2 tables8:35 3x3 tables15:56 Rewriting the equation for 3x3 tables22:20 Compact equation for 3x3 tables24:47 Larger tables27:40 Answer to Kruithof's example----------------Animated with Manim. https://www.manim.communityMusic by Callistio.Audio recorded at the Lawrence Herbert School of Communication at Hofstra University. https://www.hofstra.edu/communication/Web site: ericrowland.github.ioTwitter: twitter.com/ericrowland
In 2003 We Discovered a New Way to Generate Primes Eric Rowland 2023-01-20 | There is a Fibonacci-like recurrence that seems to generate primes! It was discovered in 2003, but at the time no one understood why it worked. A few years later, I plotted the primes in a way that reveals some hidden structure. This is a tale of logarithmic scale.Followup video on this sequence: youtu.be/2y_6IIXAI_s----------------References:Fernando Chamizo, Dulcinea Raboso, and Serafín Ruiz-Cabello, On Rowland's Sequence, The Electronic Journal of Combinatorics 18(2) (2011) P10 (10 pages).doi.org/10.37236/2006Benoit Cloitre, 10 conjectures in additive number theory (2011) (46 pages).arxiv.org/abs/1101.4274Eric Rowland, A natural prime-generating recurrence, Journal of Integer Sequences 11 (2008) 08.2.8 (13 pages).cs.uwaterloo.ca/journals/JIS/VOL11/Rowland/rowland21.htmlSerafín Ruiz-Cabello, On the use of the least common multiple to build a prime-generating recurrence, International Journal of Number Theory 13 (2017) 819–833.doi.org/10.1142/S1793042117500439Open access: arxiv.org/abs/1504.05041----------------0:00 Recurrence2:59 Doubling relations4:03 Plotting locations of primes6:24 Clusters of primes9:49 Predicting primes in each cluster15:22 Answers to burning questions18:19 Changing the initial term20:08 Cloitre's lcm recurrence----------------Animated with Manim. https://www.manim.communityThanks to Ken Emmer for supplying the microphone.Web site: ericrowland.github.ioTwitter: twitter.com/ericrowland
An Exact Formula for the Primes: Willans Formula Eric Rowland 2022-09-22 | Formulas for the nth prime number actually exist! One was cleverly engineered in 1964 by C. P. Willans. But is it useful?----------------References:Herbert Wilf, What is an answer?, The American Mathematical Monthly 89 (1982) 289–292.doi.org/10.1080/00029890.1982.11995435C. P. Willans, On formulae for the nth prime number, The Mathematical Gazette 48 (1964) 413–415.doi.org/10.2307/3611701Further reading:Jeffrey Shallit, No formula for the prime numbers?.http://recursed.blogspot.com/2013/01/no-formula-for-prime-numbers.html----------------# Python codeimport mathdef prime(n): return 1 + sum([ math.floor(pow(n/sum([ math.floor(pow(math.cos(math.pi * (math.factorial(j - 1) + 1)/j), 2)) for j in range(1, i+1) ]), 1/n)) for i in range(1, pow(2, n)+1) ])----------------(* Mathematica code *)prime[n_] := 1 + Sum[Floor[(n/Sum[Floor[Cos[Pi ((j - 1)! + 1)/j]^2], {j, 1, i}])^(1/n)], {i, 1, 2^n}]----------------0:00 A formula for primes?1:24 Engineering a prime detector4:00 Improving the prime detector5:46 Counting primes6:29 Determining the nth prime9:42 The final step11:36 What counts as a formula?12:56 What's the point?13:51 Who was Willans?----------------Animated with Manim. https://www.manim.communityThanks to Ken Emmer for supplying the microphone.Web site: ericrowland.github.ioTwitter: twitter.com/ericrowland
1 Billion is Tiny in an Alternate Universe: Introduction to p-adic Numbers Eric Rowland 2022-08-05 | The p-adic numbers are bizarre alternative number systems that are extremely useful in number theory. They arise by changing our notion of what it means for a number to be large. As a real number, 1 billion is huge. But as a 10-adic number, it is tiny! #SoME2----------------Notes and references:The last 30 digits of 2^1000000 and other large powers can be computed using modular arithmetic, by working modulo 10^30. In Mathematica, use the function PowerMod. In Python, use the third argument of pow. These functions implement the method of repeated squaring or one of its variants:en.wikipedia.org/wiki/Exponentiation_by_squaringen.wikipedia.org/wiki/Modular_exponentiationBézout's identity can be used to prove that the numbers from 2 to p-2 pair up perfectly, and the partner of a given number can be computed using the extended Euclidean algorithm:en.wikipedia.org/wiki/Bézout%27s_identityen.wikipedia.org/wiki/Extended_Euclidean_algorithmThe 2-adic limits arising from the (2^n)th Fibonacci numbers were established on page 216 of this paper:Eric Rowland and Reem Yassawi, p-adic asymptotic properties of constant-recursive sequences, Indagationes Mathematicae 28 (2017) 205–220.doi.org/10.1016/j.indag.2016.11.019Hensel's lemma gives conditions for Newton's method to work in the p-adic numbers:en.wikipedia.org/wiki/Hensel%27s_lemma----------------0:00 Introduction2:16 Properties of the real numbers3:19 10-adic integers6:55 Properties of the 10-adic integers10:06 Division?12:47 Limit points13:50 5-adic limit15:36 Fibonacci numbers16:31 Square roots of -118:25 What are p-adics good for?----------------Animated with Manim. https://www.manim.communityMusic by Marc Rowland and Cody Leavitt.Thanks to @catpfaff for helpful feedback on an earlier version.Web site: ericrowland.github.ioTwitter: twitter.com/ericrowland
