Interestingly, you can often find fractal-like structures in nature as it is the result of maximizing surface area (to absorp sunlight) while minimizing space and energy used.
Indeed, you can find an approximation to the (logarithmic) golden spiral in a romanesco, as each spiral arm is about the ratio of the Fibonacci sequence.
It's also one of the simplest possible shapes to encode, repeating the two basic instructions "grow" and "branch" independent of where in the plant you are.
I would have bet a sizable amount of money (maybe 50 english pence) that the picture was of a Romanesco. They're one of my favourite vegetables though not commonly found in supermarkets round my way.
It is unrelated to Ulam Spiral. The patterns there are due to various quadratic polynomials generating a finite number of primes, an observation going back to at least the time of Euler.
Prime numbers are also important in computability theory. Godel number, for example, uses prime number to assign each symbol and laid the foundation for Godel's incompleteness theorem
I want to know more about an intuitive take on how the Zeta function does what it does! I know it must relate somehow to finding (or perhaps excluding) all the composite numbers but I'd really love to get more of a feeling about what each 'octave' of the function is adding-in. Seems like it must be something that 'flattens' the composites but increases sharply (in the infinite sum) at each prime.. but it's still a mystery to me how one could intuitively realise or discover that it's this specific function!? How did he do it?!
I wonder, has anyone tried looking for the pattern for prime numbers in a non-base-10 representation? I've always had a hunch that maybe the chaos only seems random because our representation of numbers could be misaligned with the pattern.
The only thing that base affects is digital representation — statements like “multiples of 3 have their digits sum to a multiple of 3”. All other behavior is a consequence of numbers’ values, which is independent of base.
That question is literally how you derive both the zeta function and the prime counting functions. It also makes for an easy statement of why they are clearly related.
It's very easy to explain too so bear with me on the following layman understandable explanation.
First consider in base 2 every prime is of the form 2n + 1. Ie. every prime is odd. That's pretty understandable right? Every number that's not odd is a factor of 2. I could state that at most, above 2, only half of numbers could possibly be prime.
Now lets do this with base 6 which is 2 x 3. Similarly to the above, in base 6 every prime is of the form 6n + 1 or 6n + 5. Every other form of 6n + [0,2,3,4] is going to be divisible by 2 or 3. This is just an extension of the above idea but we've done it with both 2 and 3 simultaneously. Now i can state that above 6 only 2/6 (1/3rd) of numbers could possibly be prime. Every other number is divisible by 2 or 3.
Base 10 is the above idea but we do it with 2 x 5. Only 10n + [1,3,7,9] are not divisible by 2 or 5.
Lets now continue this idea and also consider base 30. For 2 x 3 x 5 = 30 primes can only be of the form 30n + [1,7,11,13,17,19,23,29]. Any other number is a multiple of either 2,3 or 5. Here we see only 8/30 = 4/15ths numbers above 30 could possibly be prime.
So... what's the formula for how many numbers can possibly be prime? Well if we have factors of 2,3,5... we can first work with the 2 and rule out 1/2 of numbers being prime (above 2 only half of numbers can be prime). Then in the remaining 1/2 of numbers that can still be prime, we can rule out 1/3rd of those numbers possibly being prime. So 1/2 x 1/3 numbers can't possibly be prime. Since we want to state the numbers that COULD possibly be prime we can state the inverse of this fraction. The inverse of a fraction is (1 - fraction). So (1 - 1/2) x (1 - 1/3) = 2/6 = 1/3. Which matches the above. Only 1/3 of numbers above 6 can possibly be prime. Now what if we extended this fraction for more primes? (1 - 1/2) x (1 - 1/3) x (1 - 1/5) = 8/30 = 4/15 numbers above 30 could possibly be prime which again matches the example above. Let's continue (1-1/2) x (1-1/3) x (1-1/5) x (1-1/7) x (1-1/11) x (1-1/13).... This type of equation is known as an Euler product formula. This specific form which multiplys the inverse fractions of the primes like this is called the Reimann Zeta function. The link between the Reimann Zeta function and primes isn't a surprise. The question you asked is literally how you end up coming to the Reimann Zeta function - https://en.wikipedia.org/wiki/Riemann_zeta_function#Euler's_...
Anyway the next question you may have on your mind is what does this series converge to? We can see as you increase the number of primes you get smaller and smaller fractions; 1/2 to 1/3 to 4/15ths of numbers possibly being prime? Well the above is how you derive the prime counting function; https://en.wikipedia.org/wiki/Prime_number_theorem#Elementar... and the answer is that 1/log(x) numbers are possibly prime above a given x.
Hopefully this helps with understanding of the Riemann Zeta function and prime number theory in general. They are literally not that hard to understand in broad terms and the question you asked is exactly how the Zeta function came about.
Also in practice we work with number representations, not number themselves. So there are some patterns where the representation is influenced by which base we encode them into. That's not something specific to primes of course.
For example, length in term of digits or equivalently weight in bits will carry depending on the base, or more generally which encoding system is retained. Most encoding though require to specifically also transmit the convention at some point. Primes on the other hand, are supposedly already accessible from anywhere in the universe. Probably that's part of what make them so fascinating.
You can test it quite easily, but base doesn't seem to make a difference. There are some patterns that emerge when considering the primes spatially, though.
Elsewhere someone already mentioned the Ulam Spiral [1] and I'll add the Sieve of Pritchard [2] which combines the Sieve of Eratosthenes with Wheel Factorization. Its wiki page has a nice visualization. Notice that when the primes are arranged in a rectangular grid (rows at a time, left-to-right, top-to-bottom) there are entire columns that can immediately be eliminated from consideration.
There are some patterns that emerge when you look at them in other bases. For example, in base 6, the final "digit" (hexit?) is either 1 or 5, (with the exception of the primes 2 and 3). In base 4, the final "digit" is either 1 or 3 (with the exception of the prime number 2). Of course mathematicians generally don't talk about this in terms of their base representation, they usually talk about the primes modulo 6 or the primes modulo 4.
And some of those representations actually do reveal some patterns. For example, an odd prime (so any prime other than 2) p can be written as the sum of two squares p = x^2 + y^2 if and only if p = 1 (mod 4). So those primes that end in 1 in the base 4 representation can be written as the sum of two squares, but the ones that end in 3 cannot. This is called Fermat's theorem on sums of two squares: https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_... .
My guess is that there's a number of different theorems about prime numbers that are phrased in terms of modulo arithmetic or whatever that can be converted into statements about the base representations of primes.
If I had to guess, though, I would guess there isn't a base where the pattern suddenly looks regular. That's very much a guess, but I have a couple data points to support that. The first is Dirichlet's prime number theorem: https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith... . For any coprime integers a and b, the sequence a, a + b, a + 2b, a + 3b, ... contains infinite primes. This seems to imply that primes are, in some sense, evenly distributed across the different possible last "digits" of any base-b representation. There's also the Green-Tao theorem (https://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem ) which says that there exist arbitrarily long arithmetic progressions. So for any integer k, there exists some a and b such that a, a + b, a + 2b, ... a + (k-1)b, and a + k*b are all prime! I don't have a good formal argument, but that seems like it would introduce arbitrary "noise" into any proposed pattern of "digits".
Finally, there's the Riemann Hypothesis. This is both my strongest data point and also my weakest data point. There's a deep relationship between the number of primes less than a given number and the zeroes of the Riemann Zeta function. Any pattern on the base-n representation of primes would imply some pattern on the number of primes less than a given number, which would in turn imply some pattern on the zeroes of the Riemann zeta functions. But the Riemann Hypothesis remains unsolved after over 150 years, despite being one of the most-studied problems in number theory. It seems like any pattern in the base-n representation would have meant some pattern in the zeroes of the zeta function, which means we would have made some progress on the Riemann Hypothesis after all this time. I consider this argument both very convincing and not convincing at all, because on one hand I'm relying on the lack of progress of so many people on this problem, which seems convincing, but also maybe it's basically just a logical fallacy, like an appeal to authority.
No, not at all. A bijection is a very strong requirement. There is no kind of morphism of any kind here, between any given prime and a probability, just an estimate of prime density.
No, it doesn't - here's an easy way to see why: You can already assume any conjecture to be true to see if it helps you factor a large number. After all it's easy to check your answer.
> humans decided they were "prime", i.e. most important, based on arbitrary considerations
No, not arbitrary considerations.
The term goes back at least to Euclid who investigated factorization of integers in his "Elements". He used the greek word "protos" that was later translated to Latin as "primus". It doesn't mean "most important", rather "first".
The idea is that primes are the "multiplicative building blocks" for other numbers, the "origin" or "first principles", because every integer factors into primes. When a mathematical object can be decomposed in some way, it is very natural to study the irreducible blocks, because many questions boil down to them.
That image at the top is eerily like Romanesco. I actually thought it was at first, but it's synthetic if you look at the left part (... or is it?).
[0] https://duckduckgo.com/?q=Romanesco&iar=images&t=ffab&iai=ht...
The photo's attribution gives you all you need to know.
https://www.gettyimages.com/detail/photo/romanesco-broccoli-...
Since the left is so distant, I couldn't believe it was real. But it seems to be indeed. Very nice image.
I don't think it's distant? The buds are just physically smaller there.
the fractal broccoli blows my mind.
Fibonacci broccoli.
Doodling in math class (vi hart):
https://m.youtube.com/watch?v=bY1sOzTLrQQ
every plant is a fibonacci plant because of leaves
Interestingly, you can often find fractal-like structures in nature as it is the result of maximizing surface area (to absorp sunlight) while minimizing space and energy used.
Indeed, you can find an approximation to the (logarithmic) golden spiral in a romanesco, as each spiral arm is about the ratio of the Fibonacci sequence.
It's also one of the simplest possible shapes to encode, repeating the two basic instructions "grow" and "branch" independent of where in the plant you are.
I think that actually is a photo of Romanesco or at least a pretty good fake!
I would have bet a sizable amount of money (maybe 50 english pence) that the picture was of a Romanesco. They're one of my favourite vegetables though not commonly found in supermarkets round my way.
It is broccoli.
Yeah it's also called Romanesco-Broccoli. Normal Broccoli is like this [0]
[0] https://duckduckgo.com/?q=broccoli&t=ffab&ia=images&iax=imag...
Is there a visualization possible of this pattern?
For some reason this made me think of the Ulam Spiral -- https://en.wikipedia.org/wiki/Ulam_spiral.
It is unrelated to Ulam Spiral. The patterns there are due to various quadratic polynomials generating a finite number of primes, an observation going back to at least the time of Euler.
The conference in question: https://www.youtube.com/watch?v=suFspoY3bBU
The article is a good "first introduction" to the presentation.
Prime numbers are also important in computability theory. Godel number, for example, uses prime number to assign each symbol and laid the foundation for Godel's incompleteness theorem
I want to know more about an intuitive take on how the Zeta function does what it does! I know it must relate somehow to finding (or perhaps excluding) all the composite numbers but I'd really love to get more of a feeling about what each 'octave' of the function is adding-in. Seems like it must be something that 'flattens' the composites but increases sharply (in the infinite sum) at each prime.. but it's still a mystery to me how one could intuitively realise or discover that it's this specific function!? How did he do it?!
Have you seen the 3b1b video?
https://www.3blue1brown.com/lessons/zeta
See the comment from AnotherGoodName here.
Without paywall: https://www.removepaywall.com/search?url=https://www.scienti...
I wonder, has anyone tried looking for the pattern for prime numbers in a non-base-10 representation? I've always had a hunch that maybe the chaos only seems random because our representation of numbers could be misaligned with the pattern.
Primes follow Benford's law. The base you choose does not matter.
https://t5k.org/notes/faq/BenfordsLaw.html
The only thing that base affects is digital representation — statements like “multiples of 3 have their digits sum to a multiple of 3”. All other behavior is a consequence of numbers’ values, which is independent of base.
That question is literally how you derive both the zeta function and the prime counting functions. It also makes for an easy statement of why they are clearly related.
It's very easy to explain too so bear with me on the following layman understandable explanation.
First consider in base 2 every prime is of the form 2n + 1. Ie. every prime is odd. That's pretty understandable right? Every number that's not odd is a factor of 2. I could state that at most, above 2, only half of numbers could possibly be prime.
Now lets do this with base 6 which is 2 x 3. Similarly to the above, in base 6 every prime is of the form 6n + 1 or 6n + 5. Every other form of 6n + [0,2,3,4] is going to be divisible by 2 or 3. This is just an extension of the above idea but we've done it with both 2 and 3 simultaneously. Now i can state that above 6 only 2/6 (1/3rd) of numbers could possibly be prime. Every other number is divisible by 2 or 3.
Base 10 is the above idea but we do it with 2 x 5. Only 10n + [1,3,7,9] are not divisible by 2 or 5.
Lets now continue this idea and also consider base 30. For 2 x 3 x 5 = 30 primes can only be of the form 30n + [1,7,11,13,17,19,23,29]. Any other number is a multiple of either 2,3 or 5. Here we see only 8/30 = 4/15ths numbers above 30 could possibly be prime.
So... what's the formula for how many numbers can possibly be prime? Well if we have factors of 2,3,5... we can first work with the 2 and rule out 1/2 of numbers being prime (above 2 only half of numbers can be prime). Then in the remaining 1/2 of numbers that can still be prime, we can rule out 1/3rd of those numbers possibly being prime. So 1/2 x 1/3 numbers can't possibly be prime. Since we want to state the numbers that COULD possibly be prime we can state the inverse of this fraction. The inverse of a fraction is (1 - fraction). So (1 - 1/2) x (1 - 1/3) = 2/6 = 1/3. Which matches the above. Only 1/3 of numbers above 6 can possibly be prime. Now what if we extended this fraction for more primes? (1 - 1/2) x (1 - 1/3) x (1 - 1/5) = 8/30 = 4/15 numbers above 30 could possibly be prime which again matches the example above. Let's continue (1-1/2) x (1-1/3) x (1-1/5) x (1-1/7) x (1-1/11) x (1-1/13).... This type of equation is known as an Euler product formula. This specific form which multiplys the inverse fractions of the primes like this is called the Reimann Zeta function. The link between the Reimann Zeta function and primes isn't a surprise. The question you asked is literally how you end up coming to the Reimann Zeta function - https://en.wikipedia.org/wiki/Riemann_zeta_function#Euler's_...
Anyway the next question you may have on your mind is what does this series converge to? We can see as you increase the number of primes you get smaller and smaller fractions; 1/2 to 1/3 to 4/15ths of numbers possibly being prime? Well the above is how you derive the prime counting function; https://en.wikipedia.org/wiki/Prime_number_theorem#Elementar... and the answer is that 1/log(x) numbers are possibly prime above a given x.
Hopefully this helps with understanding of the Riemann Zeta function and prime number theory in general. They are literally not that hard to understand in broad terms and the question you asked is exactly how the Zeta function came about.
Very nice explanation :)
The patterns associated with primes are inherent to the numbers themselves and not their representations. The numbers are the pattern.
Yes.
Also in practice we work with number representations, not number themselves. So there are some patterns where the representation is influenced by which base we encode them into. That's not something specific to primes of course.
For example, length in term of digits or equivalently weight in bits will carry depending on the base, or more generally which encoding system is retained. Most encoding though require to specifically also transmit the convention at some point. Primes on the other hand, are supposedly already accessible from anywhere in the universe. Probably that's part of what make them so fascinating.
You can test it quite easily, but base doesn't seem to make a difference. There are some patterns that emerge when considering the primes spatially, though.
What patterns emerge when you represent primes spatially?
Elsewhere someone already mentioned the Ulam Spiral [1] and I'll add the Sieve of Pritchard [2] which combines the Sieve of Eratosthenes with Wheel Factorization. Its wiki page has a nice visualization. Notice that when the primes are arranged in a rectangular grid (rows at a time, left-to-right, top-to-bottom) there are entire columns that can immediately be eliminated from consideration.
[1]: https://wikipedia.org/wiki/Ulam_spiral
[2]: https://wikipedia.org/wiki/Sieve_of_Pritchard
There are some patterns that emerge when you look at them in other bases. For example, in base 6, the final "digit" (hexit?) is either 1 or 5, (with the exception of the primes 2 and 3). In base 4, the final "digit" is either 1 or 3 (with the exception of the prime number 2). Of course mathematicians generally don't talk about this in terms of their base representation, they usually talk about the primes modulo 6 or the primes modulo 4.
And some of those representations actually do reveal some patterns. For example, an odd prime (so any prime other than 2) p can be written as the sum of two squares p = x^2 + y^2 if and only if p = 1 (mod 4). So those primes that end in 1 in the base 4 representation can be written as the sum of two squares, but the ones that end in 3 cannot. This is called Fermat's theorem on sums of two squares: https://en.wikipedia.org/wiki/Fermat%27s_theorem_on_sums_of_... .
My guess is that there's a number of different theorems about prime numbers that are phrased in terms of modulo arithmetic or whatever that can be converted into statements about the base representations of primes.
If I had to guess, though, I would guess there isn't a base where the pattern suddenly looks regular. That's very much a guess, but I have a couple data points to support that. The first is Dirichlet's prime number theorem: https://en.wikipedia.org/wiki/Dirichlet%27s_theorem_on_arith... . For any coprime integers a and b, the sequence a, a + b, a + 2b, a + 3b, ... contains infinite primes. This seems to imply that primes are, in some sense, evenly distributed across the different possible last "digits" of any base-b representation. There's also the Green-Tao theorem (https://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem ) which says that there exist arbitrarily long arithmetic progressions. So for any integer k, there exists some a and b such that a, a + b, a + 2b, ... a + (k-1)b, and a + k*b are all prime! I don't have a good formal argument, but that seems like it would introduce arbitrary "noise" into any proposed pattern of "digits".
Finally, there's the Riemann Hypothesis. This is both my strongest data point and also my weakest data point. There's a deep relationship between the number of primes less than a given number and the zeroes of the Riemann Zeta function. Any pattern on the base-n representation of primes would imply some pattern on the number of primes less than a given number, which would in turn imply some pattern on the zeroes of the Riemann zeta functions. But the Riemann Hypothesis remains unsolved after over 150 years, despite being one of the most-studied problems in number theory. It seems like any pattern in the base-n representation would have meant some pattern in the zeroes of the zeta function, which means we would have made some progress on the Riemann Hypothesis after all this time. I consider this argument both very convincing and not convincing at all, because on one hand I'm relying on the lack of progress of so many people on this problem, which seems convincing, but also maybe it's basically just a logical fallacy, like an appeal to authority.
Try base 6.
What about base p, where each subsequent digit is the next prime number (also more commonly called the prime factorization)? Or PNS https://medium.com/@sumitkanoje/introducing-a-new-number-sys...
Not that I understand all of this. But does that mean a bijection exists from probability values to specific prime positions?
No, not at all. A bijection is a very strong requirement. There is no kind of morphism of any kind here, between any given prime and a probability, just an estimate of prime density.
Does this have any implications for cryptography where factoring to find large primes is involved?
No, it doesn't - here's an easy way to see why: You can already assume any conjecture to be true to see if it helps you factor a large number. After all it's easy to check your answer.
>In other words, just as a cloud of gas particles could be described deterministically if a powerful enough computer existed
Let them try it with hydrogen gas.
Ok, I'll bite.
Why?
Isn't it still "just" a powerful enough computer?
Hydrogen is small enough that uncertainty principle is not completely irrelevant.
Looking for (possibly accidental) patterns.
The obsession with prime numbers (humans decided they were "prime", i.e. most important, based on arbitrary considerations).
It seems like a version of astrology to me.
Am I wrong? I'd be happy to be proved wrong.
> humans decided they were "prime", i.e. most important, based on arbitrary considerations
No, not arbitrary considerations.
The term goes back at least to Euclid who investigated factorization of integers in his "Elements". He used the greek word "protos" that was later translated to Latin as "primus". It doesn't mean "most important", rather "first".
The idea is that primes are the "multiplicative building blocks" for other numbers, the "origin" or "first principles", because every integer factors into primes. When a mathematical object can be decomposed in some way, it is very natural to study the irreducible blocks, because many questions boil down to them.
You are wrong. Prime numbers are fundamental to mathematics.
The property of certain input numbers being "prime" is required for RSA key generation.