I wrote a little program to attack this question for a smaller number of primes. The results don’t encourage me to think that there’s a “principled” answer in general. I ran it for (as it happens) the first 1002 primes, up to 7933. The visibility counts fluctuate wildly; it looks as if there may be a tendency for “typical” visibility counts to decrease, but the largest is 256 for the 943rd prime (7451) which not coincidentally has a large gap before it and smallish gaps immediately after.
It seems plausible that the winner with a billion primes might be the 981,765,348th prime, which is preceded by a gap of length 38 (the largest in the first billion primes), but I don’t know and I wouldn’t bet on it. With 1200 primes you might think the winner would be at position 1183, after the first ever gap of size 14 -- but in fact that gap is immediately followed by another of size 12, and the prime after that does better even though it can’t see its next-but-one neighbour, and both are handily beaten by the 943rd prime which sees lots of others above as well as below.
It’s still feeling to me as if any solution to this is going to involve more brute force than insight. Thomas, would you like to tell us whether you know of a solution that doesn’t involve a lot of calculation? (Since presumably any solution will at least need to know something about all the first billion primes, maybe I need to be less vague. If the solution looked like “the winning prime is the prime p_i for which p_{i+1}-p_{i-1} is greatest” or something similarly simple, I would not consider it to be mostly brute force.)
Well, congratulations for what you have done so far.
I have hoped it will be something like this. An intricated landscape of prime towers. I don’t have a solution yet because I have invented this problem this Monday morning. Like “Oh, My God, it’s Monday morning, I have to publish another Problem on my blog and cross-post it on Lesswrong …”.
I did some Googling to prevent my brains to plagiarize too much, and that was all.
I doubt, that there is a clever solution, just some brute force solutions are possible here. But one has to be clever to perform a brute force solution in this case.
Super-crudely the n’th prime number is about n log n. If this were exact then each tower would see all the others, because the function x → x log x is convex. In practice there are little “random” fluctuations which make a difference. It’s possible that the answer to the question depends critically on those random fluctuations and can be found only by brute force...
Perhaps, there is. But there are billions of such relatively simple constructions possible, such as this “Prime Towers Problem”.
I wonder how many of those are already covered by some older proven theorem or some unproven conjecture maybe. I think many of them are still unvisited and unrelated to anything known. If this one is such, I don’t know. It might be. Just might.
Yes: merely being lower isn’t enough to guarantee visibility, because another intermediate tower might be (lower than the tallest but still) tall enough to block it. Like this, if I can get the formatting to work:
#
# #
# #
# #
# # #
You can’t see the third tower from the first, because the second is in the way.
This is not the only case. For instance, the tops of the towers at heights 11, 17, 23 are collinear (both height differences are 6, both pairs are 2 primes apart).
Even if it turns out not to be relevant to the solution, the question should specify what happens in such cases.
This problem to think about.
I wrote a little program to attack this question for a smaller number of primes. The results don’t encourage me to think that there’s a “principled” answer in general. I ran it for (as it happens) the first 1002 primes, up to 7933. The visibility counts fluctuate wildly; it looks as if there may be a tendency for “typical” visibility counts to decrease, but the largest is 256 for the 943rd prime (7451) which not coincidentally has a large gap before it and smallish gaps immediately after.
It seems plausible that the winner with a billion primes might be the 981,765,348th prime, which is preceded by a gap of length 38 (the largest in the first billion primes), but I don’t know and I wouldn’t bet on it. With 1200 primes you might think the winner would be at position 1183, after the first ever gap of size 14 -- but in fact that gap is immediately followed by another of size 12, and the prime after that does better even though it can’t see its next-but-one neighbour, and both are handily beaten by the 943rd prime which sees lots of others above as well as below.
It’s still feeling to me as if any solution to this is going to involve more brute force than insight. Thomas, would you like to tell us whether you know of a solution that doesn’t involve a lot of calculation? (Since presumably any solution will at least need to know something about all the first billion primes, maybe I need to be less vague. If the solution looked like “the winning prime is the prime p_i for which p_{i+1}-p_{i-1} is greatest” or something similarly simple, I would not consider it to be mostly brute force.)
But then again. Now, I think that there is a non-brute-force solution.
Well, congratulations for what you have done so far.
I have hoped it will be something like this. An intricated landscape of prime towers. I don’t have a solution yet because I have invented this problem this Monday morning. Like “Oh, My God, it’s Monday morning, I have to publish another Problem on my blog and cross-post it on Lesswrong …”.
I did some Googling to prevent my brains to plagiarize too much, and that was all.
I doubt, that there is a clever solution, just some brute force solutions are possible here. But one has to be clever to perform a brute force solution in this case.
Which you guys are.
Initial handwaving:
Super-crudely the n’th prime number is about n log n. If this were exact then each tower would see all the others, because the function x → x log x is convex. In practice there are little “random” fluctuations which make a difference. It’s possible that the answer to the question depends critically on those random fluctuations and can be found only by brute force...
Isn’t this literally asking for the largest increasing prime gap sequence between 1 and 1bil? Probably some number theorist knows this.
If we ask for only the smallest 3000 primes, the answer is then the first tower, which is 2 in height. From there you can see 592 tops.
No major prime gap around 2.
Got it, it’s a combination of gap size and prime magnitude. That’s a weird question, but there might still be a theorem on this.
Perhaps, there is. But there are billions of such relatively simple constructions possible, such as this “Prime Towers Problem”.
I wonder how many of those are already covered by some older proven theorem or some unproven conjecture maybe. I think many of them are still unvisited and unrelated to anything known. If this one is such, I don’t know. It might be. Just might.
The intuitive answer seems to me to be: the last one. It’s the tallest, so it witness exactly one billion towers. Am I misinterpreting something?
I guess some of the towers might block each other from view.
Yes: merely being lower isn’t enough to guarantee visibility, because another intermediate tower might be (lower than the tallest but still) tall enough to block it. Like this, if I can get the formatting to work:
You can’t see the third tower from the first, because the second is in the way.
Yes, exactly so.
There is another small ambiguity here. The towers 2, 3, and 4 have colinear tops. But this is the only case and not important for the solution.
This is not the only case. For instance, the tops of the towers at heights 11, 17, 23 are collinear (both height differences are 6, both pairs are 2 primes apart).
Even if it turns out not to be relevant to the solution, the question should specify what happens in such cases.
Yes. You are right, I thought I might be wrong about this.
Okay. If they are collinear, then they are visible.
As you say, there indeed many examples, even of three literally consecutive primes: https://en.wikipedia.org/wiki/Balanced_prime