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.
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.
Sharlin 13 hours ago [-]
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.
danwills 17 hours ago [-]
I think that actually is a photo of Romanesco or at least a pretty good fake!
ndsipa_pomu 9 hours ago [-]
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.
YcYc10 16 hours ago [-]
It is broccoli.
teekert 15 hours ago [-]
Yeah it's also called Romanesco-Broccoli. Normal Broccoli is like this [0]
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.
1970-01-01 10 hours ago [-]
Primes follow Benford's law. The base you choose does not matter.
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.
AnotherGoodName 10 hours ago [-]
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.
moi2388 10 hours ago [-]
Very nice explanation :)
mmargenot 11 hours ago [-]
The patterns associated with primes are inherent to the numbers themselves and not their representations. The numbers are the pattern.
psychoslave 9 hours ago [-]
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.
bArray 11 hours ago [-]
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.
alganet 11 hours ago [-]
What patterns emerge when you represent primes spatially?
kevindamm 10 hours ago [-]
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.
Not that I understand all of this. But does that mean a bijection exists from probability values to specific prime positions?
dkural 8 hours ago [-]
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.
DougN7 10 hours ago [-]
Does this have any implications for cryptography where factoring to find large primes is involved?
dkural 8 hours ago [-]
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.
profsummergig 8 hours ago [-]
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.
eapriv 8 hours ago [-]
You are wrong. Prime numbers are fundamental to mathematics.
mjyh 8 hours ago [-]
The property of certain input numbers being "prime" is required for RSA key generation.
ReptileMan 17 hours ago [-]
>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.
Quarrel 13 hours ago [-]
Ok, I'll bite.
Why?
Isn't it still "just" a powerful enough computer?
7 hours ago [-]
ReptileMan 8 hours ago [-]
Hydrogen is small enough that uncertainty principle is not completely irrelevant.
Rendered at 01:10:06 GMT+0000 (Coordinated Universal Time) with Vercel.
For some reason this made me think of the Ulam Spiral -- https://en.wikipedia.org/wiki/Ulam_spiral.
The article is a good "first introduction" to the presentation.
[0] https://duckduckgo.com/?q=Romanesco&iar=images&t=ffab&iai=ht...
https://www.gettyimages.com/detail/photo/romanesco-broccoli-...
https://m.youtube.com/watch?v=bY1sOzTLrQQ
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.
[0] https://duckduckgo.com/?q=broccoli&t=ffab&ia=images&iax=imag...
https://www.3blue1brown.com/lessons/zeta
https://t5k.org/notes/faq/BenfordsLaw.html
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.
[1]: https://wikipedia.org/wiki/Ulam_spiral
[2]: https://wikipedia.org/wiki/Sieve_of_Pritchard
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.
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.
Let them try it with hydrogen gas.
Why?
Isn't it still "just" a powerful enough computer?